QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212374#5409. Perotationjrjyy100 ✓1790ms5708kbC++204.6kb2023-10-13 15:24:122023-10-13 15:24:12

Judging History

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

  • [2023-10-13 15:24:12]
  • 评测
  • 测评结果:100
  • 用时:1790ms
  • 内存:5708kb
  • [2023-10-13 15:24:12]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> t;
    Fenwick(int n_ = 0) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        t.assign(n, T{});
    }
    void add(int p, const T &x) {
        for (++p; p <= n; p += p & -p) {
            t[p - 1] += x;
        }
    }
    T sum(int p) const {
        T x{};
        for (; p; p -= p & -p) {
            x += t[p - 1];
        }
        return x;
    }
    T rangeSum(int l, int r) const {
        return sum(r) - sum(l);
    }
};

constexpr int B = 1000;

struct Block {
    std::vector<int> &a, &pos, &f;
    const int l = 0, r = 0;
    int sum = 0;
    std::vector<int> val, delta;
    Block(std::vector<int> &a_, std::vector<int> &pos_, std::vector<int> &f_, int l_, int r_)
        : a{a_}, pos{pos_}, f{f_}, l{l_}, r{r_}, sum{}, val(r - l), delta(r - l) {
        std::copy(a.begin() + l, a.begin() + r, val.begin());
        std::sort(val.begin(), val.end());
        pull();
    }

    void pull() {
        sum = 0;
        for (int i = 0; i < r - l; ++i) {
            delta[i] = f[pos[val[i]]] ^ (i > 0 ? f[pos[val[i - 1]]] : 0);
            sum += delta[i];
        }
    }
    void push() {
        for (int i = 0; i < r - l; ++i) {
            f[pos[val[i]]] = delta[i] ^ (i > 0 ? f[pos[val[i - 1]]] : 0);
        }
    }

    int apply(int x) {
        int pos = std::upper_bound(val.begin(), val.end(), x) - val.begin();
        if (pos < r - l) {
            sum -= delta[pos];
            delta[pos] ^= 1;
            sum += delta[pos];
        }
        return pos & 1;
    }
    void replace(int x, int y) {
        val.erase(std::lower_bound(val.begin(), val.end(), x));
        val.insert(std::upper_bound(val.begin(), val.end(), y), y);
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        --a[i];
    }

    Fenwick<int> fen(n);
    std::vector<int> pos(n), f(n);
    for (int i = n - 1; i >= 0; --i) {
        pos[a[i]] = i;
        f[i] = fen.sum(a[i]) & 1;
        fen.add(a[i], 1);
    }

    std::vector<Block> block;
    for (int l = 0, r; l < n; l = r) {
        r = std::min(l + B, n);
        block.emplace_back(a, pos, f, l, r);
    }

    auto rangeApply = [&](int l, int r, int x, int y) {
        for (int i = l; i < r; ++i) {
            f[i] ^= (x < a[i]) ^ (y < a[i]);
        }
    };
    auto rangeQuery = [&](int l, int r, int x) {
        bool res = 0;
        for (int i = l; i < r; ++i) {
            res ^= a[i] < x;
        }
        return res;
    };
    auto modify = [&](int x, int y) {
        if (x / B == y / B) {
            block[x / B].push();

            rangeApply(x + 1, y, a[x], a[y]);
            f[x] ^= rangeQuery(x, y + 1, a[x]);
            f[y] ^= rangeQuery(x, y + 1, a[y]);

            std::swap(a[x], a[y]);
            std::swap(pos[a[x]], pos[a[y]]);
            std::swap(f[x], f[y]);

            block[x / B].pull();
        } else {
            block[x / B].push();
            block[y / B].push();

            int xr = (x / B + 1) * B, yl = y / B * B;
            rangeApply(x + 1, xr, a[x], a[y]);
            rangeApply(yl, y, a[x], a[y]);
            for (int i = x / B + 1; i < y / B; ++i) {
                f[x] ^= block[i].apply(a[x]);
                f[y] ^= block[i].apply(a[y]);
            }
            f[x] ^= rangeQuery(x, xr, a[x]) ^ rangeQuery(yl, y + 1, a[x]);
            f[y] ^= rangeQuery(x, xr, a[y]) ^ rangeQuery(yl, y + 1, a[y]);
            block[x / B].replace(a[x], a[y]);
            block[y / B].replace(a[y], a[x]);

            std::swap(a[x], a[y]);
            std::swap(pos[a[x]], pos[a[y]]);
            std::swap(f[x], f[y]);

            block[x / B].pull();
            block[y / B].pull();
        }
    };
    auto query = [&]() -> int {
        int id = (n - 1) / B;
        while (id >= 0 && block[id].sum == 0) {
            --id;
        }
        if (id == -1) {
            return 0;
        }
        block[id].push();
        int pos = std::min((id + 1) * B, n);
        while (f[pos - 1] == 0) {
            --pos;
        }
        return pos;
    };

    while (q--) {
        int x, y;
        std::cin >> x >> y;
        --x, --y;
        std::tie(x, y) = std::minmax({x, y});
        modify(x, y);
        std::cout << query() + 1 << "\n";
    }

    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 3516kb

input:

2 1
1 2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

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: 3836kb

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: 3640kb

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: 0ms
memory: 3612kb

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: 3572kb

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: 3832kb

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: 3520kb

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: 3632kb

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: 0ms
memory: 3540kb

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: 3576kb

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: 0ms
memory: 3636kb

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: 0ms
memory: 3836kb

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: 3872kb

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: 3644kb

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: 0ms
memory: 3672kb

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: 3648kb

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: 0ms
memory: 3800kb

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: 0ms
memory: 3636kb

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: 0ms
memory: 3640kb

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: 0ms
memory: 3636kb

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: 0ms
memory: 3632kb

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: 0ms
memory: 3576kb

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: 1ms
memory: 3644kb

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: 0ms
memory: 3840kb

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: 3600kb

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: 35ms
memory: 3672kb

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: 35ms
memory: 3708kb

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: 44ms
memory: 3672kb

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: 34ms
memory: 3756kb

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: 39ms
memory: 3912kb

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: 61ms
memory: 3928kb

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: 36ms
memory: 3672kb

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: 50ms
memory: 3644kb

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: 35ms
memory: 3896kb

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: 50ms
memory: 3924kb

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: 39ms
memory: 3752kb

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: 52ms
memory: 3992kb

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: 39ms
memory: 3676kb

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: 53ms
memory: 3796kb

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: 34ms
memory: 3672kb

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: 53ms
memory: 3764kb

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: 31ms
memory: 3748kb

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: 49ms
memory: 3700kb

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: 48ms
memory: 3928kb

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: 51ms
memory: 3764kb

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: 54ms
memory: 3696kb

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: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #48:

score: 40
Accepted
time: 1419ms
memory: 5456kb

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:

92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
92956
...

result:

ok 98464 numbers

Test #49:

score: 0
Accepted
time: 896ms
memory: 5540kb

input:

97091 69813
15592 46029 14102 13886 62014 21924 12623 18615 71244 52306 70498 74277 6762 57365 53762 23976 7597 51582 85674 66947 32927 77215 25502 41415 51543 3789 5006 24158 37573 37002 8030 11775 78882 87754 31943 81362 36607 87591 7978 88362 68791 89500 26644 61070 85719 95437 54105 68298 34090 ...

output:

97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
97089
...

result:

ok 69813 numbers

Test #50:

score: 0
Accepted
time: 1059ms
memory: 5556kb

input:

87115 88607
44494 39980 68378 82069 54713 5104 69906 3215 2878 65516 67694 82889 7817 41102 11689 2520 31086 66312 77203 39171 6273 30202 49285 67185 51452 38803 39782 18771 72928 44899 50765 25835 83967 38905 26422 44829 10381 58401 78623 49586 18687 11775 82919 33885 43461 81531 48069 62452 41820 ...

output:

43553
43999
43996
43996
43991
43999
56146
56144
56800
56801
56801
56801
56801
56801
56801
56801
56801
56801
56801
77882
77882
78401
78401
78401
78396
78399
78401
78401
78399
78399
78401
78401
78401
78401
78401
78401
78401
78401
78401
78399
78401
78399
78396
78401
78401
78401
78401
78401
78401
78401
...

result:

ok 88607 numbers

Test #51:

score: 0
Accepted
time: 1187ms
memory: 5448kb

input:

91248 89480
12807 5744 58168 90735 47244 22322 48950 4271 41793 49574 77527 19443 7818 2274 28416 31790 75618 67687 44929 65145 69017 27920 61167 83658 43369 74389 52775 69579 66629 15980 2218 63876 34781 60638 81256 28837 55045 64661 82883 33445 46810 24144 17881 55686 16499 4852 9275 50885 79634 3...

output:

45623
46393
46393
46394
46399
66439
66437
67162
67166
67166
67200
67200
67200
67200
67200
67200
67200
67196
67200
67200
67200
67200
78768
78755
79192
79197
79197
79199
79199
79199
79199
79199
79199
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79200
79197
...

result:

ok 89480 numbers

Test #52:

score: 0
Accepted
time: 1790ms
memory: 5588kb

input:

100000 100000
13871 29418 75258 98764 29370 41805 73990 73305 5146 12821 35824 65665 33999 92221 30794 77349 35618 57168 96853 39992 84506 5551 59918 52110 4679 31711 32633 41162 39798 14398 47844 91518 79413 23893 23752 21586 33536 15122 42973 85181 68220 17547 9012 64351 40506 94391 99581 70079 94...

output:

49998
50393
50397
67559
67559
67978
67993
67993
67993
67992
67992
67992
67992
68754
68754
68775
68801
68801
68801
68799
68799
68800
68800
68801
68801
68801
68801
68801
68801
68800
82120
82120
82396
82400
82400
82400
82400
82400
82400
82400
82400
82396
82400
82400
89123
89122
89593
89593
89593
89600
...

result:

ok 100000 numbers

Test #53:

score: 0
Accepted
time: 1043ms
memory: 5424kb

input:

93415 80710
77323 77324 50577 50578 9765 9766 42575 42576 42509 42510 17251 17252 32267 32268 46581 46582 15573 15574 12007 12008 46091 46092 75765 75766 59725 59726 38525 38526 87737 87738 12739 12740 28677 28678 10197 10198 21295 21296 65775 65776 67463 67464 10229 10230 47185 47186 24845 24846 31...

output:

72478
1
22387
44295
22387
1
47595
1
73147
1
67845
1
64898
67399
67399
85746
85746
1
75055
1
15391
1
86298
86298
52409
64743
64743
1
69464
83144
69464
1
22527
91203
91203
91203
91203
1
74373
1
71960
1
80262
1
64843
1
62822
62822
62822
1
50997
80128
80128
1
93387
93387
11060
1
55755
1
81074
81074
8107...

result:

ok 80710 numbers

Test #54:

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

input:

100000 100000
52763 52764 4539 4540 18395 18396 20339 20340 41151 41152 46245 46246 10435 10436 13953 13954 42589 42590 98683 98684 39775 39776 27073 27074 32517 32518 19793 19794 88979 88980 6133 6134 18025 18026 95547 95548 23045 23046 65387 65388 51593 51594 86585 86586 97127 97128 63985 63986 55...

output:

84330
1
69216
1
79470
79470
79470
1
66075
1
73130
96708
96708
1
99560
1
71206
71206
71206
71206
54604
1
48439
77092
77092
77092
77092
1
69404
1
19512
1
84253
1
48753
1
88755
1
48868
65802
48868
1
62687
1
90441
1
70286
1
78518
1
81665
81665
81665
1
59156
1
63928
1
26898
1
67539
1
75976
1
27702
44379
...

result:

ok 100000 numbers

Test #55:

score: 0
Accepted
time: 861ms
memory: 4936kb

input:

73904 68106
32015 32016 65633 65634 30493 30494 27075 27076 32011 32012 3711 3712 5987 5988 8667 8668 9199 9200 28775 28776 2361 2362 73137 73138 28675 28676 4915 4916 17625 17626 56439 56440 56393 56394 24959 24960 10711 10712 45809 45810 4211 4212 26667 26668 18479 18480 61305 61306 39973 39974 26...

output:

64286
64286
64286
64286
64286
1
31788
1
52293
1
53306
1
68552
70795
70795
70795
70795
1
62802
1
29551
66625
29551
52337
29551
1
70379
1
73329
1
59009
1
56958
1
68211
1
32745
71448
71448
71448
71448
71448
71448
1
73084
73084
45153
1
44306
48405
48405
48405
48405
48405
48405
54996
48405
1
49402
1
4266...

result:

ok 68106 numbers

Test #56:

score: 0
Accepted
time: 1340ms
memory: 5564kb

input:

100000 100000
37401 37402 85941 85942 3343 3344 85191 85192 79499 79500 33517 33518 19631 19632 4249 4250 84709 84710 81215 81216 35221 35222 76091 76092 66875 66876 15485 15486 51141 51142 84145 84146 95907 95908 26053 26054 8075 8076 5647 5648 2465 2466 24951 24952 77823 77824 69671 69672 91327 91...

output:

96369
96369
96369
1
69255
1
98677
98677
82580
1
39911
1
72268
1
90136
1
67629
1
39196
98383
98383
98383
98383
98383
98383
95287
65732
1
84953
84953
26049
89991
26049
75710
26049
1
49612
1
75524
1
14030
1
14532
1
30155
1
96831
96831
96831
96831
96831
96831
89425
1
64442
1
71610
1
85082
85082
87361
85...

result:

ok 100000 numbers

Test #57:

score: 0
Accepted
time: 1139ms
memory: 5556kb

input:

90543 85692
9633 9634 49569 49570 23275 23276 11847 11848 17845 17846 48723 48724 42857 42858 20513 20514 62891 62892 2715 2716 52945 52946 56521 56522 77833 77834 25583 25584 63701 63702 6383 6384 70507 70508 85999 86000 1267 1268 29943 29944 45651 45652 30507 30508 3189 3190 23039 23040 19485 1948...

output:

70978
70978
87148
87148
87148
87148
79607
70978
20069
80927
89005
89005
20069
1
51790
51790
27599
53690
53690
53690
17075
55404
17075
87365
87365
87365
87365
87365
87365
1
46105
1
78009
78009
78009
82139
82139
1
65732
1
64248
64248
64248
48080
68992
48080
48080
70420
48080
1
70751
83140
88332
88332
...

result:

ok 85692 numbers

Test #58:

score: 0
Accepted
time: 1369ms
memory: 5600kb

input:

100000 100000
78247 78248 14521 14522 87139 87140 85849 85850 97605 97606 23501 23502 12333 12334 29437 29438 66931 66932 99609 99610 15383 15384 47399 47400 98935 98936 9291 9292 50443 50444 4427 4428 58687 58688 61467 61468 86847 86848 46627 46628 97313 97314 617 618 27211 27212 74775 74776 95227 ...

output:

50442
1
83390
1
58131
58131
84701
84701
91335
91335
91335
91335
91335
84701
84701
71777
64398
1
18421
98441
98441
79470
79470
77015
77015
77015
92557
92557
45715
1
92119
92119
92119
92119
80412
1
50678
1
18529
53909
18529
1
97630
1
77325
1
74673
1
57059
1
41384
44523
41384
1
99353
99353
99353
99353
...

result:

ok 100000 numbers

Test #59:

score: 0
Accepted
time: 1165ms
memory: 5244kb

input:

81670 85428
23877 23878 7435 7436 63305 63306 79627 79628 52659 52660 63191 63192 58039 58040 35789 35790 71091 71092 38649 38650 61801 61802 31613 31614 56319 56320 45689 45690 26029 26030 6539 6540 69229 69230 77207 77208 53577 53578 31577 31578 29651 29652 20051 20052 25163 25164 27343 27344 7580...

output:

70678
70678
70678
70678
70678
70678
69613
69613
69613
69613
69613
69613
69613
69613
73996
73996
73996
69613
69613
69613
69613
69613
69613
69613
69613
69613
60164
60164
54174
54174
54174
54174
46889
46889
46889
46889
46889
46889
46889
46889
46889
46889
44777
44777
24798
1
53708
59143
66233
66233
6623...

result:

ok 85428 numbers

Test #60:

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

input:

100000 100000
35987 35988 12757 12758 90479 90480 98455 98456 30061 30062 6735 6736 211 212 9881 9882 18315 18316 23617 23618 25357 25358 83609 83610 80421 80422 67323 67324 91135 91136 64979 64980 20325 20326 92161 92162 29137 29138 39591 39592 72177 72178 93173 93174 79635 79636 33731 33732 95107 ...

output:

59837
73881
85682
94524
94524
94524
94524
94524
94524
94524
94524
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
99647
94524
94524
94524
94524
94524
...

result:

ok 100000 numbers

Test #61:

score: 0
Accepted
time: 1032ms
memory: 5392kb

input:

86579 74234
58431 58432 31313 31314 34613 34614 48865 48866 22319 22320 8967 8968 80305 80306 50999 51000 25763 25764 72851 72852 30311 30312 38923 38924 70545 70546 69071 69072 47049 47050 25323 25324 3207 3208 85887 85888 34915 34916 25061 25062 62309 62310 65441 65442 14501 14502 72853 72854 3332...

output:

56415
1
86218
1
73112
73112
73112
83809
83809
73112
73112
63255
63255
64583
69996
69996
69996
69996
69996
1
63348
63348
63348
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
86343
...

result:

ok 74234 numbers

Test #62:

score: 0
Accepted
time: 1460ms
memory: 5572kb

input:

100000 100000
72165 72166 42105 42106 24145 24146 49745 49746 54523 54524 71739 71740 46653 46654 90729 90730 11187 11188 38779 38780 7561 7562 60549 60550 49699 49700 28819 28820 69469 69470 31765 31766 43557 43558 7105 7106 73741 73742 97575 97576 60065 60066 43115 43116 9581 9582 59831 59832 3203...

output:

69185
95771
95771
95771
95771
95771
95771
95771
95771
95771
95771
95771
95771
95771
95771
90629
93824
93824
93824
93824
93824
93824
93824
93824
93824
93824
93824
93824
93824
93824
99512
99512
99512
99512
99512
99512
99512
99512
99512
99512
99512
99512
99512
99752
99752
99752
99752
99752
99752
99752
...

result:

ok 100000 numbers

Test #63:

score: 0
Accepted
time: 1295ms
memory: 5336kb

input:

82155 97485
23691 23692 79293 79294 40383 40384 47021 47022 1533 1534 75109 75110 45433 45434 37539 37540 66765 66766 43345 43346 21595 21596 77739 77740 77497 77498 52239 52240 197 198 80945 80946 10615 10616 32325 32326 47425 47426 26091 26092 10343 10344 33805 33806 39579 39580 63025 63026 22815 ...

output:

63940
68628
68628
68628
68628
68628
68628
68628
75684
75684
75684
75684
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
80201
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
81252
...

result:

ok 97485 numbers

Test #64:

score: 0
Accepted
time: 1485ms
memory: 5704kb

input:

100000 100000
66623 66624 33223 33224 26453 26454 85295 85296 12923 12924 12695 12696 21299 21300 48645 48646 30039 30040 51499 51500 19011 19012 98831 98832 75769 75770 95477 95478 3789 3790 47845 47846 96301 96302 37359 37360 5031 5032 81375 81376 973 974 75127 75128 90343 90344 27843 27844 74579 ...

output:

70028
70028
70028
96413
96413
96413
97283
97283
97283
97283
97283
97283
97283
97283
97283
97283
97283
97283
97283
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
99316
98587
98587
98587
98587
98641
98641
98641
...

result:

ok 100000 numbers

Test #65:

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

input:

100000 100000
65113 65114 68257 68258 54861 54862 76871 76872 7861 7862 71577 71578 78973 78974 34659 34660 97507 97508 35689 35690 97593 97594 77705 77706 45487 45488 51711 51712 25787 25788 48983 48984 97671 97672 7021 7022 67917 67918 12791 12792 31687 31688 22159 22160 81783 81784 75767 75768 95...

output:

42074
1
86620
1
85575
1
27135
1
87788
1
96840
1
23932
1
77372
1
52502
1
65378
1
89294
1
91882
1
57606
1
89604
1
71286
1
49697
1
76513
1
87923
1
92601
1
58341
1
78478
1
70950
1
62301
1
35077
1
61130
1
80695
1
80920
1
51989
1
38794
1
64102
1
98961
1
68461
1
75549
1
87266
1
96420
1
82295
1
93550
1
7593...

result:

ok 100000 numbers

Test #66:

score: 0
Accepted
time: 1371ms
memory: 5544kb

input:

100000 100000
97369 97370 65947 65948 81377 81378 1235 1236 57983 57984 77515 77516 88347 88348 37227 37228 31227 31228 9461 9462 83879 83880 97191 97192 45667 45668 4577 4578 1025 1026 44817 44818 41499 41500 67545 67546 94769 94770 41273 41274 59183 59184 17713 17714 31393 31394 24533 24534 53937 ...

output:

6254
6254
6663
7835
7835
7835
7835
7835
7835
8912
9372
9372
9372
9372
9372
9423
9423
9423
9423
9423
9423
9423
9423
9423
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9911
9948
9948
...

result:

ok 100000 numbers

Test #67:

score: 0
Accepted
time: 1172ms
memory: 5584kb

input:

100000 100000
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 9...

output:

100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100000
1
100...

result:

ok 100000 numbers