QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317866#6414. Classical Maximization ProblemMonaco114514AC ✓149ms37660kbC++143.8kb2024-01-29 20:47:452024-01-29 20:47:46

Judging History

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

  • [2024-01-29 20:47:46]
  • 评测
  • 测评结果:AC
  • 用时:149ms
  • 内存:37660kb
  • [2024-01-29 20:47:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using ull = unsigned long long;

bool Mbe;
#define TIME chrono::steady_clock::now().time_since_epoch().count()
#ifdef Monaco
int seed = 0;
#else
int seed = TIME;
#endif
mt19937 rnd(seed);
int rd(int l, int r) {
    return rnd() % (r - l + 1) + l;
}

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {
    x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
    return x += y, x >= mod && (x -= mod), x;
}
int ksm(int a, int b) {
    int s = 1;
    while (b) {
        if (b & 1) s = 1ll * s * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return s;
}
const int N = 2e5 + 8;
int lx[N * 2], ly[N * 2], x[N * 2], y[N * 2], dep[N * 2];
vector<pair<int, int>> E[N * 2];
bool vis[N * 2];
vector<pair<int, int>> Ans;
int n;
pair<int, int> Solve(int cur, int fa, int Edge) {
    // cout << "Solve:" << cur << " " << fa << " " << Edge << endl;
    dep[cur] = dep[fa] + 1;
    assert(Edge <= 2 * n);
    vis[cur] = true;
    int rst = 0, cnt = 0;
    for (pair<int, int> ret : E[cur]) {
        assert(ret.second > 0 && ret.second <= 2 * n);
        if (ret.first == fa) continue;
        if (dep[ret.first] > dep[cur]) continue;
        if (!vis[ret.first]) {
            pair<int, int> Tmp = Solve(ret.first, cur, ret.second);
            assert(Tmp.second <= 2 * n);
            cnt += Tmp.first;
            if (!Tmp.second) continue;
            if (rst)
                Ans.emplace_back(Tmp.second, rst), rst = 0, ++cnt;
            else
                rst = Tmp.second;
        } else {
            if (rst)
                Ans.emplace_back(ret.second, rst), rst = 0, ++cnt;
            else
                rst = ret.second;
        }
    }
    if (Edge) {
        if (rst)
            Ans.emplace_back(rst, Edge), ++cnt, rst = 0;
        else
            rst = Edge;
    }
    return make_pair(cnt, rst);
}
void solve() {
    cin >> n;
    for (int i = 1; i <= 2 * n; ++i) {
        cin >> x[i] >> y[i];
        lx[i] = x[i];
        ly[i] = y[i];
    }
    sort(lx + 1, lx + 2 * n + 1);
    int cx = unique(lx + 1, lx + 1 + 2 * n) - lx - 1;
    sort(ly + 1, ly + 2 * n + 1);
    int cy = unique(ly + 1, ly + 2 * n + 1) - ly - 1;
    for (int i = 1; i <= cx + cy; ++i) E[i].clear();
    for (int i = 1; i <= 2 * n; ++i) {
        x[i] = lower_bound(lx + 1, lx + cx + 1, x[i]) - lx;
        y[i] = lower_bound(ly + 1, ly + cy + 1, y[i]) - ly;
        assert(x[i] > 0 && x[i] <= cx);
        assert(y[i] > 0 && y[i] <= cy);
        E[x[i]].emplace_back(y[i] + cx, i);
        E[y[i] + cx].emplace_back(x[i], i);
    }
    memset(vis, false, sizeof(bool) * (cx + cy + 1));
    memset(dep, false, sizeof(int) * (cx + cy + 1));
    int cnt = 0;
    Ans.clear();
    int rst = 0;
    for (int i = 1; i <= cx + cy; ++i) {
        if (!vis[i]) {
            pair<int, int> Tmp = Solve(i, 0, 0);
            cnt += Tmp.first;
            if (!Tmp.second) continue;
            assert(Tmp.second <= 2 * n);
            if (rst)
                Ans.emplace_back(rst, Tmp.second), rst = 0;
            else
                rst = Tmp.second;
        }
    }
    cout << cnt << "\n";
    for (pair<int, int> ret : Ans) cout << ret.first << " " << ret.second << "\n";
}

bool Med;
int main() {
    fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Monaco
    FILE *IN = freopen("in.in", "r", stdin);
    FILE *OUT = freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--) solve();
    cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 19612kb

input:

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

output:

2
2 4
3 1
2
2 1
4 3
0
1 2
3 4

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 59ms
memory: 19392kb

input:

10000
2
-107276936 -310501829
419434212 585811870
-65754386 -491212232
381152038 897148193
3
-474045168 493506332
299114415 540203303
165808153 983551
-506936261 -694189769
766718170 -725540031
975267148 -593051087
1
-818952276 -762387923
584023914 -612401389
6
-77701228 -266484128
659434465 6322062...

output:

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

result:

ok ok (10000 test cases)

Test #3:

score: 0
Accepted
time: 56ms
memory: 20060kb

input:

10000
1
999855386 999580905
999342928 999615227
21
999601032 999015398
999155628 999176944
999309856 999524434
999121011 999509537
999323572 999685730
999272272 999769606
999450559 999390758
999632027 999178534
999024993 999463838
999784856 999374197
999980525 999366771
999241260 999516879
999599548...

output:

0
2 1
0
30 26
9 19
27 4
41 2
40 12
33 6
3 5
35 7
16 23
42 13
1 17
8 36
28 14
38 29
32 18
20 25
10 15
21 39
37 34
24 31
22 11
0
9 22
3 16
28 30
27 5
2 24
11 6
18 26
4 8
12 7
23 14
13 19
10 29
17 15
1 20
25 21
0
25 21
15 19
17 2
28 11
24 4
20 10
3 27
26 23
5 22
1 13
8 7
6 16
12 14
18 9
0
13 8
20 24
3 ...

result:

ok ok (10000 test cases)

Test #4:

score: 0
Accepted
time: 55ms
memory: 20516kb

input:

10000
5
999984799 999981445
999958394 999984217
999994978 999981258
999955539 999938710
999936554 999963561
999907222 999907508
999938166 999941959
999910567 999986887
999901446 999961092
999994730 999963038
5
999916115 999962400
999948250 999940355
999954204 999920844
999928148 999990369
999978118 ...

output:

0
9 6
8 5
7 4
2 1
10 3
0
10 1
8 4
2 3
9 5
6 7
0
2 5
10 4
17 3
16 11
18 8
12 22
7 13
1 9
21 19
14 6
20 15
0
5 3
2 4
6 7
8 1
0
26 20
27 14
21 4
23 11
22 9
24 3
12 31
32 10
6 30
29 18
7 15
2 19
16 25
28 1
17 13
8 5
0
7 8
2 6
3 4
9 1
10 5
0
2 11
14 1
3 15
9 13
12 5
8 10
6 7
16 4
0
47 21
67 65
66 36
60 2...

result:

ok ok (10000 test cases)

Test #5:

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

input:

10000
1
999990146 999993828
999995909 999996353
56
999999851 999991179
999997250 999997987
999990590 999997316
999997350 999996856
999997034 999996236
999999396 999996897
999991180 999993309
999991265 999995185
999993952 999994054
999990210 999994471
999993201 999995893
999997170 999998971
999998201...

output:

0
1 2
1
87 61
10 52
54 33
109 3
108 41
22 25
48 7
21 85
8 14
90 92
40 60
53 29
93 102
63 103
81 34
66 82
76 111
55 50
100 24
83 78
31 11
43 42
88 51
30 9
79 15
28 70
59 56
27 23
107 68
18 77
58 84
17 57
91 64
49 69
112 96
86 36
94 72
35 38
105 37
65 5
80 75
12 2
4 106
104 62
20 95
47 101
26 13
45 32...

result:

ok ok (10000 test cases)

Test #6:

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

input:

10000
5
999999432 999999813
999999271 999999233
999999043 999999606
999999523 999999406
999999564 999999274
999999641 999999102
999999903 999999858
999999058 999999098
999999974 999999119
999999643 999999620
5
999999370 999999738
999999181 999999907
999999163 999999783
999999393 999999086
999999661 ...

output:

0
3 8
2 1
4 5
6 10
7 9
0
10 6
3 2
9 1
4 5
7 8
0
1 3
4 2
5 6
0
9 3
6 8
4 1
5 10
2 7
1
34 32
26 20
25 14
13 2
10 9
27 8
17 5
15 4
3 11
12 19
31 30
24 18
22 28
33 29
23 7
21 1
6 16
1
8 4
12 13
2 9
14 1
7 5
15 11
10 16
6 3
0
2 3
4 1
0
1 3
2 4
1
20 34
6 47
33 36
16 48
29 28
32 30
12 38
41 8
13 11
21 23
2...

result:

ok ok (10000 test cases)

Test #7:

score: 0
Accepted
time: 56ms
memory: 20500kb

input:

10000
14
-369804569 -904204119
526374829 -824374353
-127549933 -904204119
-68608787 929413707
-68608787 -363454459
526374829 929413707
693313139 -824374353
-127549933 -726843762
526374829 -904204119
526374829 -363454459
526374829 -409731440
693313139 -726843762
693313139 929413707
-68608787 -8243743...

output:

14
19 10
28 5
25 11
26 16
23 14
13 4
18 6
20 17
24 15
9 2
22 21
27 7
12 8
3 1
20
12 21
24 13
34 9
36 25
29 27
40 30
33 15
35 26
39 22
32 7
38 4
23 17
16 5
20 6
28 10
31 8
19 3
18 1
37 14
2 11
8
12 6
9 3
14 8
13 4
10 15
11 2
7 1
16 5
1
2 1
1
2 1
34
13 11
45 34
17 14
30 12
53 50
62 59
29 8
55 43
61 57...

result:

ok ok (10000 test cases)

Test #8:

score: 0
Accepted
time: 63ms
memory: 20612kb

input:

10000
5
-536123007 813600068
870612905 -192916365
-891077277 -192916365
-169354047 -86845158
-204880568 -86845158
-909192812 -613162163
-536123007 -613162163
602684169 -613162163
-909192812 813600068
602684169 -86845158
3
-296375355 579758813
-296375355 253508589
-296375355 -927878827
267975935 -927...

output:

5
9 1
5 4
10 8
7 6
2 3
3
2 1
6 5
4 3
5
10 9
3 1
6 8
7 5
4 2
5
10 9
5 1
7 6
3 4
8 2
5
2 1
4 3
6 5
8 7
10 9
2
6 4
3 5
1 2
1
2 1
13
3 2
26 6
16 9
14 12
15 18
19 1
13 11
24 20
17 7
21 5
8 4
23 22
25 10
4
10 4
8 7
1 9
3 2
6 5
3
2 3
6 5
1 4
2
4 1
3 2
5
10 1
3 5
8 7
9 6
2 4
7
6 9
14 4
13 7
10 3
16 11
15 5
...

result:

ok ok (10000 test cases)

Test #9:

score: 0
Accepted
time: 56ms
memory: 20852kb

input:

10000
13
38708650 -400244265
805800882 -207412170
-922757982 569623504
330308285 -400244265
-922757982 193222226
330308285 -701148819
-28889088 854967427
284328781 704931219
-397379302 854967427
284328781 252366771
-699696493 -701148819
953729077 -601089169
-858131099 -701148819
-397379302 193222226...

output:

12
18 17
15 13
20 11
24 6
4 1
22 26
8 10
16 7
9 14
5 3
12 25
21 2
23 19
18
3 1
31 4
6 5
30 7
17 8
14 9
11 12
16 13
19 18
33 21
10 24
23 29
36 35
27 32
15 2
25 20
28 26
34 22
7
8 11
7 5
10 16
9 4
13 1
14 2
6 3
12 15
3
2 1
5 4
6 3
1
1 4
3 2
2
2 3
4 1
8
13 2
12 3
5 8
10 7
16 11
9 15
14 4
1 6
3
5 3
8 4
...

result:

ok ok (10000 test cases)

Test #10:

score: 0
Accepted
time: 48ms
memory: 19780kb

input:

10000
2
-254673318 743896676
326182652 743896676
115024593 743896676
989112001 743896676
1
453875458 284043499
869627863 284043499
8
-68955663 625858753
-621253434 625858753
-315653340 625858753
-85160525 625858753
-592616333 625858753
114285020 625858753
618762545 625858753
524402507 625858753
1512...

output:

2
3 2
4 1
1
2 1
8
2 1
4 3
6 5
8 7
10 9
12 11
14 13
15 16
12
3 1
5 4
7 6
9 8
11 10
13 12
15 14
17 16
19 18
21 20
23 22
24 2
8
2 1
4 3
6 5
8 7
10 9
12 11
15 13
16 14
6
2 1
4 3
6 5
9 8
11 10
12 7
13
2 1
4 3
6 5
8 7
10 9
12 11
14 13
16 15
18 17
21 19
23 22
25 24
26 20
6
2 1
5 4
7 6
9 8
11 10
12 3
1
1 2
...

result:

ok ok (10000 test cases)

Test #11:

score: 0
Accepted
time: 52ms
memory: 21164kb

input:

10000
10
-302093372 -991014187
542702243 714369751
-370626462 -991014187
-700169063 714369751
-982732066 -991014187
-763837020 -991014187
320477527 -991014187
290144737 -991014187
18975042 -991014187
-339021181 -991014187
-525462052 -991014187
290144737 714369751
-538375359 714369751
15943074 -99101...

output:

10
3 1
4 2
8 12
15 13
7 19
11 20
16 6
10 9
17 14
18 5
10
14 1
11 3
5 6
8 7
12 15
13 17
16 19
10 20
18 9
4 2
18
18 6
20 7
12 10
11 3
24 15
30 21
27 22
34 25
9 26
5 28
23 31
29 32
4 33
8 35
36 14
2 1
17 16
19 13
35
64 1
4 5
6 2
33 12
56 13
19 16
28 17
20 14
34 23
49 24
67 26
30 27
7 31
35 32
54 39
43 ...

result:

ok ok (10000 test cases)

Test #12:

score: 0
Accepted
time: 52ms
memory: 20488kb

input:

10000
5
192354975 -209258445
955055576 -209258445
286707627 -209258445
-574795734 -209258445
-305243931 -209258445
-629755833 -209258445
-337515030 -209258445
980285884 -209258445
501317910 -209258445
312382135 -209258445
24
272466007 467288536
-963587196 -778274012
240097765 -778274012
-926564605 4...

output:

5
2 1
4 3
7 5
9 8
10 6
24
27 1
8 4
11 13
12 17
30 18
6 20
21 10
40 25
42 31
46 32
22 35
36 23
24 39
29 41
14 44
47 43
9 3
7 5
16 15
26 19
33 28
37 34
45 38
48 2
30
27 1
3 5
22 6
38 7
57 11
4 14
37 18
12 21
40 23
26 24
47 28
9 29
20 30
36 31
10 32
35 33
51 39
43 13
19 44
50 45
48 46
42 49
17 53
56 54...

result:

ok ok (10000 test cases)

Test #13:

score: 0
Accepted
time: 48ms
memory: 19588kb

input:

10000
11
135813326 608040171
135813326 -96255413
135813326 -31734533
135813326 -423296887
135813326 999444876
135813326 946760362
135813326 -599331154
135813326 -441599790
135813326 233339336
135813326 -759375115
135813326 163868817
135813326 321091518
135813326 -402236877
135813326 625124369
135813...

output:

11
2 1
4 3
6 5
8 7
10 9
12 11
14 13
16 15
18 17
20 19
22 21
1
2 1
16
2 1
4 3
6 5
8 7
10 9
12 11
14 13
16 15
18 17
20 19
22 21
24 23
26 25
28 27
30 29
32 31
11
2 1
4 3
6 5
8 7
10 9
12 11
14 13
16 15
18 17
20 19
22 21
7
2 1
4 3
6 5
8 7
10 9
12 11
14 13
2
2 1
4 3
7
2 1
4 3
6 5
8 7
10 9
12 11
14 13
1
2 ...

result:

ok ok (10000 test cases)

Test #14:

score: 0
Accepted
time: 52ms
memory: 19692kb

input:

10000
19
321791336 -226466052
321791336 138757626
321791336 -613429828
944682716 -446131303
321791336 -927463006
944682716 280242351
944682716 229347131
944682716 155568891
321791336 389911916
944682716 72836839
944682716 -613429828
321791336 229347131
944682716 -927463006
944682716 138757626
321791...

output:

19
21 4
12 7
28 8
35 10
3 11
5 13
2 14
18 6
34 19
24 20
17 23
15 27
9 29
38 31
32 26
22 33
25 36
37 16
30 1
19
26 1
31 2
7 4
29 9
27 10
18 14
15 11
33 20
5 21
38 22
13 24
34 25
16 30
37 32
8 36
28 12
6 3
19 17
35 23
8
4 6
16 7
5 10
8 11
3 12
9 13
2 15
14 1
4
4 3
5 6
8 1
7 2
6
2 1
4 3
6 5
8 7
10 9
12...

result:

ok ok (10000 test cases)

Test #15:

score: 0
Accepted
time: 52ms
memory: 20616kb

input:

10000
2
414226098 -53411011
414226098 -515361565
-572270323 -515361565
-572270323 -53411011
36
660074753 623771687
-917096747 533975361
660074753 337851674
-917096747 -902052044
-917096747 846238046
660074753 197157825
660074753 533975361
660074753 626049519
-917096747 -108293477
-917096747 64055247...

output:

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

result:

ok ok (10000 test cases)

Test #16:

score: 0
Accepted
time: 58ms
memory: 20644kb

input:

10000
6
475408912 -758469962
-99052258 -758469962
-716758863 872897211
-66386054 -170278720
388817201 174925294
-776227900 -285032873
475408912 872897211
-997698204 -236300379
-716758863 -85108619
-776227900 -85108619
-716758863 -236300379
-66386054 -85108619
26
879874105 877328664
-286895493 621573...

output:

5
2 1
7 3
6 10
4 12
9 11
8 5
26
42 26
22 12
29 13
50 38
44 21
3 2
16 7
32 18
39 28
25 4
51 49
47 35
17 15
43 37
20 19
31 27
46 52
48 6
34 30
45 24
23 14
41 8
9 11
40 33
5 10
1 36
4
8 4
6 2
5 7
1 3
3
5 2
1 3
6 4
21
14 35
42 41
27 31
9 33
15 7
32 28
16 20
17 25
37 29
2 30
13 10
34 1
18 5
26 12
38 6
3 ...

result:

ok ok (10000 test cases)

Test #17:

score: 0
Accepted
time: 60ms
memory: 20460kb

input:

10000
9
-980409638 -116749812
830791554 -690170434
984923479 323045898
984923479 -116749812
-197520273 323045898
-858897130 -43820432
258471629 -979749918
258471629 -690170434
-858897130 323045898
105960247 -690170434
-197520273 -841854666
-234415044 -116749812
105960247 323045898
-358435325 -202957...

output:

8
11 5
6 9
18 16
14 15
7 8
2 10
13 3
12 4
1 17
14
10 4
6 15
32 16
26 2
14 8
28 17
30 19
22 18
11 27
13 7
34 29
9 24
25 5
31 1
21 23
12 33
20 3
11
8 2
3 16
21 4
13 9
20 11
12 22
10 5
15 7
17 1
6 19
18 14
4
7 1
4 5
6 8
2 3
9
17 12
16 22
6 18
7 1
15 2
14 4
3 5
13 8
11 20
19 10
21 9
4
8 1
6 4
2 7
5 3
13...

result:

ok ok (10000 test cases)

Test #18:

score: 0
Accepted
time: 73ms
memory: 20860kb

input:

1000
45
840710004 395646135
-851514725 100215150
-423513540 -649756636
464326407 -482837664
-179781718 755995077
492651722 -268519233
367302062 -111998374
494634876 842096727
973319201 399526783
-703731734 -989899930
758934136 -959677785
-682507454 58961947
394206800 272218663
752299573 489795348
89...

output:

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

result:

ok ok (1000 test cases)

Test #19:

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

input:

1000
113
999827252 999728856
999923862 999631025
999319008 999580013
999333375 999174260
999509073 999545469
999194399 999278837
999715162 999728030
999881205 999764413
999917667 999953211
999651496 999869003
999693536 999169883
999545275 999786246
999969774 999735073
999892216 999697498
999954099 9...

output:

0
48 92
210 18
119 24
93 88
70 226
156 139
53 109
78 113
77 82
84 35
32 101
142 66
72 102
122 172
79 43
171 59
131 46
216 130
181 30
47 95
41 225
37 111
76 126
6 34
105 147
193 29
166 121
25 62
83 65
197 175
63 164
132 94
186 115
81 155
3 58
61 38
148 4
89 191
217 104
165 135
196 85
112 16
80 20
140...

result:

ok ok (1000 test cases)

Test #20:

score: 0
Accepted
time: 65ms
memory: 20560kb

input:

1000
16
999918424 999907758
999901558 999910407
999969229 999929343
999986216 999968746
999977167 999921267
999967186 999932634
999999615 999951539
999964903 999931387
999942189 999989158
999990624 999917294
999964661 999935732
999971224 999975496
999972707 999972034
999935060 999934824
999992448 99...

output:

0
2 32
16 29
1 24
27 20
31 14
26 9
23 22
11 8
28 6
18 3
12 13
17 5
21 30
25 19
4 10
15 7
0
8 15
1 9
12 21
10 7
19 24
23 22
18 20
6 13
17 16
5 11
14 2
3 4
0
12 19
5 25
32 49
7 56
2 40
45 15
16 6
31 50
46 18
35 21
51 13
8 43
33 4
30 20
55 27
23 42
48 10
34 39
44 47
36 38
41 53
37 14
24 29
52 26
9 3
22...

result:

ok ok (1000 test cases)

Test #21:

score: 0
Accepted
time: 67ms
memory: 19604kb

input:

1000
227
999994296 999999816
999998835 999994618
999998487 999991646
999995178 999996563
999996865 999996231
999990660 999996917
999995746 999998295
999993178 999995596
999994361 999991179
999990519 999991221
999996210 999992041
999991924 999992546
999991346 999991081
999998929 999995904
999992182 9...

output:

21
177 148
166 395
208 16
44 165
114 133
215 152
254 161
344 105
442 340
192 354
9 363
321 229
163 10
122 31
226 397
121 20
392 6
182 67
206 183
125 261
242 402
145 135
372 290
210 179
365 301
339 113
342 218
417 374
202 316
409 285
353 129
118 256
277 13
62 92
422 23
323 207
60 299
441 408
349 45
1...

result:

ok ok (1000 test cases)

Test #22:

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

input:

1000
87
999999138 999999640
999999785 999999342
999999914 999999854
999999771 999999416
999999011 999999479
999999217 999999865
999999423 999999937
999999684 999999301
999999323 999999399
999999071 999999949
999999226 999999154
999999770 999999090
999999778 999999735
999999034 999999517
999999803 99...

output:

23
127 32
80 54
47 165
5 119
108 14
135 139
79 117
43 95
75 10
58 97
85 91
132 92
104 26
110 71
1 84
96 31
128 73
74 25
70 6
52 17
133 11
172 35
36 122
86 29
154 120
166 111
88 148
137 76
61 144
9 57
113 50
134 169
155 142
15 23
20 145
124 51
103 101
149 131
66 78
7 123
136 45
171 49
81 118
83 27
10...

result:

ok ok (1000 test cases)

Test #23:

score: 0
Accepted
time: 56ms
memory: 20192kb

input:

1000
154
825004796 802565417
-88001579 364640592
778546546 -57508543
283686672 -57508543
473326798 -826011553
152069566 -577222261
528378065 -577222261
-56296909 -700802856
-711386984 953035370
-711386984 -577222261
895677144 -359290436
840183000 364640592
528378065 -752921798
895677144 -577222261
8...

output:

154
52 37
39 10
84 40
43 34
82 49
178 167
53 30
108 58
164 163
89 69
102 97
56 32
67 62
77 70
124 92
139 133
76 28
48 27
114 112
211 168
216 213
245 225
277 266
295 285
301 86
99 87
129 127
215 207
231 219
242 238
272 246
306 158
177 149
198 194
250 201
304 290
141 104
170 143
193 172
217 212
278 26...

result:

ok ok (1000 test cases)

Test #24:

score: 0
Accepted
time: 69ms
memory: 19456kb

input:

1000
63
859289659 -203061342
831821977 -778714404
640602188 478366497
205686723 -232506600
831821977 -498015901
-494818974 35295117
612307834 -234198721
612307834 -495294231
-898414633 476295237
995217164 -232506600
831821977 934046031
-441937174 432603845
995217164 938111737
874550198 -309423823
87...

output:

63
41 6
36 13
117 32
83 51
59 24
103 121
11 126
113 19
81 57
60 47
50 9
97 84
95 80
39 30
28 52
98 56
123 71
86 120
27 100
93 40
118 2
45 5
43 37
61 69
111 88
89 87
35 115
72 14
106 15
110 104
124 116
90 109
122 70
79 58
26 64
77 46
91 20
66 17
105 55
29 53
67 44
101 108
102 33
49 25
82 16
92 21
34 ...

result:

ok ok (1000 test cases)

Test #25:

score: 0
Accepted
time: 61ms
memory: 20708kb

input:

1000
83
-242219535 -952757420
753940135 -13368420
-180286961 -530756654
586180284 -625675517
-437809383 472014390
-242857851 -924097244
-382920283 -625675517
-630990620 -349004314
-242219535 122507147
208821889 -495849186
-736086757 -489441806
-996984615 -974276781
-275306966 -25109596
967186464 -65...

output:

83
56 91
124 78
150 137
25 115
111 10
144 39
77 3
99 41
132 130
90 32
93 8
81 145
50 106
138 119
59 67
7 105
134 87
160 110
38 21
86 62
16 65
108 70
157 149
141 60
97 57
109 123
85 76
129 103
88 52
64 54
133 79
155 164
80 18
33 9
83 35
92 127
71 36
98 46
28 24
158 17
114 125
66 6
117 146
29 120
135 ...

result:

ok ok (1000 test cases)

Test #26:

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

input:

1000
142
-28949259 975363136
-628367037 975363136
786525293 975363136
-8339801 975363136
868048337 975363136
208733157 975363136
-724415150 975363136
213367214 975363136
-686387505 975363136
-970451747 975363136
761135553 975363136
-551594491 975363136
-925080593 975363136
-243465321 975363136
-6722...

output:

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

result:

ok ok (1000 test cases)

Test #27:

score: 0
Accepted
time: 49ms
memory: 20616kb

input:

1000
458
102600109 754726017
-66999931 951825513
-767202008 951825513
-845069119 754726017
-448344214 754726017
174342794 754726017
176530329 754726017
553731053 754726017
-69189351 754726017
-455330522 951825513
-261324017 754726017
809818684 951825513
745593756 951825513
-130095774 754726017
-2737...

output:

458
712 4
5 1
780 6
658 7
434 8
471 9
86 11
290 14
387 16
673 17
150 18
289 19
871 22
458 24
467 27
219 29
859 30
452 31
15 32
41 35
888 43
93 45
246 47
498 54
50 55
343 59
709 61
126 62
108 65
261 66
68 58
307 69
175 73
368 74
53 81
72 82
832 83
119 87
203 90
757 94
789 100
103 85
865 104
777 105
1...

result:

ok ok (1000 test cases)

Test #28:

score: 0
Accepted
time: 61ms
memory: 20256kb

input:

1000
273
638010636 -796267612
299279783 -796267612
321987052 -571635029
-388046291 -571635029
-491314021 -796267612
130988206 -571635029
32427063 -571635029
51875304 -571635029
-508530089 -796267612
269379692 -571635029
214241513 -796267612
720122947 -796267612
-678543365 -796267612
158504867 -79626...

output:

273
4 3
7 6
403 10
91 16
82 17
20 8
78 21
24 22
26 25
222 34
43 30
415 45
50 44
156 53
56 52
58 57
502 60
96 62
169 64
66 61
428 68
39 70
198 73
79 67
544 81
281 84
86 83
260 89
530 93
167 94
278 99
47 100
101 92
107 106
199 110
153 117
119 114
13 121
105 125
353 127
436 130
264 131
354 133
120 134
...

result:

ok ok (1000 test cases)

Test #29:

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

input:

1000
75
429681826 802800421
429681826 -608943566
429681826 -787858696
429681826 507047252
429681826 485971873
429681826 -346306621
429681826 -612405192
429681826 -13671560
429681826 -816374335
429681826 513226316
429681826 892335083
429681826 -352600432
429681826 -556540475
429681826 -504699273
4296...

output:

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

result:

ok ok (1000 test cases)

Test #30:

score: 0
Accepted
time: 56ms
memory: 19748kb

input:

1000
81
403001151 -229966312
-27290952 -941247950
-27290952 -872808715
403001151 -81762908
403001151 825473197
403001151 730971412
403001151 -886560490
-27290952 394200417
-27290952 808677817
-27290952 -961778274
-27290952 -245434545
403001151 318019109
-27290952 792029613
403001151 390473732
-27290...

output:

81
3 2
116 1
82 4
40 6
155 7
59 12
17 14
150 16
18 5
126 20
138 22
157 28
26 29
133 31
36 34
35 37
109 41
43 42
97 49
51 48
153 52
108 53
27 55
131 57
106 58
135 60
47 61
62 54
66 65
154 67
69 68
73 70
130 74
79 75
24 85
39 86
132 87
94 88
89 80
21 90
44 93
112 95
96 92
115 98
104 103
63 105
143 113...

result:

ok ok (1000 test cases)

Test #31:

score: 0
Accepted
time: 56ms
memory: 20544kb

input:

1000
257
-24981531 -524783010
-24981531 376842743
132542945 905111237
-24981531 -663183576
132542945 238995240
-24981531 -904084630
132542945 330336577
-24981531 -424310756
132542945 26224857
-24981531 573604180
132542945 -531956470
132542945 583434945
132542945 620552707
-24981531 -351085713
132542...

output:

257
45 3
343 5
257 7
470 9
279 12
167 13
15 11
248 22
468 23
25 20
84 28
407 34
97 35
282 36
268 38
135 39
40 29
115 42
44 41
90 46
216 49
272 51
88 52
242 53
104 56
106 58
485 61
62 57
65 64
404 66
442 68
378 74
223 75
386 76
463 78
330 81
113 82
14 83
109 85
31 86
96 87
89 77
428 92
265 99
100 94
...

result:

ok ok (1000 test cases)

Test #32:

score: 0
Accepted
time: 49ms
memory: 21644kb

input:

1000
21
541263298 571344162
-338833794 258719906
814556806 571344162
749911951 -730958945
-737751671 400747496
880311857 -204125795
-555645311 -832036787
-338833794 -832036787
582588235 -915718735
-124654808 394321598
-202932677 571344162
541263298 -975674793
880311857 -730958945
-126659351 25871990...

output:

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

result:

ok ok (1000 test cases)

Test #33:

score: 0
Accepted
time: 66ms
memory: 21600kb

input:

1000
82
620344713 761205214
564192450 -149133296
855072748 -725730286
-369866361 761205214
-126903403 123500699
521658307 -238068427
564192450 -575382074
424528213 639391487
160949070 -238068427
490683515 736060786
-861287945 -430077137
92203881 -414548921
-228263452 -161807552
-739623881 619906932
...

output:

79
76 16
69 39
131 142
109 5
106 19
148 12
161 90
15 50
33 160
129 78
49 34
25 27
127 44
155 71
147 46
10 158
130 17
55 23
91 13
121 51
122 68
40 3
9 6
134 104
83 85
94 89
128 37
73 112
120 98
114 159
7 2
139 118
22 28
99 144
125 63
150 97
32 117
124 41
119 11
87 77
136 135
133 58
116 65
101 93
96 2...

result:

ok ok (1000 test cases)

Test #34:

score: 0
Accepted
time: 81ms
memory: 21248kb

input:

100
715
-716037174 449787280
-179603495 267807227
-85847745 -339745287
531498593 906672966
-65182647 -249655497
196101865 -917254384
569704541 175181937
408949063 -60772621
-471098833 -180592225
452882519 -173474204
518554869 504642822
-610596606 -43048739
-173418328 49620755
-490214353 129314297
-8...

output:

0
571 1338
1023 1051
1301 942
96 114
1333 783
671 806
614 372
1116 77
1080 1008
494 670
1226 810
425 1046
776 795
1384 1197
413 1262
121 752
605 445
136 856
974 962
1401 1124
1315 254
1183 1061
40 1113
845 652
1367 818
589 1377
720 232
75 557
250 519
242 677
226 16
1246 251
363 582
1218 1409
893 564...

result:

ok ok (100 test cases)

Test #35:

score: 0
Accepted
time: 81ms
memory: 21376kb

input:

100
1180
999939181 999607824
999877463 999501538
999725395 999197028
999578614 999669422
999691207 999388141
999798382 999350154
999515140 999686861
999804739 999722876
999059909 999779016
999988075 999795096
999394228 999790648
999357316 999130743
999834412 999146926
999533794 999419507
999164265 9...

output:

2
1174 956
294 1956
1451 251
1824 1864
1493 872
2036 2178
1010 846
2209 1618
912 418
96 473
520 890
180 1137
323 791
849 1059
1173 722
1126 733
1990 389
775 1428
475 1796
2127 1761
1670 1462
1905 1516
22 624
1742 500
1112 1534
2148 1192
2269 1113
734 511
2064 772
2129 831
1483 1746
1872 373
1361 115...

result:

ok ok (100 test cases)

Test #36:

score: 0
Accepted
time: 78ms
memory: 20876kb

input:

100
10
999949463 999921247
999942779 999933524
999900374 999919960
999913527 999977190
999963539 999919222
999986393 999982382
999960627 999912715
999955900 999934316
999962876 999904282
999944172 999923360
999974177 999993968
999960412 999941887
999902083 999920318
999906832 999942948
999934454 999...

output:

0
3 13
14 4
18 19
15 17
2 10
1 20
8 12
7 9
5 11
6 16
0
55 1
113 52
39 124
56 236
38 146
104 3
130 191
6 10
27 111
101 33
2 15
109 75
244 144
167 199
241 108
4 20
174 148
165 110
70 131
182 67
240 197
125 209
138 218
133 45
81 219
243 64
93 224
173 50
186 134
44 46
163 121
122 159
168 89
77 170
214 1...

result:

ok ok (100 test cases)

Test #37:

score: 0
Accepted
time: 71ms
memory: 20072kb

input:

100
2795
999995625 999994422
999997406 999998890
999996073 999998910
999996365 999992345
999992211 999999534
999990826 999998894
999990827 999999648
999991569 999997094
999997323 999994792
999990812 999994722
999994392 999998879
999994441 999990381
999992051 999993298
999997822 999994423
999998285 9...

output:

1710
2563 926
2540 78
611 3970
4669 1569
1970 530
4736 2866
4891 2589
5338 1024
5449 4497
3056 2582
851 3839
351 51
3380 5194
2356 4777
4263 1974
2538 4787
3834 2709
4231 2149
1959 588
158 1607
3344 1648
4652 4617
3887 700
1632 879
1159 294
4795 36
1614 3252
2089 3987
4316 1870
1712 3532
520 708
341...

result:

ok ok (100 test cases)

Test #38:

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

input:

100
1005
999999258 999999564
999999716 999999506
999999057 999999959
999999274 999999385
999999562 999999714
999999749 999999926
999999159 999999330
999999060 999999408
999999218 999999582
999999097 999999761
999999853 999999231
999999424 999999841
999999744 999999186
999999400 999999073
999999445 9...

output:

985
1837 185
1645 112
719 303
1287 102
971 529
516 1636
286 930
1103 1120
264 324
632 427
727 240
702 64
1830 564
531 694
660 651
1846 735
1537 482
771 131
1441 414
1127 650
497 1434
1530 1021
1921 1060
222 52
1812 273
1767 115
1202 957
141 454
368 150
1608 899
224 223
1470 122
1660 942
315 327
1209...

result:

ok ok (100 test cases)

Test #39:

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

input:

100
174
-958876330 -846470800
-796741809 -131152725
574295122 764287642
-958876330 -825762193
185468313 -971066749
-287559769 764287642
-904746093 -825762193
-438778854 -825762193
5267152 609322023
185468313 77515090
185468313 -131152725
-287559769 247199580
-491475497 260165013
719679418 -179087066...

output:

174
89 31
25 10
48 47
132 127
156 134
18 12
49 42
76 75
128 112
69 67
96 87
142 121
181 169
213 184
63 59
68 64
123 109
148 130
54 21
160 104
166 164
220 196
228 224
290 269
299 294
317 307
339 158
231 230
247 234
291 278
312 301
319 221
272 252
296 279
323 297
330 40
41 30
78 65
137 102
188 186
266...

result:

ok ok (100 test cases)

Test #40:

score: 0
Accepted
time: 66ms
memory: 21244kb

input:

100
454
292487349 -708917766
-446575764 -920302303
373857024 -525302786
236159958 -877034512
240035307 -28559828
-156425976 29793081
-683968223 -28559828
658545653 -892201965
-485118423 -349005511
-677465608 102959577
-241309351 -615266668
-857580103 -877034512
590882873 69859569
-961101806 -2385646...

output:

454
214 36
294 34
559 197
60 49
206 20
50 21
289 145
616 139
161 148
180 45
386 231
691 31
860 815
598 103
25 117
756 174
807 183
453 185
317 79
659 121
569 11
749 219
779 186
170 142
804 16
605 345
86 26
449 336
523 105
334 147
227 108
87 143
299 6
586 43
359 94
539 80
790 780
282 151
427 380
788 5...

result:

ok ok (100 test cases)

Test #41:

score: 0
Accepted
time: 81ms
memory: 22164kb

input:

100
140
229220674 878836488
-506767178 293730975
960642833 878836488
485659386 878836488
-225376185 16183205
-322465048 -460955536
-635701181 878836488
-578723152 374559636
956924322 878836488
-666563369 -550449367
-240963901 374559636
9519098 374559636
404598294 16183205
-188062738 467646265
937074...

output:

140
80 71
115 19
100 28
218 5
105 104
26 13
43 3
107 16
158 132
173 166
246 208
181 22
44 21
15 47
120 84
86 82
123 91
60 4
147 73
112 111
45 31
220 62
231 134
164 46
241 139
169 53
257 184
148 124
108 54
162 116
261 50
159 152
130 39
201 150
214 210
228 56
265 176
38 36
204 177
215 155
247 180
183 ...

result:

ok ok (100 test cases)

Test #42:

score: 0
Accepted
time: 54ms
memory: 23116kb

input:

100
453
-9728842 -879506383
723264369 -879506383
-617602947 -879506383
-883543546 -879506383
-365459776 -879506383
259863014 -879506383
-229024413 -879506383
-357634378 -879506383
45613473 -879506383
897413515 -879506383
142722904 -879506383
308356916 -879506383
-528467703 -879506383
45803942 -87950...

output:

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

result:

ok ok (100 test cases)

Test #43:

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

input:

100
1681
-648014211 -216027092
-372352298 95789050
-678908480 95789050
-382412165 95789050
214922606 95789050
45021991 95789050
131451784 95789050
926607022 -216027092
-500711391 95789050
527775426 -216027092
860331657 95789050
-255764825 95789050
314154093 -216027092
-631103238 95789050
292792358 9...

output:

1681
3 2
8 1
1417 10
233 13
1188 16
20 17
125 24
27 23
3163 29
413 35
38 36
466 42
3177 43
51 45
55 53
58 57
2156 62
2747 64
66 63
2824 70
576 71
72 67
749 76
78 73
1776 83
26 84
1430 85
2787 86
1832 89
92 91
1434 96
101 98
1759 105
1302 109
112 106
93 115
569 117
118 114
2543 119
122 121
1948 124
2...

result:

ok ok (100 test cases)

Test #44:

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

input:

100
476
218894313 -685169320
967098661 -16626457
-797375436 -16626457
955557493 -16626457
54133572 -16626457
-722192690 -16626457
791557373 -16626457
-208166285 -685169320
185917393 -16626457
-338707386 -16626457
49911294 -16626457
-359502368 -685169320
-359176146 -685169320
430103061 -16626457
-744...

output:

476
754 2
114 3
728 4
71 5
141 6
188 9
641 10
11 7
432 14
423 15
33 16
506 17
406 21
280 24
783 28
68 29
34 27
20 36
37 35
614 42
131 43
275 44
470 45
842 46
548 47
30 48
710 50
918 51
925 52
481 55
607 59
603 60
333 61
400 62
670 63
439 64
176 67
69 41
349 70
922 73
822 76
211 79
315 83
300 85
861 ...

result:

ok ok (100 test cases)

Test #45:

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

input:

100
1281
-7127937 -551225280
-7127937 -63829747
-7127937 50255920
-7127937 685959203
-7127937 -474730627
-7127937 205475943
-7127937 894868084
-7127937 -262984557
-7127937 858324856
-7127937 257534742
-7127937 -640954010
-7127937 -111367493
-7127937 892100661
-7127937 696606550
-7127937 136498536
-7...

output:

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

result:

ok ok (100 test cases)

Test #46:

score: 0
Accepted
time: 64ms
memory: 20840kb

input:

100
2300
930979038 -865442548
56354538 569246647
930979038 209346563
930979038 -402151796
56354538 9788037
930979038 349210639
930979038 113353815
56354538 -508882748
56354538 -390359400
930979038 881411592
56354538 328521324
56354538 569030395
56354538 749112678
930979038 -492654973
930979038 -5806...

output:

2300
3485 1
1472 3
4187 4
229 6
1777 7
14 10
1005 15
17 16
4208 19
2914 20
326 24
25 21
402 30
33 31
4518 36
39 35
2308 45
302 46
1183 51
2724 52
54 44
56 55
2300 57
1964 58
4554 67
68 59
1288 69
75 73
856 77
4045 79
81 80
4406 82
3923 84
1762 86
4425 89
91 90
2699 92
1916 93
664 98
3065 99
2298 102...

result:

ok ok (100 test cases)

Test #47:

score: 0
Accepted
time: 65ms
memory: 19616kb

input:

100
393
484804995 -671233294
484804995 45381500
-343734967 483744892
-343734967 -678278044
-343734967 430018594
484804995 -536133521
-343734967 972761171
-343734967 188883545
484804995 291634094
484804995 161326893
484804995 43447237
-343734967 81642646
-343734967 905579532
484804995 -838456546
4848...

output:

393
351 1
509 2
219 6
232 9
384 10
206 14
76 15
586 17
349 18
104 19
67 20
34 21
496 22
679 23
357 26
27 11
643 28
99 30
63 31
182 37
362 38
41 35
647 45
684 50
383 51
405 52
406 54
79 55
267 56
277 57
241 58
264 60
766 62
409 65
66 59
479 69
657 71
157 73
411 74
748 80
103 81
641 82
338 87
44 89
68...

result:

ok ok (100 test cases)

Test #48:

score: 0
Accepted
time: 59ms
memory: 23088kb

input:

100
2245
257511569 -570888823
-409065975 834451934
972932318 -206332685
-220073979 -895107571
819486773 -206332685
819823298 -570888823
116295608 282026121
589205449 -895107571
-54658019 -895107571
987042524 -206332685
-196884689 282026121
-940822451 993058719
402874649 -895107571
633334868 99305871...

output:

2245
48 4
1122 1
4327 29
2215 1046
1402 453
1789 14
1939 24
1544 565
1578 40
3357 3106
47 12
934 194
3955 63
2539 1477
2995 70
4039 3423
1977 1885
4360 77
3208 1398
4089 82
2238 521
83 74
2673 1717
3804 84
2203 1795
2338 94
1901 112
546 153
3139 1211
4240 143
2789 2450
180 149
3807 2732
857 260
3205...

result:

ok ok (100 test cases)

Test #49:

score: 0
Accepted
time: 68ms
memory: 23092kb

input:

100
116
-28349829 -267772969
-181233169 605639981
-221792554 885875755
-8847461 376377302
-527881168 376377302
-794286947 885875755
-442516480 365428090
60367949 59687335
844852200 -267772969
70152464 -267772969
-326579976 59687335
-382146420 885875755
-305012413 376377302
-255659827 495623398
84485...

output:

116
95 8
156 11
151 14
196 51
30 56
121 72
128 75
194 103
226 225
183 115
64 39
90 86
200 186
77 66
132 110
134 80
73 20
129 139
184 148
195 157
161 144
143 169
214 174
117 177
199 193
205 173
71 49
88 28
112 99
208 207
125 74
180 221
230 212
130 7
166 96
46 24
114 61
19 78
154 109
135 131
206 165
1...

result:

ok ok (100 test cases)

Test #50:

score: 0
Accepted
time: 102ms
memory: 22964kb

input:

10
10568
266619539 928993099
644537002 -163339024
-965315605 131093436
-873401839 -319727236
-682029920 -699502948
-857838819 -528950378
126750467 -72275669
623580094 410832833
287731394 -865265684
-71034303 515678565
-897514612 929674238
-794392375 895647772
811715826 600060479
640892543 -557248887...

output:

0
880 17160
9453 20942
17567 14653
2168 1355
2104 3943
9161 334
18251 13351
14455 14578
13413 19906
665 2681
19082 5797
8990 7714
12759 10478
19093 16656
14427 13111
10387 4670
21058 14174
2959 17148
13358 4791
4923 14565
16270 2065
3795 6732
15705 2889
10658 9606
10700 14999
13722 16826
10483 8732
...

result:

ok ok (10 test cases)

Test #51:

score: 0
Accepted
time: 101ms
memory: 24464kb

input:

10
983
999595593 999481588
999941833 999204986
999676040 999115470
999653065 999524261
999950018 999574889
999911879 999942071
999134864 999155033
999133604 999956453
999424191 999531479
999169859 999553795
999163364 999608732
999486991 999180185
999600255 999690901
999278724 999959357
999886640 999...

output:

2
903 935
62 345
1868 559
48 1449
1432 850
38 201
158 571
1131 788
1738 680
396 363
1519 44
795 1597
453 344
1616 526
731 798
603 306
1920 1663
429 1820
362 459
688 1162
254 1141
87 536
489 1194
193 31
1382 919
1423 1221
1772 475
1040 1639
1864 1189
1461 216
1834 587
801 1513
784 1892
169 888
1799 9...

result:

ok ok (10 test cases)

Test #52:

score: 0
Accepted
time: 95ms
memory: 22916kb

input:

10
15236
999975325 999978324
999983228 999957461
999965056 999943264
999953829 999920806
999913911 999975263
999949326 999952997
999948654 999968342
999957007 999987426
999900723 999909965
999944389 999907733
999911075 999973513
999997298 999931066
999983079 999918568
999946266 999969557
999900152 9...

output:

6279
12245 21809
2368 30312
30122 27410
323 15845
16648 25082
4930 2985
6716 172
23451 11875
16924 26552
14499 7930
14142 4067
23494 22065
28130 9879
6571 5413
8918 22110
20990 22535
21295 26342
13147 443
24289 19369
19204 7679
29713 20476
2120 16564
7503 5512
7394 410
19556 5706
4907 28175
13196 38...

result:

ok ok (10 test cases)

Test #53:

score: 0
Accepted
time: 99ms
memory: 23200kb

input:

10
6642
999992808 999996636
999995238 999998603
999990460 999998357
999992495 999998027
999994992 999993315
999990663 999999307
999994510 999991024
999994319 999993024
999996312 999990447
999990590 999994561
999997748 999994786
999990918 999993436
999994457 999993851
999994234 999991647
999996595 99...

output:

6031
8370 2276
6444 3816
3107 1505
6262 6207
91 11461
264 824
5887 8507
2271 1146
6030 2089
7852 7301
7178 7808
10969 5197
11671 6556
9412 5095
8974 607
7245 9485
12704 2200
9304 4680
2482 1981
10728 10278
12613 4881
4753 6550
5206 9982
8775 8717
11561 3846
13236 1451
2869 4080
7375 1308
749 6961
27...

result:

ok ok (10 test cases)

Test #54:

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

input:

10
19516
999999707 999999837
999999488 999999818
999999509 999999591
999999991 999999026
999999356 999999726
999999489 999999193
999999038 999999298
999999881 999999157
999999344 999999162
999999160 999999113
999999139 999999582
999999470 999999327
999999742 999999921
999999255 999999737
999999216 9...

output:

19516
1614 1038
5454 3045
3418 815
3024 2698
2869 804
3006 2554
3932 3351
1009 713
4883 2634
9755 9327
2886 1555
4983 3021
2483 1412
2686 2675
1926 313
3955 704
5448 665
6492 2002
3444 1258
2685 2402
1952 1747
2873 2786
1460 1197
5765 2161
4756 3878
3943 3025
9706 5335
4944 1503
1397 1068
3354 3181
...

result:

ok ok (10 test cases)

Test #55:

score: 0
Accepted
time: 68ms
memory: 21368kb

input:

10
14948
-170688734 833794743
949001579 224632065
-887648481 346146784
994218765 -808897932
948269970 764123696
24957273 562441566
-170688734 843621240
959643634 -354951661
631351081 -86364881
-9691567 824383620
-935916525 352437858
381851425 387057559
-6239193 951794229
450798340 -742525732
-394344...

output:

14948
475 40
863 393
388 78
366 279
1227 568
771 698
371 221
280 226
349 58
592 515
1134 914
536 501
921 844
888 169
297 146
334 325
260 248
583 529
253 178
428 422
164 123
690 202
799 727
734 278
289 174
396 374
632 520
999 463
1280 1231
591 398
746 367
656 542
1536 1113
1759 1630
2071 1878
2512 21...

result:

ok ok (10 test cases)

Test #56:

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

input:

10
18275
46937162 -785699925
-512599977 -861792903
-732947245 771605479
-317815822 369273432
-478775873 211331712
-678678382 -401598442
-366699505 752973691
776710779 -7216385
-88306688 -190102574
328516250 -317225669
522217639 215990988
523904534 -256490677
540608168 493241721
620782210 -185524925
...

output:

18275
1997 255
1560 1196
4045 2517
1043 736
1906 1122
2099 1566
1704 523
1426 958
2589 2457
3620 2617
1001 567
651 457
4925 1453
7199 4997
10184 7850
1462 357
1730 1413
1565 1251
3012 868
2122 1932
2790 1894
842 788
1181 650
687 531
2904 2474
2831 1664
595 468
1176 676
2502 1993
1773 979
4596 4249
2...

result:

ok ok (10 test cases)

Test #57:

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

input:

10
390
-347835130 869197644
963535733 392603688
671237510 92351133
671237510 -703861232
671237510 423461538
671237510 369343656
671237510 980877320
-347835130 456099182
671237510 -311676199
-347835130 -886266831
-347835130 -257100015
-347835130 -637839633
963535733 -16989823
963535733 -821875052
963...

output:

390
639 412
269 38
13 2
670 14
742 481
268 191
18 15
479 62
570 422
21 19
566 289
761 330
28 27
730 413
333 33
436 238
35 31
662 293
319 102
39 36
717 701
550 41
445 329
50 40
290 56
758 582
750 170
59 57
741 448
629 66
584 68
540 463
69 64
714 636
261 78
486 79
748 525
83 73
470 81
477 227
93 89
43...

result:

ok ok (10 test cases)

Test #58:

score: 0
Accepted
time: 68ms
memory: 23376kb

input:

10
1285
637213737 -900998147
-356659628 -900998147
950244610 -900998147
-182671545 -900998147
-708950884 -900998147
-973866581 -900998147
-190878205 -900998147
135731649 -900998147
-125331609 -900998147
521939981 -900998147
976257311 -900998147
818237327 -900998147
705563706 -900998147
58565785 -900...

output:

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

result:

ok ok (10 test cases)

Test #59:

score: 0
Accepted
time: 76ms
memory: 23124kb

input:

10
5000
-188767223 -315528788
-987365245 -315528788
-106387689 135511984
127392808 -315528788
800721151 -315528788
146952905 -315528788
-323702728 135511984
411611172 135511984
872064533 -315528788
-40050336 135511984
119702024 135511984
-208480603 -315528788
679048782 -315528788
402900711 -31552878...

output:

5000
3727 7
5884 8
4275 10
5954 11
2758 16
136 17
3353 18
7177 21
22 3
796 23
9314 25
5648 26
139 27
8232 28
1284 30
1049 32
4245 35
1850 37
1515 38
39 36
5937 41
6193 44
8999 45
4361 49
6634 50
51 42
8929 56
4884 57
58 55
9881 59
4871 61
1013 63
9346 65
8355 68
7168 71
3297 75
2425 76
9131 77
4537 ...

result:

ok ok (10 test cases)

Test #60:

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

input:

10
5892
25327490 -567979409
-735380777 -567979409
362509197 -518667355
380762791 -518667355
-325207607 -518667355
541910006 -518667355
36310841 -567979409
-726943590 -518667355
513235902 -518667355
289283655 -518667355
290421813 -567979409
892523351 -567979409
-894087744 -567979409
621832318 -567979...

output:

5892
7407 1
2821 7
11 2
4804 12
11638 13
15 14
1176 17
26 21
2822 27
1228 28
1188 29
1473 30
35 32
6144 38
8413 41
3704 42
43 37
5556 48
50 46
10984 52
3538 54
3084 55
2750 57
59 51
64 62
10463 66
416 70
1901 73
6600 74
84 72
4747 88
1094 90
4767 91
9771 94
95 93
7070 97
1274 98
1788 101
10466 104
7...

result:

ok ok (10 test cases)

Test #61:

score: 0
Accepted
time: 65ms
memory: 22736kb

input:

10
7074
241731848 530211859
241731848 -112101076
241731848 -387299272
241731848 840407166
241731848 -519364921
241731848 -927667636
241731848 -12750799
241731848 446782229
241731848 -605995785
241731848 -360804301
241731848 -706630766
241731848 95158934
241731848 -937680624
241731848 162324777
24173...

output:

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

result:

ok ok (10 test cases)

Test #62:

score: 0
Accepted
time: 68ms
memory: 22176kb

input:

10
729
867500722 -983664796
867500722 -428285695
-323742684 -171458916
-323742684 440597108
867500722 878319625
867500722 225023835
-323742684 -291982426
-323742684 568294497
867500722 327920686
867500722 -477580489
-323742684 310693081
-323742684 775098797
867500722 -334572408
-323742684 181766129
...

output:

729
1098 1
1036 2
542 5
20 6
268 9
1043 10
110 17
1390 18
326 19
864 22
304 24
1328 25
875 27
1377 29
30 13
1384 31
824 32
786 33
897 34
978 35
240 39
286 40
1172 41
1343 43
1332 44
534 47
253 49
359 51
934 52
972 53
21 54
1138 55
1426 59
815 62
1064 63
703 65
720 66
1013 67
226 68
422 69
60 72
464 ...

result:

ok ok (10 test cases)

Test #63:

score: 0
Accepted
time: 67ms
memory: 21956kb

input:

10
23890
-966926807 -783294985
-966926807 -231086723
-966926807 -827425532
-966926807 951590873
-966926807 -847083727
-322954521 -903547355
-966926807 395823002
-322954521 113620163
-966926807 442076584
-322954521 -358356830
-966926807 -416611206
-966926807 308206261
-322954521 -548371038
-966926807...

output:

23890
20642 8
20588 10
13 6
7766 18
7181 19
31740 21
32364 23
26 15
12062 29
33 31
18344 35
22052 45
32496 49
12026 51
7987 52
34443 54
36999 55
3930 56
22322 59
28745 60
11958 65
70 44
34185 71
37782 77
15889 80
33338 83
39276 86
4774 87
35030 89
34986 95
24048 96
5647 97
7879 101
17701 105
46987 1...

result:

ok ok (10 test cases)

Test #64:

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

input:

10
6461
164403694 719871079
-178686855 -505252945
820168812 419207217
-229478200 77799158
677361796 77799158
575661006 419207217
-697613489 -329650846
-362539459 -563403377
727778010 -563403377
-111787135 419207217
892586613 -329650846
664142990 435882783
-746057528 435882783
-484808272 -329650846
-...

output:

6461
4518 3
5005 1315
12020 11269
12502 7
1021 613
7374 14
11230 19
5770 21
6178 4900
37 11
3888 2596
4921 52
5738 520
9664 70
72 39
7884 75
9584 89
9660 9427
10682 94
5851 243
12442 103
7932 4985
6334 119
128 104
3405 1373
7888 1533
8414 132
11922 136
7708 215
139 131
6392 5121
10445 10317
150 141
...

result:

ok ok (10 test cases)

Test #65:

score: 0
Accepted
time: 72ms
memory: 23332kb

input:

10
14956
895706895 998300226
820538240 306140296
-445632195 597312604
-409959410 597312604
755346555 251251450
259123019 -176732314
701825202 -694016428
520061157 306140296
626248236 -236060915
321824154 -762678310
714689875 444441588
-774797456 597312604
4205823 306140296
104689711 -236060915
-9484...

output:

14956
1753 1330
9038 4551
14224 10015
18218 15156
4066 1979
7363 7232
8697 8125
1998 723
7932 2407
12260 10279
15372 12368
23779 23360
23986 5
5568 3386
9742 5852
17790 13472
23955 19200
27317 24295
13015 478
18104 14544
18738 18147
23188 18848
26047 25646
28343 30
2737 1300
11889 3930
16480 12242
1...

result:

ok ok (10 test cases)

Test #66:

score: 0
Accepted
time: 144ms
memory: 34012kb

input:

1
100000
70720045 -382955525
180416482 414551370
-321808609 -148240525
-959621209 239890090
279590168 239445206
-672414454 -968764851
978907902 855176899
-927586531 -493246847
-87140549 -239161862
394302217 -390243883
747094712 472952985
437187652 834551586
-394349288 431373156
954522299 545636033
-...

output:

23
142651 56682
60906 128366
177956 144242
195725 78760
195105 85843
103173 179725
151801 196676
189027 136206
10956 167240
190102 88936
127502 192318
171804 169985
53661 183482
148017 81864
103145 135633
8742 63912
78882 125537
26978 48772
164407 5307
62458 26167
195667 5430
168377 41900
144989 289...

result:

ok ok (1 test case)

Test #67:

score: 0
Accepted
time: 143ms
memory: 32936kb

input:

1
100000
999264440 999048423
999943779 999924927
999580357 999266886
999189670 999239640
999169156 999823062
999940080 999293014
999369020 999661305
999189323 999146694
999183801 999589407
999918625 999551090
999402308 999679213
999139826 999423045
999933104 999726376
999862333 999034393
999325582 9...

output:

30281
55325 96228
178475 191468
106003 197741
30975 138073
196465 114440
130183 21205
63279 190168
116391 35971
190032 131210
102771 47813
95072 8708
196792 102258
139621 72193
16926 118296
186506 163785
183876 10251
121960 63039
179740 152060
127251 149117
23328 43268
30258 74515
54270 167754
12482...

result:

ok ok (1 test case)

Test #68:

score: 0
Accepted
time: 129ms
memory: 34360kb

input:

1
100000
999975273 999973662
999943883 999925191
999951597 999989446
999981472 999903478
999927188 999993354
999922765 999970341
999935838 999925520
999910876 999943291
999965140 999987674
999960397 999922095
999924484 999966851
999904125 999916521
999937262 999938937
999920433 999985453
999952260 9...

output:

97922
76495 89920
20843 64943
158771 23237
102301 2950
107680 9718
10387 6029
77168 2145
122131 82903
176216 153224
119627 26981
101605 5917
142953 56273
167121 102847
180088 22806
147828 124272
50245 7387
85338 36122
762 47989
40225 91451
67769 47821
159476 87297
55437 4329
187987 41461
99489 12187...

result:

ok ok (1 test case)

Test #69:

score: 0
Accepted
time: 95ms
memory: 28632kb

input:

1
100000
999995621 999999670
999999969 999993086
999991515 999996627
999998034 999997733
999990010 999990951
999994345 999999518
999995768 999995576
999990755 999995308
999994356 999993294
999999258 999992963
999991118 999997972
999996805 999995493
999996557 999999418
999998617 999990595
999992992 9...

output:

100000
5776 2776
14090 13451
42050 22322
52695 19020
5163 2771
50440 8760
14439 11146
42830 14465
38802 12937
23533 23290
8012 5178
55359 7046
50908 18492
34070 14951
32713 2029
27728 15474
15975 11738
70981 59993
36417 26929
39606 30606
33249 21377
16395 13554
67341 62436
105790 69311
52908 26107
6...

result:

ok ok (1 test case)

Test #70:

score: 0
Accepted
time: 76ms
memory: 25752kb

input:

1
100000
999999356 999999100
999999557 999999477
999999247 999999556
999999478 999999687
999999801 999999758
999999391 999999967
999999895 999999528
999999030 999999011
999999914 999999760
999999637 999999704
999999672 999999060
999999035 999999996
999999846 999999054
999999166 999999583
999999765 9...

output:

100000
1954 1914
5373 2297
3990 3441
6192 6056
1844 1550
5981 2908
1238 736
2529 1021
3121 688
6686 3392
3246 1007
2965 213
3011 574
1838 164
5282 4456
1794 765
2433 324
4355 1699
1008 313
4344 2332
676 528
3648 3593
2336 1694
2901 1176
909 636
4961 1730
3255 1917
3363 2049
582 578
2427 1509
3040 25...

result:

ok ok (1 test case)

Test #71:

score: 0
Accepted
time: 66ms
memory: 25264kb

input:

1
100000
-547614182 905649186
-730348421 219289192
-138779779 -601726529
637290947 785577159
582877718 711339300
-747547194 -798832505
156167189 928036875
718258793 236208965
357417172 -293383985
383912089 713166152
233364698 -834647510
33321838 -637401353
-524918636 -271511728
-93689863 14541656
65...

output:

100000
2931 2327
612 479
1603 737
686 486
1421 329
986 824
2286 1792
2818 2658
1184 698
1189 1110
531 509
1641 500
700 661
1377 915
1950 1528
1684 1019
2498 2290
1885 484
677 199
1537 902
783 693
2213 2025
266 151
1511 663
1358 784
2244 1440
860 563
810 431
1864 739
338 255
838 349
680 248
922 913
2...

result:

ok ok (1 test case)

Test #72:

score: 0
Accepted
time: 79ms
memory: 25528kb

input:

1
100000
-894716977 -12445007
-635179783 -174303206
-468545915 -376509646
7552798 863131659
-452959582 -848004313
240678088 -531526042
-479003636 561079229
-136051729 -523206668
-54957196 -969050964
202486976 -149599358
511163288 -909769354
-642881606 611633044
470598875 411065934
-70167418 -8251878...

output:

100000
1104 366
543 440
1665 1484
3013 2691
4741 3860
1282 647
1909 1637
3973 1069
562 484
773 465
1844 844
1460 1176
1592 211
3114 2148
3103 1419
1293 639
2443 1249
3894 3143
1123 893
2742 2520
1171 207
2892 2137
6157 6059
1118 859
872 823
4340 4326
1487 1046
3686 2335
3413 3269
3932 376
2333 1257
...

result:

ok ok (1 test case)

Test #73:

score: 0
Accepted
time: 128ms
memory: 33964kb

input:

1
100000
798544191 -742903658
-344389104 -188662067
-571373110 161581382
-60448446 -916202148
-35781172 434088687
-786229077 240454644
-926134390 -986182581
17116411 -71954950
995069384 559207186
-65532930 -598813224
138636725 -620533705
781019115 572534456
-972340297 -182563578
-649565762 -18399977...

output:

99971
56880 36716
14631 30427
171593 103564
49253 23932
54780 49094
70500 28665
145668 8512
56055 872
80790 4271
116070 12345
103805 26247
85234 59182
138785 21519
109786 34512
93641 16590
48664 152942
12960 10323
87274 12975
79689 61269
161259 4136
137730 31359
180390 161444
69722 73904
18369 10239...

result:

ok ok (1 test case)

Test #74:

score: 0
Accepted
time: 82ms
memory: 29520kb

input:

1
100000
339988059 -602619276
-336733168 -602619276
-3170495 -602619276
608750101 -602619276
125004008 -602619276
877505856 -602619276
-736053016 -602619276
80826707 -602619276
612582932 -602619276
-901063623 -602619276
-24681200 -602619276
-338686211 -602619276
786194401 -602619276
-639927824 -6026...

output:

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

result:

ok ok (1 test case)

Test #75:

score: 0
Accepted
time: 85ms
memory: 26612kb

input:

1
100000
-152505637 741483922
608264196 -922967866
-978496364 741483922
517162535 741483922
-622471931 -922967866
-321900491 -922967866
69265759 -922967866
-580002960 -922967866
653169748 741483922
-40672330 -922967866
486195777 -922967866
301503518 -922967866
481889997 741483922
-351983361 74148392...

output:

100000
83948 1
179971 3
65585 4
186932 9
165246 13
134689 14
126205 16
17391 23
106877 25
157905 27
141980 28
198829 29
49095 30
155449 31
1110 32
98334 33
24429 34
126096 36
21994 37
158621 38
100989 40
120409 41
130966 43
20544 47
75403 51
4891 52
32981 53
98196 54
190837 55
150060 57
195869 58
76...

result:

ok ok (1 test case)

Test #76:

score: 0
Accepted
time: 79ms
memory: 27884kb

input:

1
100000
756868275 -358967603
-497301030 -358967603
649448245 -358967603
-887427985 -535956822
878399175 -535956822
108874606 -358967603
-489595415 -358967603
325972197 -358967603
498592984 -535956822
333245905 -358967603
-950621798 -535956822
-609666390 -535956822
-740046219 -358967603
-720433327 -...

output:

100000
123640 4
4673 5
154627 11
96955 12
181564 14
109735 17
21 9
108844 25
70643 26
149199 28
45264 29
31 22
37581 33
22044 35
3241 36
72157 37
88005 41
170764 43
70482 44
185539 45
108435 46
71179 49
79416 50
52 38
100760 53
90149 57
4950 58
59 56
61 60
78509 64
172629 65
107228 66
189559 69
1169...

result:

ok ok (1 test case)

Test #77:

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

input:

1
100000
264643553 -937908082
264643553 361997414
264643553 -23850010
264643553 753755453
264643553 362490250
264643553 239156434
264643553 -577712364
264643553 -392015932
264643553 -411918647
264643553 -915806614
264643553 231314817
264643553 -909126325
264643553 -20860430
264643553 647884648
26464...

output:

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

result:

ok ok (1 test case)

Test #78:

score: 0
Accepted
time: 79ms
memory: 26152kb

input:

1
100000
13210362 155232928
689159667 -465052240
13210362 21054014
689159667 867788821
689159667 -625434390
13210362 364078249
13210362 -911970949
13210362 937669731
689159667 -904647545
13210362 953420119
689159667 349328690
13210362 772099718
689159667 -718290541
13210362 -863735041
689159667 -306...

output:

100000
38296 2
46071 4
14584 5
182959 9
55851 11
97362 13
12052 15
163255 16
105161 18
195982 21
39740 22
15969 23
46845 24
52443 25
9884 26
65865 29
105025 31
40527 32
121893 33
108923 36
129153 37
197691 40
141648 41
32161 42
54396 43
34772 46
121564 47
61768 48
167920 49
110337 50
145062 51
18314...

result:

ok ok (1 test case)

Test #79:

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

input:

1
100000
-530472390 452797636
12273745 -840226242
12273745 138841937
-530472390 397016016
-530472390 309315299
12273745 979552760
-530472390 286391147
12273745 -839888853
-530472390 468449806
12273745 27131915
12273745 144818527
-530472390 -97939838
-530472390 -221056215
-530472390 -238960974
-53047...

output:

100000
5650 2
59766 3
9107 6
68906 8
198331 10
124862 11
101743 16
63363 24
112142 25
113845 29
25358 32
34 26
54288 37
141715 39
12836 41
63705 43
134779 47
67766 51
183225 52
143016 53
57 42
12237 60
194121 62
66 61
146379 69
175259 71
195596 76
28022 81
82 75
67042 84
35079 86
95523 87
159196 92
...

result:

ok ok (1 test case)

Test #80:

score: 0
Accepted
time: 93ms
memory: 26168kb

input:

1
100000
-132158759 -454759942
-893626513 149724597
-756161772 -22802718
579977604 -454759942
430467545 149724597
363069127 -454759942
-355589432 -488155881
348983244 149724597
253076693 -258440137
391935158 862260872
211993426 -258440137
928069632 862260872
403296863 -22802718
-302606363 -258440137...

output:

100000
20 19
171633 146901
126270 2953
81366 48918
179998 74141
61268 13157
71137 27
187958 26478
28 25
111965 92722
118266 74465
122804 10
112640 51361
157900 48953
42 12
32533 59
127481 116385
152638 62
133731 61673
96479 76
172604 145872
77 66
171162 129117
92 82
61002 211
166609 113
4947 116
107...

result:

ok ok (1 test case)

Test #81:

score: 0
Accepted
time: 81ms
memory: 26056kb

input:

1
100000
3959073 -767392567
109384252 941067269
-878847334 -620223817
607693789 483382967
998749160 43543215
259351742 -658880496
817766616 491476307
265921619 920072631
-95644194 43543215
-145143632 -356499617
-708593795 -254752752
292642145 865122144
-525142707 -376455870
653151805 -418942337
1803...

output:

100000
47185 18711
33121 29358
38098 32904
7801 377
24960 10447
8373 2960
22243 6625
63168 19250
30955 21238
14008 4249
22589 16897
66399 27697
1711 73
9616 9095
10176 1913
61182 24100
89617 66505
117035 114194
139789 131035
169191 151057
184039 183597
22229 9052
14583 553
10636 2512
4990 1005
33379...

result:

ok ok (1 test case)

Test #82:

score: 0
Accepted
time: 149ms
memory: 33804kb

input:

1
100000
-574560244 663989471
147836313 776509735
-654179276 -456564123
-688242213 850544277
-769192009 -999278429
47264577 -474897694
661553314 -35586919
31425538 950985408
119252682 -364980087
-482879014 -842019980
562833870 -434563528
-602373511 -586582786
-597688232 794041526
-796369392 -9877200...

output:

0
85419 64647
85842 132476
5440 87082
195926 106433
150410 54308
16860 153672
142943 35771
119566 54116
47056 126636
95279 183079
185257 141680
5304 122058
142694 38348
89930 175363
93366 96570
199230 110097
118573 1754
190992 140745
19660 34066
170781 199455
121602 98675
46936 85987
85244 72527
547...

result:

ok ok (1 test case)

Test #83:

score: 0
Accepted
time: 133ms
memory: 33800kb

input:

1
100000
563809006 598960902
129945828 823924799
-921279427 -278305161
932151061 -615426941
253018906 394552155
-685768166 660779890
443266995 -129270185
314826112 -262631640
503785849 280786037
964401164 -60690178
-543715115 692212503
570497299 -501483747
-280889633 566370668
238345598 -30723398
40...

output:

10
90458 34466
25284 74754
137127 129391
137685 179103
74324 181735
2407 55897
163486 149257
1993 161813
41743 175639
190155 182666
7398 15506
168734 132856
138298 112659
161028 708
107686 65317
6852 46325
195914 110231
94444 199265
133071 156520
65986 41876
188517 97762
82897 68972
132042 144770
15...

result:

ok ok (1 test case)

Test #84:

score: 0
Accepted
time: 138ms
memory: 34536kb

input:

1
100000
-250360297 -826731365
-132998833 434577984
-271597239 443621731
-568418163 -685113319
-351376307 -75720590
361691254 909826155
-611075026 748106801
-796334684 588036703
-192353104 -22634313
219167808 -130214795
153254126 -663910409
-706144293 -503074450
641195348 -471304455
952972496 722756...

output:

100
75140 195091
99842 127577
78003 122867
174662 110583
133075 114416
172532 58882
161123 85142
47238 87538
30868 102192
81145 120368
19704 84129
80177 177261
23718 185551
106731 168166
199479 145909
68167 25956
106814 90930
16146 3366
152325 166954
151917 16172
5960 135051
193416 33793
111887 1948...

result:

ok ok (1 test case)

Test #85:

score: 0
Accepted
time: 148ms
memory: 34088kb

input:

1
100000
847984927 -235516053
-225657532 174062262
-864702235 849255554
-294101500 -395862766
308093550 262724017
-821802819 777396740
-166183219 -205295668
-925592163 -890396698
629939776 554098977
-597066517 -627025783
-488670566 -192742453
321766317 357807409
-56687363 -479719304
-346692362 43123...

output:

1000
112223 170647
195502 154494
40627 125813
149869 52047
19500 128870
73989 52444
89928 7240
68837 65931
18179 153916
75818 183541
66627 96870
29323 85720
193667 187581
137248 171606
37139 147593
192155 7174
152756 23856
127448 120827
61275 173283
8241 164591
36889 130364
38 34
274 50
842 684
987 ...

result:

ok ok (1 test case)

Test #86:

score: 0
Accepted
time: 149ms
memory: 33296kb

input:

1
100000
326229520 805825077
371787034 -612906440
-488264751 -793472428
184436425 366708550
-501110960 713157720
810357640 -567097567
-906732603 439225325
-340392868 -70415813
-189664219 -713969208
381067874 -619756834
674460096 668727994
618268128 -733873663
-622488527 -374494000
-696690105 -871302...

output:

10000
111036 79565
187660 53058
117827 77636
5624 61009
132773 173741
92042 8605
3566 142166
197233 171069
66494 44276
17791 51377
22273 43730
34 3
71 64
198 90
224 212
229 226
273 233
375 370
387 382
409 399
426 413
434 428
500 498
577 549
609 603
631 628
641 632
668 646
698 691
704 699
710 708
724...

result:

ok ok (1 test case)

Test #87:

score: 0
Accepted
time: 81ms
memory: 29412kb

input:

1
100000
107663449 169602795
-293408075 136298377
107663449 677735329
107663449 -133164493
107663449 -405477830
-973012232 136298377
40661124 136298377
107663449 -772028365
314648168 136298377
-951394425 136298377
107663449 252358019
107663449 84643404
107663449 661318647
-458027461 136298377
107663...

output:

99999
6 2
9 7
14 10
18 17
25 22
27 26
30 28
32 31
37 34
40 38
44 41
47 45
52 51
56 54
60 59
63 62
69 67
74 73
79 77
81 80
84 82
87 86
89 88
94 93
97 96
100 98
106 102
109 107
115 110
117 116
123 120
128 125
133 132
136 134
139 137
143 140
146 144
149 148
152 150
156 155
160 157
163 161
167 165
172 1...

result:

ok ok (1 test case)

Test #88:

score: 0
Accepted
time: 93ms
memory: 29836kb

input:

1
100000
621676756 -105718828
907764147 -105718828
-558728021 -105718828
-945909098 -105718828
-602870402 -105718828
104020243 -105718828
-283225325 -105718828
-188159226 -105718828
-15757119 -105718828
12299950 -105718828
382647230 -105718828
961198249 -105718828
142879463 -105718828
677630999 -105...

output:

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

result:

ok ok (1 test case)

Test #89:

score: 0
Accepted
time: 85ms
memory: 29832kb

input:

1
100000
791929316 -452812205
-414545951 -452812205
-492402719 -452812205
-350798285 -452812205
308143137 -452812205
-270019539 -452812205
-837044713 -452812205
-855873836 -452812205
299134701 -452812205
-928378050 -452812205
949766412 -452812205
983552624 -452812205
-302417116 -452812205
-575137906...

output:

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

result:

ok ok (1 test case)

Test #90:

score: 0
Accepted
time: 82ms
memory: 29736kb

input:

1
100000
-389700968 -854866948
157177186 -854866948
389548526 -854866948
359801591 -854866948
-404781586 -854866948
-756263865 -854866948
-874320830 -854866948
-860738544 -854866948
-494835614 -854866948
135417793 -854866948
878395153 -854866948
416627219 -854866948
50576116 -854866948
-877491066 -8...

output:

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

result:

ok ok (1 test case)

Test #91:

score: 0
Accepted
time: 78ms
memory: 29992kb

input:

1
100000
-863878388 -228877853
556347609 -228877853
715519933 -228877853
-685414679 -228877853
121136094 -228877853
835184421 -228877853
2884225 -228877853
-632661834 -228877853
-376071163 -228877853
561924123 -228877853
104284355 -228877853
-832791265 -228877853
219285074 -228877853
-532813184 -228...

output:

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

result:

ok ok (1 test case)

Test #92:

score: 0
Accepted
time: 79ms
memory: 30044kb

input:

1
100000
59979025 770483795
-687037673 770483795
-606503145 770483795
74265013 770483795
535504783 770483795
-353324202 770483795
-742185632 770483795
-880778420 770483795
445635005 770483795
-637158728 770483795
-798486264 770483795
-969460603 770483795
-183267551 770483795
219412933 770483795
4516...

output:

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

result:

ok ok (1 test case)

Test #93:

score: 0
Accepted
time: 81ms
memory: 29800kb

input:

1
100000
-238717794 -675789740
892502036 -675789740
927735589 -675789740
265425600 -675789740
713089930 -675789740
975285688 -675789740
994425171 -675789740
377011822 -675789740
-469725428 -675789740
240456322 -675789740
-696780335 -675789740
13943625 -675789740
-105628955 -675789740
500932288 -6757...

output:

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

result:

ok ok (1 test case)

Test #94:

score: 0
Accepted
time: 81ms
memory: 30332kb

input:

1
100000
-721839075 207317220
198969479 207317220
721075181 207317220
816055383 207317220
129129955 207317220
578715168 207317220
938570372 207317220
-111023272 207317220
704310574 207317220
-29012555 207317220
-1124535 207317220
565642912 207317220
-164326927 207317220
269985061 207317220
-85992111...

output:

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

result:

ok ok (1 test case)

Test #95:

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

input:

1
100000
-394106502 -349602555
-214790523 -349602555
-773354523 -349602555
282532628 -349602555
908276613 -349602555
90866698 -349602555
547592286 -349602555
-771664838 -349602555
-459895994 -349602555
545210801 -349602555
348330065 -349602555
69245707 -349602555
-70850421 -349602555
-570400234 -349...

output:

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

result:

ok ok (1 test case)

Test #96:

score: 0
Accepted
time: 81ms
memory: 29640kb

input:

1
100000
-212599148 -631411742
-212599148 -756608454
-212599148 -380727055
-212599148 -483620464
-212599148 -806607419
-212599148 464110295
-212599148 100221705
-212599148 426302083
-212599148 -770781036
-212599148 238123749
-212599148 652260340
-212599148 7400105
-212599148 -114015691
-212599148 26...

output:

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

result:

ok ok (1 test case)

Test #97:

score: 0
Accepted
time: 80ms
memory: 29372kb

input:

1
100000
861172394 -290759846
861172394 752238765
861172394 -567950860
861172394 998044325
861172394 315984459
861172394 -627793707
861172394 -220676787
861172394 -268949003
861172394 -808244877
861172394 203040434
861172394 221600196
861172394 -142395895
861172394 723984474
861172394 25261585
86117...

output:

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

result:

ok ok (1 test case)

Test #98:

score: 0
Accepted
time: 97ms
memory: 30192kb

input:

1
100000
499304870 -456067706
499304870 -526478356
499304870 -698177941
962157497 -209895866
499304870 603709976
194809397 -209895866
499304870 -622241129
295675965 -209895866
798750809 -209895866
499304870 -379083513
499304870 -835042147
499304870 -239680418
69233437 -209895866
-139695003 -20989586...

output:

92291
6 4
9 8
14 13
19 17
22 20
28 26
31 29
41 34
45 43
49 47
53 51
56 54
58 57
63 62
69 65
72 71
74 73
80 79
85 81
87 86
91 90
95 94
101 98
105 103
110 106
116 113
118 117
121 120
127 122
131 128
134 133
138 135
141 139
155 144
160 158
164 162
170 167
172 171
174 173
179 177
184 182
188 185
194 189...

result:

ok ok (1 test case)

Test #99:

score: 0
Accepted
time: 112ms
memory: 31564kb

input:

1
100000
-858246250 615044192
-266041885 988276483
482718956 -318377373
-764628559 -906181651
-858246250 -473264095
142558228 706800755
-788262537 988276483
22746060 640859154
-990386331 988276483
-69851564 988276483
-858246250 85218196
218467508 988276483
-858246250 859181857
687573233 988276483
-4...

output:

67291
7 2
10 9
14 12
19 15
23 21
32 24
35 33
51 43
56 53
61 59
72 67
82 73
84 83
90 85
95 92
98 97
103 99
113 106
122 119
128 127
132 131
142 141
149 147
161 156
163 162
175 171
180 176
186 183
190 187
196 194
201 200
205 202
211 206
220 214
228 221
234 233
238 235
244 243
250 249
253 251
258 255
26...

result:

ok ok (1 test case)

Test #100:

score: 0
Accepted
time: 121ms
memory: 32340kb

input:

1
100000
-150551753 452254502
-589126107 -154864988
-774655110 -258862906
419458744 436149924
832748324 626049996
-150551753 -842016341
50222854 48805382
-533365798 510362787
417401571 -205386056
567574644 -154864988
-813149443 794441936
-299793018 -154864988
770796798 807259574
-150551753 345399056...

output:

32291
77155 126161
118161 198279
14309 189895
10 2
28 12
50 32
91 78
103 102
152 133
189 174
212 204
259 239
297 294
332 299
362 347
441 368
472 450
492 479
498 495
532 522
627 584
651 640
751 706
798 758
812 804
898 814
908 902
1042 972
1114 1079
1135 1119
1208 1154
1214 1209
1238 1218
1278 1246
13...

result:

ok ok (1 test case)

Test #101:

score: 0
Accepted
time: 140ms
memory: 33588kb

input:

1
100000
285908168 272049532
-886964145 -569780386
510905036 729082089
-980711479 -610409392
-374956972 -629812402
247564824 -494813970
-424829969 808435687
-596358126 293552786
-231573518 593358144
-206584506 -197027197
788863793 -320825254
-80636341 343699149
865833827 -126707889
-264031756 -99178...

output:

5111
13466 137373
118134 61529
28854 120314
25 20
118 31
148 147
174 153
217 215
252 241
331 286
408 398
533 445
567 536
606 594
652 629
674 656
739 707
781 741
817 782
886 861
907 903
911 909
945 917
964 947
1066 1018
1092 1089
1098 1095
1133 1106
1145 1135
1174 1153
1258 1235
1349 1297
1419 1392
1...

result:

ok ok (1 test case)

Test #102:

score: 0
Accepted
time: 142ms
memory: 33736kb

input:

1
100000
565553778 -960078095
363313784 637330036
813479302 196734774
-774652802 -191779344
-980564833 -172476596
97721308 -222616457
-585108481 -816071325
384348686 -771714186
399507870 923194801
775022324 -521366927
112774804 -456550819
596715515 -351906433
-733278086 945383835
-295767823 82342179...

output:

20
108914 116314
101520 178476
65506 116815
40552 190381
121514 152454
144495 25810
164042 87644
33170 119421
4266 192591
126351 44722
47027 43348
172654 75403
70379 133939
131824 134644
2326 58805
60610 105123
179061 102401
1700 68548
124586 171661
81404 11919
192781 197742
116053 7127
124592 13110...

result:

ok ok (1 test case)

Test #103:

score: 0
Accepted
time: 139ms
memory: 34468kb

input:

1
100000
832414397 -191973279
799697814 453822080
472902980 355661811
773889737 -237095042
139066161 -168030962
-200818308 -659210292
591819947 -690219588
-894723232 -724129935
309100621 -442280293
601783531 -629714403
-518284237 -502069854
-324318938 -999351826
-445350259 -776355044
579496048 -3535...

output:

200
143983 145667
120616 69855
178276 176191
121965 47654
34328 38757
56792 67349
149056 142814
120885 124138
134855 9751
141657 32156
47866 76985
67520 36334
82821 125498
150467 83240
77037 139745
91983 149296
94968 192295
167368 158483
45518 24732
185941 72743
146967 124584
47243 28909
124907 1822...

result:

ok ok (1 test case)

Test #104:

score: 0
Accepted
time: 137ms
memory: 33864kb

input:

1
100000
316081038 264919400
418308983 754756042
-672507100 -504831259
347176006 -475455422
-464074155 250593938
-689733050 -558992193
165084421 594791692
756992395 93538486
601928596 425487522
-948968175 -775787311
642279460 -97489081
949706854 134386823
-573515957 -691035427
686110259 935429550
-3...

output:

1984
26708 43596
196830 109828
186933 5894
65823 164325
13595 47548
25644 95201
35963 125484
42574 37119
46948 56376
22570 194797
166233 187820
140016 58113
27588 32656
69483 36923
155480 25159
114969 22966
41055 55565
119394 36979
8018 41224
54765 58065
43864 46268
137263 157612
24967 173702
20063 ...

result:

ok ok (1 test case)

Test #105:

score: 0
Accepted
time: 149ms
memory: 33136kb

input:

1
100000
889766050 -900215668
-785435069 932780511
-593598392 -319579936
-819907899 -897600509
-163102947 369765636
-287328155 456835725
-903811491 57154208
-354611840 883364613
475188396 746218920
-813614969 540734211
824473110 591677255
-509397296 458247192
468251135 -745120799
508553265 422069900...

output:

18252
30867 130239
92647 94232
108109 73253
17709 81359
197305 1594
34334 158030
151284 109298
103958 173042
10999 52181
196652 163997
163994 159253
95288 85881
172697 46749
95067 194590
25247 195155
126589 59728
164895 39390
6810 101611
140209 114777
178735 166634
88342 32732
59065 29061
186692 167...

result:

ok ok (1 test case)

Test #106:

score: 0
Accepted
time: 137ms
memory: 34012kb

input:

1
100000
569138929 623081181
595176935 -231729559
-353366942 -403863070
910926966 869119211
394470687 778639413
603585935 114468456
-834453070 52891615
988978359 457907555
-126372552 606236966
-965264313 -667974370
933978631 902269405
-462709387 -210009622
715607853 -386237572
-671683002 152885468
4...

output:

99999
80378 77506
136886 40856
100175 83134
56152 17028
108946 27956
78657 1965
14843 10576
19489 12217
148265 44310
132758 106861
28713 16626
103653 55892
165312 65886
93731 14242
38823 25723
95019 55936
179898 105510
81274 35350
69202 2705
102628 83434
70222 50290
55335 20028
19324 10832
103614 26...

result:

ok ok (1 test case)

Test #107:

score: 0
Accepted
time: 125ms
memory: 30988kb

input:

1
100000
-545580238 206875231
-334278490 284778314
-577688466 532471873
-696161358 -260770669
-543552171 609399466
-248845812 281374889
604662925 947696452
815211151 -792551232
-726993196 -873648831
-806959352 -523234454
451106708 -525149528
196005170 210990094
7637155 927805109
-471891793 91423437
...

output:

100000
3632 578
13170 13161
17623 13255
19844 17890
24353 20691
31106 25178
37013 32582
41897 38430
51891 47038
57640 55976
78983 63235
10512 289
22036 18257
54463 49823
55165 54703
34569 22259
14843 8760
42022 23921
57739 46896
101668 80069
140545 105368
9327 2743
30732 18825
39969 30867
49312 4131...

result:

ok ok (1 test case)

Test #108:

score: 0
Accepted
time: 79ms
memory: 29660kb

input:

1
100000
289524496 -156648931
477259193 -156648931
-940874730 -156648931
-678074509 -156648931
430778344 -156648931
314792323 -156648931
590595199 -156648931
336769789 -156648931
-952491382 -156648931
569800304 -156648931
-334619798 -156648931
745977166 -156648931
-939318247 -156648931
313727017 -15...

output:

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

result:

ok ok (1 test case)

Test #109:

score: 0
Accepted
time: 78ms
memory: 30040kb

input:

1
100000
551608067 365421420
-487728687 365421420
143644232 365421420
-351527721 365421420
-871435010 958574747
437117589 365421420
79082823 365421420
-932527349 365421420
-51983999 365421420
-981644356 365421420
27516634 365421420
122232864 365421420
-586305842 958574747
-186314882 365421420
-77505...

output:

100000
13 5
29 22
42 37
59 58
65 62
73 72
91 83
126 112
128 127
134 133
146 143
199 181
210 202
238 222
249 239
258 252
264 262
273 265
286 281
310 302
319 314
323 320
334 331
364 343
410 401
437 431
444 441
481 451
507 499
534 511
538 537
549 542
587 552
598 596
614 612
626 615
642 627
675 672
697 ...

result:

ok ok (1 test case)

Test #110:

score: 0
Accepted
time: 74ms
memory: 30088kb

input:

1
100000
973177252 740095208
603591199 740095208
912041445 740095208
-879893070 740095208
513021608 740095208
-296817755 397134181
-920132372 740095208
874286779 740095208
-697477339 740095208
675338682 740095208
-688816419 397134181
274927171 397134181
-966544303 740095208
-168526049 740095208
7376...

output:

100000
11 6
18 12
22 20
35 27
38 36
46 41
52 47
55 53
60 57
68 63
80 77
87 86
90 88
94 92
100 95
104 101
108 107
124 111
131 130
135 134
137 136
140 139
144 143
147 146
154 152
156 155
175 169
180 179
183 181
185 184
193 192
195 194
201 199
205 202
212 206
216 215
220 217
229 225
231 230
236 233
241...

result:

ok ok (1 test case)

Test #111:

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

input:

1
100000
801543585 -255560886
-749926618 -255560886
-127843709 -255560886
845588435 -737531782
988339842 -737531782
-626861162 -255560886
918453589 -255560886
749726781 -737531782
-581771893 -386009779
590486060 -386009779
734676998 -737531782
153171830 -737531782
845030651 -737531782
-915274358 -25...

output:

99999
2 1
6 3
14 7
20 16
26 24
29 28
31 30
34 33
41 36
44 42
47 46
52 51
55 53
57 56
61 59
64 62
67 65
70 68
73 71
78 75
82 79
86 83
91 90
93 92
97 95
101 98
109 104
112 110
114 113
119 115
121 120
131 129
138 137
141 140
143 142
149 147
153 152
159 158
169 160
186 180
190 189
192 191
201 200
206 20...

result:

ok ok (1 test case)

Test #112:

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

input:

1
100000
946325199 -654997315
-893568018 -134419061
729992347 -654997315
759203364 -134419061
931585734 -654997315
813067224 -654997315
-219515258 -654997315
942523112 -654997315
93044508 -654997315
112202638 -654997315
887362429 -654997315
-895695158 -654997315
122895052 -334072657
-236406425 -3340...

output:

99999
3 1
6 5
8 7
10 9
12 11
17 15
20 19
23 22
25 24
28 26
30 29
33 31
35 34
37 36
39 38
43 42
47 45
49 48
51 50
53 52
57 54
60 58
62 61
67 63
72 71
74 73
77 75
79 78
82 81
84 83
86 85
88 87
90 89
92 91
94 93
97 96
100 98
103 102
105 104
107 106
109 108
112 111
115 113
117 116
121 120
125 122
127 12...

result:

ok ok (1 test case)

Test #113:

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

input:

1
100000
-286313978 229324447
783769798 -259261199
203372724 229324447
903846546 -259261199
-62506027 229324447
-878593732 -259261199
-24614745 229324447
-681646734 -259261199
30846373 229324447
516134098 -259261199
383203441 229324447
-416474256 -259261199
-293604347 -259261199
-122611506 -25926119...

output:

100000
3 1
7 5
11 9
32 25
52 35
69 59
73 72
78 77
81 79
84 83
89 87
96 92
106 104
119 115
123 122
125 124
144 133
149 147
154 153
164 159
170 165
183 171
213 190
238 221
252 239
263 260
265 264
274 272
281 277
293 291
301 298
313 305
317 314
324 322
326 325
334 332
339 335
351 343
356 354
361 358
37...

result:

ok ok (1 test case)

Test #114:

score: 0
Accepted
time: 116ms
memory: 29892kb

input:

1
100000
-683388360 919019809
-859428325 -677839811
998213859 512472227
893351203 -331849691
-812365568 378975580
-361448436 -768680818
-498101610 -891785673
-48853924 827302039
-977322158 911487244
630622919 -47675260
464560219 -996571204
781514945 47367981
-641893570 460320130
-716591231 -24159771...

output:

97961
4326 829
13647 12339
17225 14830
25420 17885
32948 25972
42751 42527
44072 42811
55526 51436
62857 61071
66817 65771
78128 75446
82394 80674
95528 93187
103568 96007
131106 127596
146888 146129
158351 156530
162487 158434
167942 164684
182889 180637
192378 183982
193962 138884
3046 2372
42773 ...

result:

ok ok (1 test case)

Test #115:

score: 0
Accepted
time: 71ms
memory: 29584kb

input:

1
100000
965071155 961909473
965071155 116193246
965071155 -398741995
965071155 -46836400
965071155 107811853
965071155 472916725
965071155 -801103891
965071155 -429946712
965071155 779079739
965071155 -339584185
965071155 -117199737
965071155 -34574080
965071155 940172004
965071155 859809257
965071...

output:

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

result:

ok ok (1 test case)

Test #116:

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

input:

1
100000
-108646393 572873810
760590825 -20548996
-817355882 -691664274
-652085034 966416413
760590825 -791160497
-684709037 441553262
691698692 281355233
-899208930 128349406
-344513662 428545673
-108646393 7920617
760590825 -153682268
760590825 -5134307
-899208930 891399973
975722593 224997612
760...

output:

100000
13 8
47 23
144 70
193 188
205 197
286 284
348 287
364 359
375 372
428 426
549 480
570 561
599 574
707 692
715 710
775 765
786 782
922 850
1015 992
1048 1042
1064 1061
1173 1130
1210 1177
1240 1238
1292 1248
1330 1318
1375 1350
1514 1456
1556 1532
1620 1561
1660 1654
1690 1669
1707 1702
1801 1...

result:

ok ok (1 test case)

Test #117:

score: 0
Accepted
time: 127ms
memory: 29096kb

input:

1
100000
657771764 499917223
340860304 -894365154
-166481907 95140359
263475661 -453431393
-421208726 -214095000
880473397 -932916417
-75750425 259300793
-605153080 -141604420
562225805 7170053
-611074444 -745330023
834249871 -314820890
608021155 -709004755
-214410370 -48571110
643218522 497384980
3...

output:

96041
30538 22606
157631 68862
34391 30308
183799 176913
138876 127450
197124 35091
180235 22791
179905 14056
171558 116870
120501 18130
58572 174953
107853 73980
182551 192801
101801 193023
196841 147708
4874 10517
57938 29229
95359 83296
163457 52274
43454 11352
103457 110164
77385 50845
104489 22...

result:

ok ok (1 test case)

Test #118:

score: 0
Accepted
time: 133ms
memory: 29804kb

input:

1
100000
-367654468 -952563688
285936870 592116431
-274071733 455847465
-171624585 354239799
349408391 -485168327
767563471 234441392
-528077539 -342651670
502696003 -903892090
-229679854 -452018526
-553390072 218410940
632717195 56077406
588095737 -173132122
-618084086 465397930
931640280 533044102...

output:

80396
54836 16616
15917 175350
183011 92896
55522 130628
71674 133924
45078 145805
188853 152715
83178 65251
2517 198530
151705 173687
126232 50136
56001 120611
178496 748
11680 18352
156402 110677
138613 15250
98160 102437
7919 125916
2544 144442
19436 1413
104265 67777
146646 69216
130739 80445
13...

result:

ok ok (1 test case)

Test #119:

score: 0
Accepted
time: 138ms
memory: 32020kb

input:

1
100000
-906200254 -265351581
-61657317 -473114865
952191838 -484210630
-968862768 -688100917
-946086398 207717766
96200317 881558228
645408728 -29904463
-65219541 512094883
-105610142 -944887267
232013995 -248237040
571558060 -90454204
-56844375 -803257756
703491466 211175053
910638201 896424741
-...

output:

48783
81840 27439
87595 66331
131324 128285
198304 136032
188658 69403
18843 66820
145141 46725
30898 99894
127914 1521
123093 9315
144887 7510
194257 153578
89697 74561
148408 175612
57245 52332
112839 117373
165950 114622
108591 65599
79414 76723
188830 141082
165451 191621
114706 103998
58701 180...

result:

ok ok (1 test case)

Test #120:

score: 0
Accepted
time: 131ms
memory: 33080kb

input:

1
100000
766382075 -21012642
-128826313 -161927840
507846892 -465151202
-122637205 252503287
673961711 322092096
472140704 525292475
-591417285 438455480
-659982761 -855470959
781169250 -760438229
-230659843 -352619932
64397555 -344061705
249444096 -515285207
-966136666 474387926
836585434 673332290...

output:

9778
115078 142387
186990 135298
26769 84403
159936 81164
82120 147994
2771 64189
13650 167490
155498 43423
141525 151112
4158 62822
189871 144872
111492 191606
125976 156697
183884 175745
104443 57642
5232 163390
46088 149315
190625 79135
177544 172378
193444 195302
44518 55853
160527 196895
41807 ...

result:

ok ok (1 test case)

Test #121:

score: 0
Accepted
time: 133ms
memory: 37660kb

input:

1
100000
-391309465 574501656
-601163643 398769165
437998755 -432176181
-504670744 400573721
363523163 -727677520
-810716783 387537161
-171290820 222526143
-710458455 -569456596
-546226838 -832409181
531132193 824799149
-523158870 -960204834
907379792 -31354498
-659185380 651124824
-917386965 958360...

output:

100000
46787 10268
18371 9849
45971 32376
41923 31595
26480 8221
117233 95846
97207 74944
190426 149396
112912 62263
114061 109108
38999 28309
91547 20789
152337 101874
78615 29079
62553 39231
38382 32644
35435 14222
22804 16727
27527 10373
110323 46646
158739 9954
94153 91984
28676 20440
118801 399...

result:

ok ok (1 test case)

Test #122:

score: 0
Accepted
time: 137ms
memory: 36648kb

input:

1
100000
-570308074 564028419
41974764 951482748
-458707143 821043169
792070901 519849419
-897928950 732129807
-377209691 238697917
846996677 789967440
92894202 -75895048
674835179 -287863905
818656679 -759156926
-929937983 329230903
52584650 -174966413
-245982588 55776587
619716488 -142539574
-3331...

output:

100000
40183 13137
54347 42137
74524 65403
25720 6700
99979 84878
194160 166991
19445 12665
48294 19776
87608 64753
130588 13990
73870 9529
167061 159198
133559 52408
18372 15300
7754 5688
83518 26904
23919 20213
44723 35293
65584 44837
60094 7343
32171 22959
124235 84419
175112 168150
18849 3486
74...

result:

ok ok (1 test case)

Test #123:

score: 0
Accepted
time: 139ms
memory: 35756kb

input:

1
100000
-870867990 -427477336
377455239 817489100
878782331 -17678742
638141193 -507332664
760969286 -686215018
680187812 -958635909
650765571 -244064336
-162743943 -197718056
-803668177 -612150607
245627960 16037985
-301270470 -415814129
-725795982 901008722
-795739083 25301151
-690989959 99318401...

output:

100000
61972 22279
152272 20604
61806 13340
10151 4234
57378 14947
75039 72786
103873 98167
112045 75187
23212 7883
115666 46019
50062 33187
76913 51907
48055 8767
100682 67344
177405 3950
45764 45141
174719 34588
86972 20163
147441 95284
98007 78707
134771 64319
106991 17659
115938 68953
31576 2774...

result:

ok ok (1 test case)

Test #124:

score: 0
Accepted
time: 130ms
memory: 37264kb

input:

1
100000
-539465148 -845708233
41183593 -459286909
-334098911 241729240
-391831038 -16693053
973020777 536265241
556557281 -789431898
52149811 -685715732
-792343215 686258394
464507471 -40092028
-870155969 590469644
465578389 -589697394
-161523675 -991602821
855948608 265525154
-839351205 -62602192
...

output:

100000
44662 23525
28423 12618
151933 585
95691 72512
171034 61632
140645 108603
117215 110307
91765 84946
30730 26184
79510 32507
16733 8005
105461 40837
21928 3119
62536 14741
21776 10931
127846 54382
130426 29084
117364 11122
9670 1711
15574 8184
17277 12422
65645 23257
167245 42001
31141 7280
69...

result:

ok ok (1 test case)

Test #125:

score: 0
Accepted
time: 129ms
memory: 35408kb

input:

1
100000
-301707541 -107785349
651696377 527237688
-311820441 -207092527
-214569234 -975358436
701909387 -785968490
-711653988 396775134
320035803 -913625682
593258459 -175337068
238164130 72714700
-539135317 -424645474
-205072058 507538329
-942822743 848584924
20017998 840987059
-272745279 -7423224...

output:

100000
24124 14378
90269 10511
164784 19847
133619 32326
127746 93394
187379 143308
116681 97018
68611 737
124891 123868
130968 61579
72762 1659
72750 32452
79229 63103
49499 1585
81399 20347
27608 18858
78562 28989
80046 70752
169156 162541
37816 26726
91379 43692
56670 46628
10539 997
124152 27739...

result:

ok ok (1 test case)

Test #126:

score: 0
Accepted
time: 134ms
memory: 34768kb

input:

1
100000
372101953 621089677
-107763756 -662571441
-63243920 659729647
441606222 -20964438
-861658828 -775998558
970349344 -718761240
-11091310 -651405801
723558495 57067049
-334677637 723258287
833883610 54943079
734085988 -274788427
668836759 -415187691
-227285405 23994731
212507360 -328156423
940...

output:

100000
87831 77826
4680 1272
89796 31307
102384 53803
61484 2884
43460 2743
107721 106035
102169 72832
70458 13346
156447 102628
169059 166457
28680 13506
128962 66685
88757 63723
114012 18260
9098 2956
115934 93045
96061 36829
111807 105788
55039 46641
28366 27498
47849 44396
93257 52193
61494 2585...

result:

ok ok (1 test case)

Test #127:

score: 0
Accepted
time: 124ms
memory: 32216kb

input:

1
100000
-915867003 -471353976
-388104681 -614331870
712512068 -176609228
-249834836 -559087269
653127892 -445584953
754204027 962058868
-859865327 -430551978
-748113746 22447905
-53970847 230698214
488889725 -10963115
856013500 103474622
-985497526 -436330311
596095986 -945139677
35717532 -85633518...

output:

99946
86904 85665
35912 24682
176447 161885
58272 20782
41898 36448
122232 78051
52608 51403
144146 8845
65977 38671
94759 12745
125819 112703
125923 105229
110092 39013
184691 2473
59215 32783
144494 35969
138450 109534
194428 186086
99312 67989
145580 108953
128587 81285
120059 309
130763 80304
19...

result:

ok ok (1 test case)

Test #128:

score: 0
Accepted
time: 129ms
memory: 35140kb

input:

1
100000
-462294685 526220805
-608793181 78935812
-652123710 -88897518
-549445127 -950121976
404063639 -731462283
873109908 911227253
280108661 -384023678
-224512922 -527391217
-606653749 460705189
-795453552 954412985
557042734 419950356
71945893 766707128
975265143 857240778
678089771 850488211
86...

output:

100000
44751 2488
137168 136259
111475 92528
147589 60336
14001 3795
114147 28229
60169 10754
69015 22913
52258 47428
145275 101346
153006 58110
66051 16063
4929 2188
170580 81113
78266 51733
138447 121370
103794 51393
52480 14990
56984 51073
32207 16970
187372 67002
49607 23834
106958 43866
19919 8...

result:

ok ok (1 test case)

Test #129:

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

input:

1
100000
-217244737 -919036017
839515854 811349301
-529200839 -607492236
206068906 -756100661
-93942296 718088556
164065404 687609627
-335010106 575687136
-753768524 797665484
528969092 -675985219
-833864420 -976856005
-254998531 102163056
193138802 -109129538
-963610238 68206037
-505611099 66224247...

output:

100000
118860 63449
90460 28026
52949 31515
109902 97929
32688 14321
43859 16797
102615 32159
70205 11764
95700 62041
21972 11427
123889 7341
27163 24350
151402 105594
42702 20008
111091 55117
146554 8035
143603 74408
31706 9961
50855 26784
52893 21832
44931 33084
113030 38096
67491 52484
47945 8616...

result:

ok ok (1 test case)

Test #130:

score: 0
Accepted
time: 139ms
memory: 29048kb

input:

1
100000
546952831 -551916540
-222366580 -190550190
690748205 621971537
-304787213 -426869636
430677306 737609007
-552529934 -587069496
534035388 -224937134
817092293 51151294
-603326277 963652497
675552100 -708035960
570918080 -54876116
-969756137 789057618
412261743 152512971
404319641 37207120
-1...

output:

95853
55648 54423
126966 21044
44186 4433
35964 12892
185098 93423
117593 44849
111718 28151
163841 112731
2760 101559
94549 20410
45139 7384
129797 125338
170017 168582
57128 195301
197961 148936
63400 56519
129387 98280
160205 28064
50646 39950
104395 87626
143977 124083
111253 142351
132580 8837
...

result:

ok ok (1 test case)

Test #131:

score: 0
Accepted
time: 94ms
memory: 28212kb

input:

1
100000
-718650142 -337515990
219225987 -796448041
945735467 769273424
-265106195 -836296134
286397419 -465897164
-217444051 -861702365
-142203839 354946276
962047833 625331802
-436237082 697041665
-210015414 251812388
-580562900 -862577184
468877853 314574614
-848683471 -115639376
358203437 674429...

output:

100000
14737 11287
11364 8610
29670 26653
34027 31774
19801 15597
35130 10597
21972 16639
8840 6459
9590 6599
19666 19529
55600 52394
15219 13068
25048 14606
31786 23770
14387 12029
21404 11802
67027 4431
49281 2680
33360 30309
48985 10131
31415 18004
34699 32852
37224 35070
83757 46455
53895 21914
...

result:

ok ok (1 test case)

Test #132:

score: 0
Accepted
time: 133ms
memory: 32188kb

input:

1
100000
514065105 703173790
-898391374 199118883
-736313276 118966780
722733109 744001421
495427092 -308368925
-315318854 128815246
269153707 551867497
-795428350 -627563242
-221111684 -748945403
149671640 991495820
-169151249 -133790110
-552570804 601719573
-805801829 -857404452
-491986921 9945430...

output:

35570
91481 32332
103979 59337
21702 46731
85241 119994
52918 178096
107102 194426
190424 130408
11937 96070
43245 32152
107074 38506
25387 95797
112583 25128
45017 97191
11040 78305
45817 111104
129777 139425
135660 103335
134225 66283
94185 101530
150968 96125
113693 129236
86218 21509
130429 1165...

result:

ok ok (1 test case)

Test #133:

score: 0
Accepted
time: 78ms
memory: 29708kb

input:

1
100000
-352442278 -740018096
-88202974 -740018096
-738618658 -144110914
-738618658 -604922659
-738618658 -932820553
356311978 -740018096
578254098 -740018096
-738618658 -853474506
366314668 -740018096
-738618658 -328885215
-738618658 804967834
-738618658 -326990482
-675958519 -740018096
-943725244...

output:

100000
2 1
7 6
13 9
17 14
21 20
23 22
26 24
33 31
37 34
43 41
47 45
51 49
55 54
60 58
62 61
66 63
70 69
72 71
74 73
76 75
78 77
84 81
86 85
89 88
95 93
100 98
107 101
112 111
115 114
119 118
122 121
125 123
129 126
132 131
136 135
140 138
146 145
151 148
162 159
168 167
174 172
176 175
178 177
184 1...

result:

ok ok (1 test case)

Test #134:

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

input:

1
100000
325122130 172466804
325122130 812054805
325122130 982296227
325122130 -588934091
325122130 -19140359
325122130 547947686
325122130 -958881583
325122130 -115703499
399672789 821857835
-751884489 821857835
-407471339 821857835
-440355675 821857835
-930981956 821857835
325122130 411759969
9942...

output:

100000
10 9
12 11
15 13
24 19
33 26
43 41
51 47
57 52
59 58
61 60
69 62
74 71
79 78
91 86
97 96
101 98
119 111
122 120
126 124
131 130
138 136
143 141
151 145
153 152
157 156
159 158
161 160
166 162
171 167
179 174
189 187
197 195
210 209
218 217
220 219
223 222
225 224
232 228
245 240
250 247
263 2...

result:

ok ok (1 test case)

Test #135:

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

input:

1
100000
-226465324 -765160112
-804076207 -66372335
-996256652 -66372335
-232309074 -66372335
433736878 -66372335
-226465324 884802247
241435841 -66372335
-216832241 -66372335
311207842 -66372335
-226465324 -209742435
368069229 -66372335
-605974269 -66372335
-846600651 -66372335
781736433 -66372335
...

output:

100000
3 2
5 4
8 7
11 9
13 12
19 14
22 20
24 23
26 25
28 27
30 29
34 31
37 35
40 39
45 41
47 46
50 49
52 51
54 53
56 55
59 58
62 61
64 63
66 65
69 67
71 70
74 72
76 75
78 77
81 79
83 82
85 84
87 86
89 88
92 91
94 93
96 95
99 97
101 100
103 102
106 104
108 107
111 109
114 112
116 115
119 118
122 120
...

result:

ok ok (1 test case)

Test #136:

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

input:

1
100000
-938307807 -589622988
-781309279 862497436
-938307807 -280855161
-938307807 821787178
-938307807 -143785330
-342339007 862497436
-159228282 862497436
480181280 862497436
-725384126 862497436
-780856436 862497436
-915347010 862497436
-292109291 862497436
-183345034 862497436
158697996 862497...

output:

100000
6 2
8 7
10 9
12 11
14 13
16 15
18 17
20 19
22 21
24 23
27 25
30 29
33 31
36 34
38 37
40 39
42 41
44 43
46 45
48 47
50 49
53 52
55 54
57 56
59 58
61 60
63 62
65 64
67 66
70 69
72 71
75 74
77 76
80 78
82 81
84 83
86 85
89 88
91 90
93 92
95 94
97 96
100 98
102 101
107 105
109 108
111 110
113 112...

result:

ok ok (1 test case)

Test #137:

score: 0
Accepted
time: 4ms
memory: 19636kb

input:

10000
1
1 1
1 0
1
1 0
1 1
1
1 1
0 1
1
0 0
1 0
1
1 0
0 0
1
1 1
0 1
1
1 1
0 1
1
1 0
0 1
1
1 1
0 0
1
0 1
0 0
1
0 0
0 1
1
0 1
1 1
1
0 0
1 0
1
1 0
0 1
1
1 0
0 1
1
1 1
0 1
1
0 0
1 1
1
1 1
0 0
1
1 0
1 1
1
1 1
0 0
1
1 1
1 0
1
0 0
1 0
1
1 0
0 0
1
1 1
0 0
1
0 1
1 1
1
1 0
0 1
1
1 0
0 1
1
1 1
0 0
1
0 1
0 0
1
1 ...

output:

1
2 1
1
2 1
1
1 2
1
2 1
1
1 2
1
1 2
1
1 2
0
2 1
0
2 1
1
2 1
1
2 1
1
2 1
1
2 1
0
2 1
0
2 1
1
1 2
0
1 2
0
2 1
1
2 1
0
2 1
1
2 1
1
2 1
1
1 2
0
2 1
1
2 1
0
2 1
0
2 1
0
2 1
1
2 1
0
2 1
1
2 1
0
2 1
0
2 1
0
2 1
1
1 2
1
2 1
0
2 1
0
1 2
1
2 1
1
2 1
1
2 1
1
2 1
0
2 1
1
2 1
1
2 1
0
1 2
1
2 1
1
2 1
1
2 1
0
2 1
...

result:

ok ok (10000 test cases)

Test #138:

score: 0
Accepted
time: 7ms
memory: 20680kb

input:

10000
1
0 0
1 0
4
1 0
0 2
2 1
1 3
2 0
2 2
0 3
1 2
1
1 0
1 1
2
1 2
3 3
3 1
2 3
2
1 2
2 1
0 2
0 1
2
0 0
1 1
1 0
0 1
5
2 0
2 3
3 0
3 2
0 3
0 0
1 1
3 3
1 0
0 2
1
0 1
1 1
1
0 0
0 1
4
5 2
0 4
1 4
0 0
5 3
4 3
0 3
0 5
3
1 4
4 3
1 2
4 0
1 0
0 4
1
1 0
0 1
1
1 0
0 0
3
3 2
0 1
1 0
3 3
2 2
2 3
2
1 1
0 2
0 0
0 1
...

output:

1
2 1
4
7 4
8 1
5 3
6 2
1
2 1
1
3 2
1 4
2
1 3
2 4
2
4 2
3 1
5
10 4
8 3
7 9
6 1
2 5
1
2 1
1
2 1
4
3 2
1 5
6 7
8 4
3
2 4
5 3
1 6
0
2 1
1
1 2
2
2 3
6 4
1 5
2
3 2
1 4
4
5 7
6 2
8 1
4 3
1
2 1
1
2 1
1
2 1
2
4 1
3 2
5
12 5
10 3
2 1
11 7
8 6
9 4
3
2 1
6 7
4 3
8 5
0
2 1
1
1 2
2
4 1
3 2
3
7 2
4 6
3 5
8 1
4
9 ...

result:

ok ok (10000 test cases)

Test #139:

score: 0
Accepted
time: 16ms
memory: 19504kb

input:

10000
1
0 1
1 0
4
3 0
2 1
3 1
2 4
4 0
1 3
1 2
4 4
1
0 0
0 1
1
0 1
1 0
3
3 5
2 5
5 3
4 2
0 4
5 5
2
1 2
2 1
1 1
2 2
1
1 1
0 1
2
1 0
1 2
2 0
2 2
1
0 1
0 0
3
1 1
0 1
2 2
2 0
0 0
2 1
1
1 0
0 0
2
0 1
2 0
2 1
0 2
4
3 3
6 4
4 3
7 1
2 4
5 1
6 7
6 5
1
1 0
0 1
2
1 3
3 2
0 1
2 3
3
3 2
1 2
2 2
0 0
2 3
3 0
1
0 0
...

output:

0
1 2
4
7 6
4 8
5 1
3 2
1
2 1
0
1 2
2
3 6
1 2
5 4
2
3 2
4 1
1
1 2
2
2 4
3 1
1
2 1
3
5 4
3 6
1 2
1
1 2
2
2 3
4 1
4
8 7
2 5
3 1
4 6
0
2 1
1
4 1
3 2
3
5 3
2 1
6 4
1
2 1
1
1 4
2 3
2
6 2
5 4
3 1
3
9 4
3 10
5 1
8 6
7 2
1
2 1
2
4 3
2 1
0
1 2
1
2 1
0
2 1
1
1 2
6
5 3
10 8
6 1
11 4
9 12
2 7
2
1 2
4 3
4
8 2
7 ...

result:

ok ok (10000 test cases)

Test #140:

score: 0
Accepted
time: 21ms
memory: 19364kb

input:

10000
1
1 1
0 1
4
0 1
1 1
2 1
0 2
2 0
0 0
1 2
2 2
4
3 2
1 0
1 3
0 3
2 3
2 2
2 0
3 3
5
6 4
2 0
2 7
1 7
0 9
7 2
1 9
8 4
9 8
0 6
6
3 3
0 3
0 4
1 1
4 0
2 2
5 4
1 3
4 3
4 2
3 0
2 4
2
0 1
1 1
0 0
1 0
1
0 1
0 0
5
3 4
4 1
0 7
0 2
1 4
2 7
2 6
4 3
6 5
6 2
10
5 3
6 4
0 2
8 7
4 4
3 3
7 0
7 5
4 5
7 3
5 0
6 0
0 1...

output:

1
1 2
4
6 5
3 8
4 7
2 1
4
8 1
6 5
7 2
3 4
4
2 3
4 7
10 5
8 1
6 9
6
7 3
12 6
10 9
5 11
4 8
1 2
2
3 4
2 1
1
2 1
5
7 6
9 10
4 3
1 5
8 2
10
13 3
10 6
16 1
9 5
20 2
19 12
15 11
7 8
4 18
17 14
1
4 3
1 2
1
1 2
2
4 3
1 2
0
2 1
2
4 3
1 2
4
2 3
8 1
6 4
7 5
7
8 12
5 11
10 2
9 6
14 7
4 1
3 13
2
4 2
1 3
8
12 16
...

result:

ok ok (10000 test cases)

Test #141:

score: 0
Accepted
time: 22ms
memory: 19872kb

input:

10000
2
2 3
2 2
3 1
0 3
5
1 5
5 5
1 2
4 4
5 3
6 1
2 2
0 6
3 0
3 6
3
0 1
0 2
1 0
0 0
2 0
2 2
1
1 1
0 0
4
1 2
2 4
2 0
3 4
4 2
0 1
0 2
0 4
5
1 3
0 1
3 2
2 0
0 2
1 0
0 3
0 0
3 3
1 1
6
2 4
5 5
2 3
0 4
6 0
2 1
2 2
0 0
5 1
6 2
5 4
6 4
4
2 2
0 1
2 0
1 2
0 0
1 1
2 1
1 0
4
4 3
6 2
6 0
7 4
1 0
2 5
5 1
6 7
12
1...

output:

1
2 1
4 3
3
9 10
5 2
7 3
8 1
4 6
3
4 3
5 6
2 1
0
2 1
4
5 1
7 6
3 2
4 8
5
5 3
9 7
8 4
6 1
10 2
6
11 2
9 6
8 5
12 10
7 3
1 4
4
8 5
7 3
1 4
6 2
2
8 2
3 5
6 1
7 4
10
4 17
2 3
23 5
7 20
9 24
22 10
21 19
14 18
6 11
13 16
15 8
1 12
5
2 5
9 3
6 8
4 7
10 1
0
2 1
3
5 2
1 6
3 4
6
8 4
12 10
7 5
11 1
3 2
9 6
3
4...

result:

ok ok (10000 test cases)

Test #142:

score: 0
Accepted
time: 27ms
memory: 20288kb

input:

10000
10
1 0
0 1
1 4
1 2
2 1
0 4
0 3
4 4
1 3
3 0
4 3
3 3
2 0
0 2
3 1
4 1
0 0
4 2
2 4
1 1
7
1 3
5 6
4 0
5 3
1 5
6 3
0 2
1 1
2 1
6 4
3 1
3 6
3 3
4 2
12
5 0
1 5
9 5
3 8
9 2
4 7
1 1
0 6
8 6
9 3
7 5
7 9
4 3
2 8
7 6
6 9
1 8
4 8
9 0
7 8
5 4
2 6
5 3
6 3
8
7 5
2 7
1 6
6 6
2 4
0 7
3 2
2 0
1 2
7 7
2 6
0 6
5 4
...

output:

10
9 7
15 10
12 11
14 4
18 16
8 6
19 3
20 1
17 13
5 2
6
3 14
9 8
13 11
12 2
10 6
4 1
7 5
12
22 14
5 3
23 21
1 19
12 16
24 10
13 6
18 4
20 17
7 2
11 15
9 8
8
15 4
12 11
7 9
3 14
8 16
13 5
1 10
2 6
2
2 3
4 1
6 5
2
3 2
4 1
2
3 2
4 1
16
15 31
18 5
29 7
30 28
11 4
21 16
20 24
35 9
26 36
27 1
22 6
17 13
1...

result:

ok ok (10000 test cases)

Test #143:

score: 0
Accepted
time: 28ms
memory: 20644kb

input:

10000
1
0 1
1 1
3
1 2
2 2
0 2
0 0
1 1
0 1
2
1 0
0 0
0 1
1 1
6
3 2
3 0
1 3
2 0
4 3
3 1
0 4
0 1
3 3
3 4
4 1
4 4
5
2 3
6 6
6 4
4 0
6 3
7 3
1 3
3 4
4 5
6 7
3
1 1
2 3
1 3
0 0
2 1
0 3
6
5 2
2 5
4 7
1 5
5 3
2 4
4 0
6 5
6 4
8 5
1 4
6 0
1
1 0
1 1
6
4 11
3 7
9 10
0 5
1 10
4 4
7 8
8 2
4 0
7 0
1 3
4 2
4
0 6
6 2...

output:

1
2 1
3
6 5
2 1
4 3
2
3 4
1 2
6
4 2
9 3
12 5
11 8
6 1
10 7
5
8 3
10 2
5 1
6 7
9 4
3
3 1
5 2
6 4
6
3 7
12 8
11 9
6 2
10 4
5 1
1
2 1
4
3 5
4 11
6 1
7 10
8 12
2 9
4
8 5
2 6
4 1
7 3
5
4 10
6 2
9 3
7 12
11 8
1 5
1
2 1
16
17 11
30 4
13 2
25 12
10 15
24 16
29 7
18 26
23 6
31 21
14 5
19 8
20 32
27 22
9 28
3...

result:

ok ok (10000 test cases)

Test #144:

score: 0
Accepted
time: 38ms
memory: 20500kb

input:

10000
12
13 12
11 3
11 1
7 0
9 8
11 6
2 17
1 9
8 11
17 0
11 11
6 17
15 11
9 5
13 2
0 3
5 3
12 9
5 6
0 16
3 8
17 11
17 6
7 6
7
7 7
2 5
10 4
7 4
2 7
1 1
7 1
8 3
2 2
6 8
4 6
6 2
8 10
10 9
9
9 1
10 11
10 8
7 1
0 3
0 8
6 1
12 3
2 7
3 2
8 6
8 3
3 0
3 3
5 5
10 0
0 7
6 6
3
2 1
3 3
4 0
2 0
2 2
1 1
1
0 0
1 1
...

output:

11
17 19
24 4
11 9
13 22
10 23
6 3
2 16
18 8
12 7
14 5
20 21
15 1
6
10 12
9 2
5 1
14 3
4 7
6 11
13 8
8
4 1
7 18
11 12
6 3
2 16
13 10
14 8
9 17
5 15
2
3 4
5 1
6 2
0
1 2
1
1 2
3
3 4
6 1
2 5
2
4 2
3 1
1
2 1
7
6 1
7 11
10 9
8 14
2 12
4 3
13 5
16 15
19
33 8
34 14
38 35
37 7
26 12
30 1
39 32
21 25
6 3
2 1...

result:

ok ok (10000 test cases)

Test #145:

score: 0
Accepted
time: 42ms
memory: 21236kb

input:

10000
2
0 0
1 1
0 1
1 0
12
1 1
3 3
6 1
4 3
0 2
5 0
0 5
5 4
2 6
2 3
2 1
0 3
2 2
0 6
1 2
5 5
3 0
4 0
5 1
2 0
4 1
1 3
5 2
1 5
16
5 2
3 2
7 5
7 10
1 2
9 6
5 1
10 5
6 7
5 5
8 3
6 2
6 4
2 0
8 7
3 10
9 1
5 7
3 8
3 6
8 9
0 3
4 3
1 10
7 8
8 0
3 1
7 6
10 8
3 3
0 10
1 5
15
5 5
2 1
2 3
6 3
2 5
6 6
0 6
5 1
6 1
5...

output:

2
3 2
4 1
12
14 9
11 3
18 4
21 19
15 1
22 24
7 16
23 8
20 6
17 2
12 10
13 5
16
25 19
29 8
24 5
32 10
28 3
31 4
16 2
30 27
20 6
17 7
18 1
13 12
9 15
14 26
21 11
23 22
15
19 18
26 11
14 13
21 10
25 23
22 12
27 15
24 17
16 5
28 1
9 8
20 2
30 3
29 4
6 7
21
8 13
21 15
35 19
44 30
22 41
27 20
2 38
36 11
3...

result:

ok ok (10000 test cases)

Test #146:

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

input:

10000
8
7 4
14 3
1 8
9 12
2 7
7 1
12 3
5 3
7 12
1 9
7 2
9 10
4 12
6 8
12 12
11 2
6
4 3
1 1
2 2
4 0
0 0
3 0
2 3
1 0
0 1
4 2
3 3
2 1
56
0 5
10 15
5 0
6 17
5 3
11 14
3 5
5 12
7 2
0 14
13 18
14 9
9 6
13 15
7 18
19 13
11 6
7 9
16 12
8 0
20 18
20 0
19 9
5 16
19 14
2 20
3 11
11 13
10 0
5 1
3 19
15 7
17 19
...

output:

7
14 3
10 5
12 4
6 1
16 11
8 2
7 15
9 13
6
10 3
8 2
9 12
6 11
7 1
4 5
56
38 31
49 28
83 52
22 21
55 30
106 101
18 12
37 23
103 99
66 5
64 34
90 84
92 79
100 97
111 67
91 61
112 104
26 59
40 24
89 72
80 36
43 39
65 63
71 56
88 96
108 68
48 4
74 57
109 9
110 95
70 15
11 14
82 2
62 29
102 58
77 35
105 ...

result:

ok ok (10000 test cases)

Test #147:

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

input:

1000
116
40 14
11 4
18 3
11 36
20 21
11 5
10 21
8 37
8 38
11 22
40 33
4 4
2 36
31 21
0 0
37 16
21 39
16 42
41 9
13 25
6 41
33 2
38 30
30 38
9 33
19 24
0 20
7 38
27 21
22 39
1 41
42 18
3 1
5 40
38 18
38 32
4 29
1 19
0 27
16 36
22 31
11 29
30 41
42 31
34 8
16 19
1 24
27 9
13 19
1 9
8 18
34 24
9 4
22 3...

output:

116
163 126
65 52
105 45
62 7
143 71
215 159
46 40
129 18
43 24
169 85
96 58
117 119
184 115
209 63
133 6
83 81
227 97
48 19
67 50
128 14
156 142
222 150
177 75
203 196
198 152
77 28
214 213
140 87
89 33
191 54
210 200
180 110
172 168
193 197
76 73
127 111
186 3
212 91
88 27
230 112
104 95
149 131
2...

result:

ok ok (1000 test cases)

Test #148:

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

input:

100
1751
676 962
2080 1171
2449 361
678 1915
276 2074
1308 739
1328 739
442 105
1452 14
962 26
614 2079
1882 1674
1619 868
1354 435
2075 2473
514 1497
2365 2044
601 734
2227 1499
218 519
1848 600
219 1462
207 450
1644 1089
2157 2364
1890 1306
697 1851
1293 1484
1068 1656
2405 2194
625 727
2460 375
2...

output:

1627
1040 508
798 1849
1662 1546
1681 399
1810 3098
2511 2314
1463 809
1129 817
2788 400
2200 3105
750 30
3252 2031
3482 3293
747 849
3126 776
2717 279
3327 1646
1702 3090
2891 3213
2041 1005
2159 2116
3076 265
3073 121
960 31
3337 2676
638 346
897 498
1508 3067
1812 2828
1319 1250
3197 74
1594 3115...

result:

ok ok (100 test cases)

Test #149:

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

input:

10
5923
990 3340
465 3601
4722 4502
1946 1225
2051 4441
3447 2001
1373 1646
4604 1645
2067 2525
2984 486
1779 2132
281 2392
3682 3334
2807 2874
1709 1458
3249 1263
3358 1826
1067 3769
1473 3101
144 1498
2492 553
341 1852
397 4263
4683 3010
4547 4068
2198 689
2087 4032
182 545
3578 3282
3051 2356
258...

output:

5878
10207 10057
2543 104
665 799
7382 4037
9735 9158
5248 1580
8463 4017
8079 6711
4898 3896
10823 5931
9659 2204
10325 3316
7314 4875
11473 1210
4036 3662
10106 188
10037 146
6686 3764
74 4273
6276 4569
7399 5921
9708 8427
3515 100
6413 6868
5379 2946
7504 2616
2242 1854
7439 2406
9685 9493
3001 5...

result:

ok ok (10 test cases)

Test #150:

score: 0
Accepted
time: 130ms
memory: 30632kb

input:

1
100000
167013 125784
135343 32228
31636 139579
125392 28117
109132 130552
18863 126456
70093 140399
65187 131293
60990 127651
2030 57656
111845 109917
114136 18890
12132 33233
93847 20459
44854 159309
21435 47947
118357 48471
33129 78641
154624 169493
106664 83316
164632 49121
5045 149642
161002 1...

output:

86849
171913 140427
73941 61233
59593 123958
101644 102762
146350 110514
37092 144410
83372 55103
21848 817
82937 44365
198660 196576
89524 76081
114767 184208
142760 16278
190175 69482
124733 103119
181507 126660
186635 174041
99523 166736
43453 31840
159152 69100
144643 19595
6068 161352
187150 11...

result:

ok ok (1 test case)

Test #151:

score: 0
Accepted
time: 35ms
memory: 20436kb

input:

10000
8
2 1
0 1
2 3
3 3
2 0
1 0
1 3
3 1
1 2
0 2
2 2
0 3
1 1
3 2
0 0
3 0
6
2 3
3 0
0 1
2 1
0 3
3 3
2 2
1 1
0 0
1 0
0 2
1 2
56
2 4
5 2
6 6
4 9
5 1
8 5
10 7
8 3
2 0
8 6
6 1
0 4
9 8
10 10
2 2
3 10
6 3
0 9
8 4
2 5
4 5
10 2
1 8
8 8
10 3
2 6
6 10
1 0
2 3
6 0
2 10
8 2
9 9
6 7
6 4
3 9
6 9
9 3
5 10
5 0
10 6
9...

output:

8
15 5
16 6
13 7
10 9
11 14
8 4
12 3
1 2
6
11 7
12 8
10 9
2 6
5 1
4 3
56
26 10
45 34
58 52
55 11
27 14
39 31
60 44
95 78
107 16
59 36
88 71
108 89
111 63
70 62
97 83
98 5
54 40
84 69
101 86
106 2
22 15
61 32
85 79
103 93
57 49
74 73
109 87
112 92
96 94
25 7
80 67
105 91
42 41
77 72
104 3
35 30
81 37...

result:

ok ok (10000 test cases)

Test #152:

score: 0
Accepted
time: 45ms
memory: 20056kb

input:

1000
116
8 8
4 15
0 7
0 0
9 4
14 3
12 9
8 9
9 2
3 13
7 6
7 8
7 5
14 10
6 14
3 12
15 14
6 11
14 2
4 5
3 10
5 14
0 10
13 8
14 1
3 1
14 5
0 13
1 7
2 12
12 7
15 1
13 14
4 13
2 15
4 10
9 9
3 0
14 12
10 12
12 12
10 13
11 3
10 11
11 9
2 11
13 7
12 6
5 12
1 9
7 15
11 8
0 14
4 0
13 6
14 9
2 6
1 13
7 12
12 10...

output:

116
21 14
36 23
49 22
100 82
150 129
27 20
42 40
70 19
33 24
55 47
38 4
95 54
157 112
161 159
203 173
219 209
230 224
87 69
118 102
142 125
183 177
226 199
103 84
126 120
135 130
167 138
181 171
208 9
78 37
91 81
105 94
146 141
198 195
220 213
74 5
107 99
166 123
192 176
200 193
223 207
231 63
98 44...

result:

ok ok (1000 test cases)

Test #153:

score: 0
Accepted
time: 49ms
memory: 21048kb

input:

100
1751
43 55
50 32
40 59
17 23
14 41
50 44
52 57
26 29
6 21
2 50
46 36
34 9
44 12
55 22
20 5
23 45
50 43
53 6
41 58
19 27
22 53
16 32
11 56
7 36
20 39
23 48
46 48
9 51
15 4
40 38
51 36
21 45
52 7
49 37
10 24
16 56
33 50
48 56
51 34
11 33
43 18
20 59
4 9
41 44
52 23
26 26
20 51
40 36
37 59
40 56
37...

output:

1751
56 31
245 215
151 110
222 197
59 58
161 122
613 336
159 141
153 82
202 143
156 142
574 190
64 53
223 152
149 139
321 248
384 167
558 509
587 586
747 640
212 148
280 189
352 334
230 91
354 340
388 373
441 436
481 465
654 520
707 685
903 753
183 163
128 96
561 199
73 33
237 236
169 166
370 193
40...

result:

ok ok (100 test cases)

Test #154:

score: 0
Accepted
time: 59ms
memory: 20760kb

input:

10
5923
53 27
26 66
1 35
65 99
6 99
28 12
61 5
106 43
37 67
106 91
84 102
76 52
10 52
20 74
11 12
29 4
42 71
86 53
42 37
89 37
70 36
12 19
78 53
8 15
106 11
28 97
10 11
100 89
55 2
46 94
82 43
57 84
62 101
65 58
16 16
82 59
91 76
7 30
50 65
107 9
46 12
105 55
11 10
97 23
83 82
6 50
52 57
69 53
77 83...

output:

5923
322 300
454 409
363 359
309 231
286 229
457 366
272 99
224 109
426 239
190 72
1180 671
394 25
370 74
611 566
649 614
976 942
283 111
147 135
478 157
471 340
510 507
181 104
279 213
364 326
485 482
276 233
414 349
344 81
420 395
238 223
295 289
358 320
469 403
782 542
1004 858
1239 1136
1562 150...

result:

ok ok (10 test cases)

Test #155:

score: 0
Accepted
time: 58ms
memory: 25856kb

input:

1
100000
436 393
386 68
30 357
47 276
18 61
414 156
347 273
304 106
72 167
114 83
260 443
192 432
324 196
388 313
153 350
284 316
165 408
26 313
298 348
293 221
318 119
380 345
27 325
91 223
403 186
374 185
416 143
418 325
217 7
147 209
385 220
128 207
58 331
35 309
151 313
284 372
335 384
181 274
3...

output:

100000
927 669
791 321
1389 18
1516 966
1845 1269
806 548
466 397
1086 921
1006 704
521 471
433 214
420 257
1780 1166
2665 1957
2433 2405
422 412
1958 637
754 570
3049 1613
801 225
1102 977
1572 992
537 396
1222 1051
1440 1064
1167 644
989 255
1131 681
660 405
1658 1118
1103 1033
2247 269
1893 1583
...

result:

ok ok (1 test case)