QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#415854#5409. Perotationsidekick25760 145ms7792kbC++981.3kb2024-05-21 11:37:052024-05-21 11:37:05

Judging History

你现在查看的是最新测评结果

  • [2024-05-21 11:37:05]
  • 评测
  • 测评结果:60
  • 用时:145ms
  • 内存:7792kb
  • [2024-05-21 11:37:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
const int N=1e5+4;
int n,q,a[N],f[N];
int mid(int x,int a,int b){
    if(x<max(a,b)&&x>min(a,b)) return 1;
    return 0;
}
int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[j]<a[i]) f[i]++;
    f[0]=1;
    while(q--){
        int x=read(),y=read();
        if(x>y) swap(x,y);
        f[x]=f[y]=0;
        swap(a[x],a[y]);
        for(int i=x+1;i<=n;i++)
            if(a[i]<a[x]) f[x]++;
        for(int i=y+1;i<=n;i++)
            if(a[i]<a[y]) f[y]++;
        for(int i=x+1;i<y;i++)
            if(mid(a[i],a[x],a[y])) f[i]+=(a[x]>a[y]?1:-1);
        for(int i=n;~i;i--)
            if(f[i]&1){
                // cout<<f[i]<<" ";
                cout<<i+1<<"\n";
                break;
            }
        // for(int i=1;i<=n;i++) cout<<f[i]<<" ";
        // cout<<"\n";
    }
    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 5684kb

input:

2 1
1 2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5684kb

input:

9 7
3 5 8 2 4 9 1 6 7
2 8
3 1
2 1
1 5
3 8
1 3
9 1

output:

7
7
7
7
7
7
7

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 7692kb

input:

7 7
6 7 2 1 5 3 4
3 1
3 1
7 5
1 6
6 5
6 1
1 7

output:

3
4
6
7
4
4
4

result:

ok 7 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 5708kb

input:

7 7
2 4 3 1 5 6 7
7 6
6 3
3 1
1 4
3 4
2 5
4 1

output:

7
6
6
6
6
6
6

result:

ok 7 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 5608kb

input:

6 6
5 3 1 4 2 6
5 4
5 2
4 3
6 5
1 5
6 4

output:

1
3
4
6
6
6

result:

ok 6 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 7752kb

input:

10 9
7 9 2 5 1 6 8 3 4 10
4 5
2 9
10 6
6 1
5 3
10 1
5 7
1 7
8 3

output:

4
8
10
10
10
8
6
8
8

result:

ok 9 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 5740kb

input:

8 8
4 2 6 5 8 3 7 1
5 6
2 4
6 5
6 1
4 6
1 2
2 8
8 6

output:

8
8
8
8
8
8
8
8

result:

ok 8 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 7780kb

input:

8 8
6 8 4 7 1 3 5 2
1 4
3 8
3 8
8 3
6 2
1 5
1 6
7 4

output:

8
8
8
8
8
8
8
8

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 5660kb

input:

6 8
6 1 2 5 3 4
6 1
4 5
2 5
5 3
4 6
4 1
2 4
4 2

output:

5
2
5
5
3
2
3
2

result:

ok 8 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 5612kb

input:

10 7
3 1 8 7 6 2 9 5 10 4
7 3
10 7
1 3
2 1
8 10
8 3
1 2

output:

10
10
10
10
10
10
10

result:

ok 7 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 7684kb

input:

8 7
3 1 4 2 7 5 8 6
6 5
6 5
2 3
5 1
4 8
7 2
5 1

output:

8
8
8
8
8
8
8

result:

ok 7 numbers

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #12:

score: 20
Accepted
time: 1ms
memory: 5688kb

input:

90 83
53 72 1 6 48 45 55 24 20 78 36 82 67 35 63 7 61 69 90 52 21 80 65 32 71 81 38 43 34 64 60 40 4 49 28 89 56 77 51 46 2 18 5 62 19 57 3 88 39 85 86 23 75 10 83 27 22 68 9 37 76 50 87 79 16 11 25 26 14 8 74 41 66 58 84 12 54 17 33 42 15 44 13 73 30 29 70 59 47 31
76 86
30 50
85 3
23 51
42 59
37 8...

output:

90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
89
89
89
89
89
89
89
89
89
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88
88

result:

ok 83 numbers

Test #13:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

87 95
69 48 22 37 65 67 72 78 59 85 74 26 25 28 53 51 23 56 50 52 81 76 57 30 10 49 21 87 34 16 15 80 43 47 2 20 86 13 29 36 58 71 83 35 40 46 38 54 14 18 84 39 27 3 61 77 64 8 6 68 11 31 7 73 1 9 4 79 55 63 82 75 33 32 24 5 19 45 41 60 44 66 70 17 42 62 12
53 8
8 34
49 54
16 33
64 78
11 2
73 85
51 ...

output:

87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
85
85
85
85
85
85
85
85
85
85
83
83
83
83
83
83
83
83
83
83
83
83
85
85
85
85
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87
87

result:

ok 95 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 7652kb

input:

87 90
19 70 69 56 20 16 66 9 21 47 81 5 50 7 24 85 1 80 4 73 37 52 12 75 64 3 57 71 77 28 40 17 82 65 45 22 6 79 87 63 27 39 42 83 38 11 14 41 31 74 15 60 62 86 34 23 49 33 68 51 61 32 67 59 35 58 30 29 36 25 48 84 13 54 10 53 46 78 76 26 43 72 2 8 18 44 55
58 62
14 17
36 78
11 20
35 15
85 21
74 64
...

output:

83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
83
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
86
84
84
84
84
84
84
84
84
84
84
84
84
84
84
86
86
86
86
86
86

result:

ok 90 numbers

Test #15:

score: 0
Accepted
time: 1ms
memory: 7740kb

input:

91 71
40 81 83 16 76 5 85 64 84 82 63 42 32 71 73 3 51 11 30 65 17 20 56 31 4 54 49 38 52 86 34 48 80 6 26 87 8 25 36 23 2 7 70 62 67 88 72 47 55 77 29 66 68 69 91 37 79 22 44 61 45 41 74 89 28 15 13 39 75 14 46 21 33 35 43 18 58 53 90 57 19 10 12 50 59 60 1 9 24 27 78
44 18
42 5
41 26
41 29
40 1
38...

output:

45
45
45
45
45
45
45
45
45
45
45
45
45
73
74
73
72
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80
80

result:

ok 71 numbers

Test #16:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

80 66
26 54 23 35 62 1 25 56 12 48 37 8 80 7 32 40 52 78 69 6 29 10 36 50 16 42 61 60 27 38 14 77 17 9 20 59 64 79 5 76 67 39 18 34 13 71 15 70 66 19 24 63 72 53 2 75 65 51 22 44 73 28 11 3 57 33 30 74 46 55 31 41 43 68 4 47 49 58 21 45
39 1
37 18
35 6
32 3
31 21
31 27
31 46
46 55
54 6
51 19
51 45
5...

output:

40
40
40
40
40
40
47
55
55
55
55
55
55
55
55
55
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
72
72
70

result:

ok 66 numbers

Test #17:

score: 0
Accepted
time: 1ms
memory: 5684kb

input:

100 100
15 10 37 71 30 22 78 12 33 13 29 26 27 11 3 24 42 18 21 28 73 23 53 57 91 32 20 6 4 5 82 16 95 80 14 17 76 25 9 8 31 7 99 19 96 49 59 2 65 93 70 58 60 43 44 50 74 92 35 86 98 84 90 52 67 72 83 62 56 100 46 89 69 36 45 38 77 61 81 63 41 55 87 79 39 88 54 85 64 75 48 97 68 94 40 66 1 51 34 47
...

output:

68
64
68
68
68
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
85
90
90
90
90
90
90
90
90
90
90
90
90

result:

ok 100 numbers

Test #18:

score: 0
Accepted
time: 1ms
memory: 5684kb

input:

94 100
85 86 55 56 3 4 67 68 61 62 77 78 65 66 89 90 73 74 45 46 11 12 49 50 37 38 51 52 43 44 83 84 41 42 31 32 5 6 25 26 7 8 79 80 1 2 47 48 91 92 35 36 23 24 29 30 93 94 17 18 15 16 71 72 53 54 27 28 21 22 75 76 19 20 63 64 57 58 39 40 59 60 69 70 33 34 13 14 81 82 87 88 9 10
56 78
86 68
55 77
85...

output:

78
86
86
1
23
31
23
1
18
1
53
1
90
1
91
1
29
1
55
77
77
77
18
1
85
85
85
1
26
1
54
87
87
1
66
1
73
1
50
82
82
1
80
84
80
1
78
88
94
88
78
1
91
1
79
79
79
1
49
1
65
1
44
1
27
77
27
1
60
60
47
1
92
1
75
1
74
1
57
94
94
87
57
1
68
68
81
81
81
1
47
53
53
1
34
1
33
65
33
1

result:

ok 100 numbers

Test #19:

score: 0
Accepted
time: 1ms
memory: 7724kb

input:

100 100
43 44 77 78 75 76 99 100 1 2 5 6 19 20 89 90 47 48 41 42 65 66 67 68 25 26 91 92 95 96 71 72 97 98 49 50 23 24 17 18 81 82 55 56 45 46 27 28 21 22 29 30 15 16 51 52 11 12 31 32 61 62 87 88 57 58 35 36 73 74 9 10 59 60 7 8 85 86 83 84 33 34 39 40 53 54 37 38 69 70 13 14 93 94 79 80 63 64 3 4
...

output:

96
96
96
1
36
1
56
1
88
1
81
1
68
1
37
1
90
1
28
1
98
98
98
1
55
86
86
1
93
1
84
84
69
69
65
1
99
1
55
1
61
61
42
1
88
1
30
1
38
1
49
49
44
1
96
96
85
85
85
1
50
1
60
60
60
1
45
45
26
1
27
1
42
78
78
1
53
53
100
100
100
1
94
94
64
88
88
1
87
96
96
1
98
98
98
97
97
1
83
1

result:

ok 100 numbers

Test #20:

score: 0
Accepted
time: 1ms
memory: 7704kb

input:

84 83
55 56 13 14 69 70 79 80 3 4 49 50 9 10 27 28 29 30 59 60 73 74 1 2 11 12 77 78 51 52 45 46 15 16 17 18 33 34 31 32 25 26 53 54 43 44 63 64 41 42 39 40 19 20 37 38 81 82 75 76 83 84 23 24 47 48 61 62 5 6 7 8 35 36 21 22 65 66 57 58 71 72 67 68
12 32
11 31
62 82
22 48
21 47
78 72
77 71
68 52
61 ...

output:

13
1
63
63
63
78
63
68
68
1
33
23
33
1
48
1
63
1
33
1
60
1
40
51
80
80
80
1
75
61
74
1
58
1
72
1
31
51
31
1
62
1
39
73
73
79
79
1
67
1
74
75
74
74
74
76
76
1
39
1
4
1
82
82
76
76
76
1
22
23
23
1
78
1
52
1
47
57
57
1
75
1
59

result:

ok 83 numbers

Test #21:

score: 0
Accepted
time: 1ms
memory: 7708kb

input:

100 100
79 80 63 64 23 24 41 42 87 88 33 34 99 100 65 66 73 74 11 12 69 70 71 72 19 20 59 60 75 76 35 36 15 16 3 4 67 68 17 18 93 94 39 40 9 10 81 82 13 14 89 90 49 50 31 32 43 44 97 98 95 96 77 78 57 58 55 56 29 30 51 52 61 62 27 28 53 54 47 48 25 26 91 92 5 6 83 84 7 8 37 38 45 46 1 2 21 22 85 86
...

output:

75
1
33
1
59
1
80
98
98
98
98
98
17
1
80
80
80
80
80
80
80
89
89
1
75
75
75
54
74
74
54
1
48
1
87
87
84
88
88
1
62
1
61
1
95
1
86
86
86
86
30
1
47
1
86
86
39
1
83
1
10
1
90
90
90
1
26
1
41
66
66
1
67
1
94
1
46
1
71
71
70
1
82
1
96
96
96
1
14
68
68
68
40
1
79
79
79
1
48
1

result:

ok 100 numbers

Test #22:

score: 0
Accepted
time: 1ms
memory: 7632kb

input:

95 82
65 66 53 54 1 2 83 84 19 20 43 44 89 90 5 6 11 12 67 68 55 56 87 88 77 78 17 18 7 8 49 50 9 10 57 58 79 80 71 72 23 24 81 82 93 94 3 4 39 40 13 14 21 22 59 60 25 26 91 92 63 64 15 16 69 70 47 48 61 62 41 42 33 34 31 32 27 28 35 36 45 46 73 74 37 38 29 30 51 52 85 86 75 76 95
74 62
73 61
8 50
7...

output:

73
1
45
1
72
1
11
92
92
92
92
87
87
87
87
87
87
87
87
87
27
1
88
1
82
82
82
82
82
69
84
84
84
84
84
68
68
1
78
78
78
92
92
92
92
92
92
92
92
92
81
81
68
1
43
43
43
1
77
77
39
1
71
71
71
71
60
60
94
60
60
1
73
1
33
52
52
46
33
1
70
1

result:

ok 82 numbers

Test #23:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

100 100
55 56 49 50 81 82 37 38 51 52 35 36 89 90 57 58 7 8 27 28 99 100 65 66 5 6 87 88 83 84 53 54 91 92 77 78 13 14 29 30 41 42 9 10 45 46 63 64 93 94 59 60 23 24 1 2 3 4 97 98 69 70 85 86 21 22 25 26 31 32 11 12 39 40 95 96 19 20 73 74 79 80 47 48 71 72 43 44 15 16 67 68 61 62 75 76 17 18 33 34
...

output:

47
55
69
55
55
64
64
64
64
64
84
84
84
84
84
1
96
96
96
96
72
1
31
89
91
91
31
38
38
55
38
94
38
1
26
26
96
96
96
96
96
96
96
96
96
96
90
90
90
1
65
92
92
92
92
92
92
92
92
92
92
92
27
1
68
68
57
66
73
73
57
57
62
62
62
62
62
89
89
97
97
1
78
1
57
91
91
59
91
91
82
1
86
1
69
1
75
1
46
1

result:

ok 100 numbers

Test #24:

score: 0
Accepted
time: 0ms
memory: 5608kb

input:

100 100
53 54 83 84 29 30 95 96 11 12 45 46 91 92 17 18 5 6 39 40 87 88 57 58 93 94 81 82 67 68 85 86 59 60 73 74 71 72 99 100 19 20 31 32 65 66 23 24 43 44 25 26 1 2 9 10 61 62 7 8 35 36 89 90 69 70 37 38 51 52 79 80 63 64 55 56 47 48 3 4 13 14 49 50 97 98 27 28 41 42 33 34 21 22 75 76 15 16 77 78
...

output:

97
1
39
1
80
1
27
1
25
1
7
1
79
1
60
1
63
1
84
1
60
1
27
1
78
1
33
1
44
1
41
1
90
1
69
1
94
1
99
1
92
1
59
1
59
1
87
1
83
1
63
1
82
1
94
1
25
1
91
1
83
1
50
1
77
1
71
1
46
1
89
1
18
1
36
1
51
1
14
1
48
1
76
1
7
1
42
1
57
1
17
1
68
1
98
1
52
1
49
1

result:

ok 100 numbers

Test #25:

score: 0
Accepted
time: 1ms
memory: 5612kb

input:

100 100
3 4 63 64 21 22 49 50 35 36 99 100 65 66 85 86 25 26 17 18 23 24 69 70 33 34 13 14 41 42 81 82 11 12 67 68 57 58 29 30 15 16 1 2 55 56 31 32 83 84 37 38 91 92 45 46 43 44 79 80 93 94 9 10 73 74 95 96 61 62 39 40 7 8 53 54 87 88 5 6 59 60 47 48 75 76 89 90 27 28 19 20 71 72 97 98 51 52 77 78
...

output:

7
7
7
7
7
7
10
10
10
10
46
46
99
46
89
46
77
46
100
46
92
46
82
46
46
46
59
66
99
66
100
66
66
66
83
66
66
66
65
66
95
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
99
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
100
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96
96

result:

ok 100 numbers

Test #26:

score: 0
Accepted
time: 0ms
memory: 7728kb

input:

100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1
100
1

result:

ok 100 numbers

Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #27:

score: 30
Accepted
time: 68ms
memory: 5640kb

input:

3695 3785
270 3225 1936 1747 2487 1557 2343 3313 2544 1941 1095 1919 3206 901 327 3076 557 29 112 2617 201 53 2643 678 1666 680 1523 3380 1353 2059 2566 1743 523 1131 168 509 2138 3577 109 2930 1114 3563 3395 2075 2271 1228 3462 1952 1535 1087 2548 653 2713 1749 336 1658 2470 466 958 639 3184 2451 1...

output:

3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
3694
...

result:

ok 3785 numbers

Test #28:

score: 0
Accepted
time: 75ms
memory: 7756kb

input:

3723 4095
328 2762 1127 671 588 1400 462 1610 480 2418 498 754 1996 3542 2366 1926 2523 2763 3334 1001 2644 206 3129 27 1969 2135 1957 2051 3593 627 1002 1464 436 1399 362 964 1318 3486 3367 1705 591 574 2303 1039 1157 1719 640 1749 779 2570 2322 2050 75 288 1795 2313 369 1479 1364 1543 1380 587 347...

output:

3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
3721
...

result:

ok 4095 numbers

Test #29:

score: 0
Accepted
time: 92ms
memory: 5604kb

input:

3751 4991
1413 3000 2568 849 2640 2080 2991 1124 965 897 1156 505 3393 62 2470 2855 441 1964 1102 3686 1608 1096 3152 2109 815 3301 303 2549 1265 304 1829 486 69 1460 2279 1641 1395 3669 2276 1118 3299 3480 1889 3130 2502 3288 1984 1895 2775 1044 3545 732 2333 512 3733 2511 3448 693 1344 1798 25 261...

output:

3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
3748
...

result:

ok 4991 numbers

Test #30:

score: 0
Accepted
time: 108ms
memory: 7732kb

input:

4365 4219
4170 1729 419 37 3601 3093 3961 4198 1090 2353 3745 1042 2374 1571 1280 1406 2361 4349 2275 2759 591 743 3036 2147 794 2598 1875 1058 1682 1877 3460 3678 2048 2101 2459 89 2437 3713 4307 1543 1668 3547 3600 1011 4193 2262 827 606 3990 217 283 3701 3383 3964 3052 906 1038 3764 157 1276 3690...

output:

2181
3256
3256
3982
3995
3999
4001
4001
4001
4001
4001
4001
3999
3999
3999
4001
4001
3999
3999
3999
3998
3999
3999
3999
3993
3998
3998
4001
4001
4001
3999
3999
4001
4001
4001
3995
3999
3999
3999
3999
3995
3999
3999
3999
3995
3995
3995
3998
4000
4000
4000
4000
3998
3998
3998
3998
4001
4001
4001
4001
...

result:

ok 4219 numbers

Test #31:

score: 0
Accepted
time: 120ms
memory: 5624kb

input:

4394 4906
3424 864 2175 3494 610 4297 4057 2341 1132 125 2504 1923 1080 628 2011 3599 579 2541 1652 1643 1919 2268 2668 3577 3151 4153 1658 2630 656 2458 1430 4053 463 4199 2770 1345 859 3061 2249 1023 2413 3132 1809 1978 2712 961 2593 2947 3512 2580 2247 114 1611 3291 1776 3995 3261 2270 2771 2340 ...

output:

3025
3024
3197
3166
3182
3182
3197
3198
3201
3460
3460
4000
4001
4000
4000
3996
4001
3996
3999
3999
3999
3999
3998
3998
4001
3998
3998
3998
4001
4001
4001
4001
4001
4001
4001
3999
3999
4000
4000
4000
4000
3999
3999
4000
4000
3998
4000
3998
3998
3998
3998
3998
3998
3998
3999
3999
3999
3999
3995
3995
...

result:

ok 4906 numbers

Test #32:

score: 0
Accepted
time: 145ms
memory: 7728kb

input:

5000 5000
963 4459 3471 3824 3201 1969 2194 4708 4445 3506 2258 1126 1769 4333 2746 3148 1410 762 849 3007 590 2259 477 1644 3827 4589 286 3930 2147 2436 818 1200 4218 3036 2165 1180 4050 1538 1296 2790 186 2014 1274 891 4613 3583 4714 3457 1312 888 4616 3505 577 310 1060 4397 1188 1303 1250 1226 30...

output:

2497
3197
3197
3197
3197
4206
4206
4799
4799
4799
4801
4801
4801
4801
4801
4801
4801
4801
4801
4801
4801
4801
4801
4798
4798
4799
4798
4789
4798
4798
4798
4801
4798
4798
4798
4798
4798
4798
4798
4798
4801
4801
4801
4798
4798
4799
4801
4801
4798
4798
4798
4799
4799
4799
4799
4799
4801
4801
4801
4801
...

result:

ok 5000 numbers

Test #33:

score: 0
Accepted
time: 51ms
memory: 7660kb

input:

3820 3878
843 844 1569 1570 1659 1660 3585 3586 201 202 3093 3094 1691 1692 2705 2706 1437 1438 839 840 3267 3268 521 522 2961 2962 3101 3102 3649 3650 1947 1948 229 230 1645 1646 1121 1122 2407 2408 1253 1254 1383 1384 1597 1598 3341 3342 1535 1536 897 898 441 442 1061 1062 569 570 3499 3500 585 58...

output:

1739
1
2315
2315
2315
1611
1611
1
3814
3814
3173
1
3208
1
2387
1
914
1
1872
1872
3507
3507
1480
1
3564
3722
3564
1
1874
1
2608
1
2370
2528
2528
1
2727
1
2064
1
2502
1
2773
1
3185
1
3165
1
2573
1
3680
1
3050
1
994
1457
1457
1
2186
1
2366
3163
3163
1
2960
1
1323
1
2083
1
979
1
2418
1
3634
3634
2778
1
...

result:

ok 3878 numbers

Test #34:

score: 0
Accepted
time: 88ms
memory: 5700kb

input:

5000 5000
3489 3490 2613 2614 4155 4156 1163 1164 2317 2318 375 376 3995 3996 2765 2766 4315 4316 4073 4074 3181 3182 4979 4980 3785 3786 3981 3982 1411 1412 3915 3916 1567 1568 3795 3796 3497 3498 3205 3206 3807 3808 2737 2738 539 540 3081 3082 553 554 135 136 199 200 1203 1204 2821 2822 1737 1738 ...

output:

4187
1
2219
4312
2219
1
4013
1
455
1
4738
4738
4738
4333
3279
1
2724
1
1374
1
3012
1
3377
1
928
3606
928
1
1426
1759
1759
1
4627
1
4632
1
3905
1
3038
1
3502
3502
3502
4445
4445
1
3861
4473
3861
4900
3861
1
2878
1
2538
1
4303
4303
3471
3471
2611
1
2674
1
3236
1
2337
1
1735
1
4177
4177
4177
1
4974
1
2...

result:

ok 5000 numbers

Test #35:

score: 0
Accepted
time: 46ms
memory: 5608kb

input:

3620 3786
1149 1150 2365 2366 3157 3158 3539 3540 3517 3518 1489 1490 3083 3084 1823 1824 1211 1212 2837 2838 1891 1892 2327 2328 1885 1886 2235 2236 25 26 2043 2044 2267 2268 3491 3492 1297 1298 3431 3432 3559 3560 2351 2352 223 224 1273 1274 1603 1604 743 744 1701 1702 1187 1188 1275 1276 1395 139...

output:

1536
1
2053
2053
1288
2458
2606
2606
2606
1
1786
2224
1786
1
2835
3485
2835
2835
2835
2919
2919
1
1585
1
3266
1
2333
1
3222
3222
2234
2318
2318
2318
2318
1
2027
1
517
3336
3336
1
2027
3083
2027
2027
2027
1
1085
1
2645
2645
2645
3103
3103
3103
2518
2518
1052
1
1931
1
186
2677
186
2628
186
1
3558
3558...

result:

ok 3786 numbers

Test #36:

score: 0
Accepted
time: 87ms
memory: 5748kb

input:

5000 5000
3169 3170 2479 2480 2139 2140 4305 4306 4399 4400 483 484 883 884 121 122 3339 3340 3669 3670 3763 3764 511 512 3299 3300 65 66 1293 1294 4729 4730 4607 4608 3779 3780 4549 4550 3771 3772 171 172 3365 3366 2397 2398 3221 3222 283 284 2165 2166 563 564 4249 4250 4595 4596 855 856 4287 4288 ...

output:

3531
1
2694
1
4374
1
4564
1
4085
1
4440
1
995
1
4529
1
3545
3545
3545
4867
3545
1
1268
1
2051
1
863
1
2876
1
2126
1
2988
3152
3152
1
4952
1
3355
3355
1659
4610
4610
1
1381
4296
4296
1
3075
1
4946
1
2896
2896
1510
1
3204
4126
3204
3204
3204
4861
4861
1
314
1
4117
1
3856
1
3280
1
4754
1
3363
1
4732
47...

result:

ok 5000 numbers

Test #37:

score: 0
Accepted
time: 62ms
memory: 5784kb

input:

4569 3992
843 844 4391 4392 4463 4464 4103 4104 2319 2320 3829 3830 3081 3082 2981 2982 667 668 1445 1446 3429 3430 2609 2610 4225 4226 741 742 755 756 3605 3606 579 580 1479 1480 25 26 191 192 1681 1682 2455 2456 2559 2560 467 468 525 526 1541 1542 1595 1596 1051 1052 1923 1924 2191 2192 1261 1262 ...

output:

1868
1868
2796
4085
4085
3910
3910
2796
4490
4528
4528
4528
4528
4528
4528
4312
2665
1
3985
1
1387
4113
4113
3333
1387
2291
1387
1
2071
1
4077
4077
4077
4077
4077
1599
967
1
2469
4205
2469
1
3117
3117
1789
3969
3969
3969
3969
3969
3969
3969
3969
3969
3969
3969
3969
3912
3007
1
2938
1
3522
1
1618
1
3...

result:

ok 3992 numbers

Test #38:

score: 0
Accepted
time: 83ms
memory: 5684kb

input:

5000 5000
1611 1612 2733 2734 3021 3022 2221 2222 375 376 1115 1116 1713 1714 567 568 1013 1014 2739 2740 841 842 4561 4562 2961 2962 2921 2922 1269 1270 4135 4136 3663 3664 3871 3872 1237 1238 4633 4634 2475 2476 381 382 4725 4726 2877 2878 3259 3260 4335 4336 4417 4418 3943 3944 2025 2026 1485 148...

output:

3813
3813
3813
3835
3835
4493
4493
4493
4493
4493
3813
3813
2299
1
4906
4906
3731
4893
4893
4893
4893
4893
4893
4893
4893
4893
4893
4893
4893
3824
3824
1
3749
3749
3749
3749
3960
4653
3960
3960
3749
1
1828
4250
4250
2794
1828
3464
1828
1
4698
4698
650
1
4461
4461
4461
1
1972
4117
4117
3835
4238
4238...

result:

ok 5000 numbers

Test #39:

score: 0
Accepted
time: 57ms
memory: 7656kb

input:

4077 3960
39 40 947 948 1193 1194 893 894 229 230 1571 1572 1829 1830 211 212 3 4 837 838 173 174 1819 1820 685 686 3629 3630 1185 1186 689 690 3211 3212 667 668 367 368 1759 1760 3117 3118 1803 1804 2525 2526 1497 1498 3707 3708 3817 3818 165 166 2101 2102 4043 4044 2461 2462 1733 1734 1821 1822 10...

output:

3613
3613
3773
3773
3773
3773
3773
3773
3773
3773
3773
3773
3773
3773
3773
3773
3773
1
1589
1
1466
1466
390
1
3703
3703
3703
3703
3243
3243
3419
3419
3419
4048
4048
3419
3419
3243
3830
3830
3243
1
3601
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
3715
371...

result:

ok 3960 numbers

Test #40:

score: 0
Accepted
time: 87ms
memory: 5688kb

input:

5000 5000
4471 4472 2627 2628 4695 4696 2617 2618 1159 1160 117 118 2669 2670 1455 1456 519 520 597 598 1761 1762 3631 3632 2001 2002 2639 2640 913 914 4111 4112 4517 4518 2103 2104 1307 1308 4995 4996 801 802 2013 2014 2307 2308 1391 1392 1259 1260 2333 2334 2365 2366 3885 3886 4977 4978 2997 2998 ...

output:

4194
4194
4972
4972
4972
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4978
4994
4994
4994
4994
4978
4978
4978
4978
4978
4978
4978
4978
4857
4857
4857
4857
4857
4597
4896
4896
4896
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
4795
...

result:

ok 5000 numbers

Test #41:

score: 0
Accepted
time: 47ms
memory: 5688kb

input:

3642 3651
2435 2436 2655 2656 277 278 2569 2570 925 926 2613 2614 3545 3546 915 916 3625 3626 1627 1628 1915 1916 3249 3250 2887 2888 2451 2452 405 406 1385 1386 2625 2626 2403 2404 3579 3580 2453 2454 2085 2086 649 650 2891 2892 979 980 2507 2508 3571 3572 1651 1652 2793 2794 2377 2378 643 644 2145...

output:

2030
3535
3535
3535
3535
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3628
3573
3383
3383
3383
3383
3383
3383
3383
3383
3383
3383
3476
3476
3476
3383
2922
2922
2922
2922
2922
2797
3581
...

result:

ok 3651 numbers

Test #42:

score: 0
Accepted
time: 84ms
memory: 5644kb

input:

5000 5000
1447 1448 1677 1678 2235 2236 37 38 3595 3596 625 626 835 836 3063 3064 4035 4036 3165 3166 3827 3828 1277 1278 4599 4600 1977 1978 411 412 4897 4898 3289 3290 1549 1550 4149 4150 3831 3832 2635 2636 3735 3736 1105 1106 1779 1780 2117 2118 695 696 377 378 2359 2360 1575 1576 1731 1732 1319...

output:

4827
4827
4827
4827
4827
4827
4827
4827
4827
4827
4827
4310
4453
4310
4310
4347
4310
4310
3212
3212
3008
1
2907
2907
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
4745
474...

result:

ok 5000 numbers

Test #43:

score: 0
Accepted
time: 53ms
memory: 5616kb

input:

4221 3506
533 534 1071 1072 505 506 569 570 1297 1298 2019 2020 1545 1546 3095 3096 3557 3558 2159 2160 3315 3316 1711 1712 803 804 1755 1756 2921 2922 2385 2386 3723 3724 4007 4008 447 448 3149 3150 669 670 3121 3122 235 236 1025 1026 3719 3720 709 710 385 386 1825 1826 4179 4180 4031 4032 2437 243...

output:

3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3725
3791
3791
3791
3791
3941
3941
3941
4094
4094
4094
4189
4189
4189
4189
4189
4189
4189
4189
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
4211
...

result:

ok 3506 numbers

Test #44:

score: 0
Accepted
time: 91ms
memory: 7792kb

input:

5000 5000
4195 4196 2865 2866 759 760 1939 1940 4359 4360 3335 3336 2621 2622 4283 4284 2235 2236 3829 3830 4479 4480 3273 3274 725 726 867 868 329 330 2597 2598 4817 4818 1507 1508 1845 1846 2117 2118 3449 3450 515 516 3989 3990 3733 3734 121 122 379 380 1501 1502 3739 3740 1505 1506 3639 3640 989 ...

output:

1967
1967
2815
3841
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
4945
...

result:

ok 5000 numbers

Test #45:

score: 0
Accepted
time: 87ms
memory: 5716kb

input:

5000 5000
545 546 1869 1870 143 144 1969 1970 1013 1014 2703 2704 3507 3508 2091 2092 4957 4958 2055 2056 4097 4098 1769 1770 1301 1302 1537 1538 3911 3912 2691 2692 4719 4720 105 106 1561 1562 1925 1926 1563 1564 4673 4674 2907 2908 3049 3050 725 726 1287 1288 1671 1672 2277 2278 3921 3922 4021 402...

output:

3679
1
4331
1
3599
1
1735
1
4832
1
2596
1
4350
1
3331
1
3217
1
4699
1
3493
1
3832
1
4492
1
4293
1
4142
1
3301
1
2004
1
4621
1
4317
1
3763
1
4715
1
2752
1
1569
1
4837
1
2893
1
4100
1
845
1
3123
1
4821
1
4349
1
1858
1
4927
1
4816
1
719
1
1560
1
2731
1
2450
1
3459
1
1212
1
4974
1
2346
1
4305
1
2616
1
2...

result:

ok 5000 numbers

Test #46:

score: 0
Accepted
time: 89ms
memory: 5712kb

input:

5000 5000
2393 2394 4967 4968 1659 1660 925 926 4519 4520 257 258 859 860 67 68 3677 3678 419 420 4977 4978 849 850 1483 1484 4403 4404 3349 3350 3525 3526 165 166 629 630 2597 2598 815 816 4059 4060 229 230 2927 2928 3441 3442 763 764 1549 1550 4729 4730 1393 1394 901 902 3661 3662 2065 2066 3377 3...

output:

456
456
456
456
462
469
469
469
469
469
469
469
469
469
469
469
469
469
469
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
498
...

result:

ok 5000 numbers

Test #47:

score: 0
Accepted
time: 70ms
memory: 7764kb

input:

5000 5000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1
5000
1...

result:

ok 5000 numbers

Subtask #4:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #48:

score: 0
Time Limit Exceeded

input:

92958 98464
51219 9529 5310 48981 12657 92722 17683 1969 89122 57994 77115 3985 89329 58436 62960 78863 60463 13809 76207 73216 80590 37997 64129 20857 37000 82851 34428 54499 6939 6207 23897 3322 74613 92701 34910 46456 34956 70002 9221 54471 63095 49941 8885 74051 55498 18672 17692 60440 32870 351...

output:


result: