QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198607#6414. Classical Maximization Problemucup-team870WA 280ms57188kbC++171.6kb2023-10-03 15:25:332023-10-03 15:25:34

Judging History

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

  • [2023-10-03 15:25:34]
  • 评测
  • 测评结果:WA
  • 用时:280ms
  • 内存:57188kb
  • [2023-10-03 15:25:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=1e5+5;
unordered_map<int,int>mx,my;
vector<P>tu[N*4],eg[N*4];
P pt[N*2],res2[N*2];
int dep[N*2],res1[N*2],cnt1,cnt2;
int dfs(int now,int fa){
    dep[now]=dep[fa]+1; vector<int>q;
    for(auto [son,id]:tu[now]){
        if(!dep[son]){
            int res=dfs(son,now);
            if(res)res2[++cnt2]={res,id};
            else q.push_back(id);
        }
        else if(dep[son]>dep[now])q.push_back(id);
    }
    for(int i=0;i+1<q.size();i+=2)res2[++cnt2]={q[i],q[i+1]};
    if(q.size()&1)return q.back();
    else return 0;
}
void slv(){
    int n;cin>>n;
    mx.clear(); my.clear(); cnt1=cnt2=0;
    rep(i,1,n*2){
        int x,y;cin>>x>>y; pt[i]={x,y};
        mx[x]=1; my[y]=1;
    }
    int cnt=0;
    for(auto &[k,v]:mx)v=++cnt;
    for(auto &[k,v]:my)v=++cnt;
    rep(i,0,cnt){
        tu[i].clear(); eg[i].clear(); dep[i]=0;
    }
    rep(i,1,n*2){
        auto [x,y]=pt[i]; x=mx[x]; y=my[y];
        tu[x].push_back({y,i}); tu[y].push_back({x,i});
    }
    rep(i,1,cnt){
        if(!dep[i]){
            int res=dfs(i,0);
            if(res)res1[++cnt1]=res;
        }
    }
    cout<<cnt2<<'\n'; assert(cnt1%2==0);
    rep(i,1,cnt2)cout<<res2[i].first<<" "<<res2[i].second<<'\n';
    for(int i=1;i<cnt1;i+=2)cout<<res1[i]<<' '<<res1[i+1]<<'\n';
}
signed main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 26036kb

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 1
3 4
2
1 2
3 4
0
4 3
2 1

result:

ok ok (3 test cases)

Test #2:

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

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

result:

ok ok (10000 test cases)

Test #3:

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

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

result:

ok ok (10000 test cases)

Test #4:

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

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
10 6
9 4
8 7
5 2
3 1
0
10 9
7 8
6 5
4 3
2 1
0
19 17
16 15
1 2
9 12
5 14
6 22
18 7
20 8
21 4
10 11
3 13
0
8 6
7 5
4 3
2 1
0
32 31
30 4
2 3
28 5
7 12
8 1
9 13
20 14
15 16
11 26
17 23
6 10
18 24
27 19
21 22
25 29
0
10 9
8 7
6 5
4 3
2 1
0
16 15
13 12
11 10
9 8
7 6
5 4
14 3
2 1
0
68 62
61 60
2 3
4 65
7...

result:

ok ok (10000 test cases)

Test #5:

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

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
2 1
1
111 76
112 108
106 104
103 100
98 97
96 93
92 91
90 88
87 85
84 83
82 81
79 110
74 73
72 71
80 70
68 78
67 102
75 66
65 105
64 63
62 29
56 61
26 2
28 23
27 24
21 35
16 15
94 1
37 7
34 89
22 17
107 101
13 48
69 6
95 77
11 4
49 55
25 99
58 9
54 20
12 3
46 14
59 8
30 47
31 32
33 38
10 50
39 86
...

result:

ok ok (10000 test cases)

Test #6:

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

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
9 10
8 7
5 6
3 2
4 1
0
10 9
8 6
7 5
4 3
2 1
0
6 5
4 3
2 1
0
10 9
8 5
6 4
3 7
2 1
1
9 10
33 32
31 13
7 1
19 5
34 21
4 3
11 12
17 2
16 18
15 29
20 8
22 23
24 6
25 26
27 28
14 30
1
12 13
16 15
14 11
10 8
7 6
5 4
3 9
2 1
0
4 3
2 1
0
4 3
2 1
1
10 44
49 48
47 43
42 40
37 45
35 38
33 32
41 31
30 29
28 26...

result:

ok ok (10000 test cases)

Test #7:

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

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
20 25
1 3
17 19
26 8
12 24
27 28
7 21
22 2
9 10
11 15
6 13
18 4
5 14
16 23
20
21 7
9 34
11 2
25 39
26 22
4 17
23 5
20 36
40 6
12 15
32 28
31 8
19 33
3 18
1 10
14 16
35 37
38 13
24 27
29 30
8
3 4
15 2
6 7
8 1
13 5
9 10
11 12
14 16
1
1 2
1
1 2
34
8 41
17 1
57 7
18 30
37 63
3 16
52 59
15 40
43 10
12...

result:

ok ok (10000 test cases)

Test #8:

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

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
1 9
6 7
4 5
8 10
2 3
3
1 2
6 3
4 5
5
3 9
1 6
2 4
5 7
8 10
5
6 3
4 5
7 1
9 10
2 8
5
1 2
3 4
5 6
7 8
9 10
2
2 5
3 4
6 1
1
1 2
13
6 16
12 14
15 18
9 19
1 11
13 20
26 17
2 3
7 21
5 4
8 10
22 23
24 25
4
1 9
6 7
4 8
5 2
10 3
3
2 3
5 1
4 6
2
1 4
2 3
5
6 2
1 5
3 4
7 8
9 10
7
7 13
6 9
14 4
11 16
3 10
8 1
5...

result:

ok ok (10000 test cases)

Test #9:

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

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

result:

ok ok (10000 test cases)

Test #10:

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

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
1 2
3 4
1
1 2
8
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 1
12
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
24 23
8
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
6
1 2
3 4
5 6
7 8
9 10
11 12
13
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
6
1 2
3 4
5 6
7 8
9 10
11 12
1
1 2
...

result:

ok ok (10000 test cases)

Test #11:

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

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
2 4
12 13
15 19
20 16
1 3
5 6
7 8
9 10
11 14
18 17
10
1 3
6 7
8 9
15 17
20 18
2 4
5 10
11 12
13 14
16 19
18
3 6
7 10
11 15
21 22
25 26
28 32
33 35
36 14
1 2
4 5
8 9
12 13
16 17
18 19
20 24
27 29
30 34
23 31
35
1 2
5 6
12 13
14 16
17 20
23 24
26 27
30 31
32 35
38 39
41 42
48 51
52 57
61 63
65 66
6...

result:

ok ok (10000 test cases)

Test #12:

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

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

result:

ok ok (10000 test cases)

Test #13:

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

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

result:

ok ok (10000 test cases)

Test #14:

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

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

result:

ok ok (10000 test cases)

Test #15:

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

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

result:

ok ok (10000 test cases)

Test #16:

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

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

result:

ok ok (10000 test cases)

Test #17:

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

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

result:

ok ok (10000 test cases)

Test #18:

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

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

result:

ok ok (1000 test cases)

Test #19:

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

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
226 222
219 215
213 208
207 204
203 196
191 205
189 185
209 184
181 180
179 211
175 174
173 171
169 166
177 164
163 162
161 160
202 198
159 168
158 157
201 156
153 151
214 148
176 146
143 142
135 130
132 128
56 53
73 58
4 197
147 44
83 28
183 121
42 167
139 7
90 54
82 210
41 29
187 60
75 178
86 37...

result:

ok ok (1000 test cases)

Test #20:

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

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

result:

ok ok (1000 test cases)

Test #21:

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

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
172 367
9 363
340 442
315 378
297 405
109 278
43 351
128 436
142 448
180 203
90 247
124 368
176 100
22 49
322 235
112 231
3 253
148 177
135 145
10 163
263 300
454 453
450 449
445 444
440 439
438 437
435 432
431 427
426 424
423 434
420 419
418 416
410 408
407 403
401 400
399 398
394 393
392 391
38...

result:

ok ok (1000 test cases)

Test #22:

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

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
47 165
143 161
158 168
142 155
16 162
83 27
26 104
80 54
12 98
84 71
15 23
121 56
70 6
51 124
92 132
29 86
72 112
10 75
65 115
135 139
166 111
159 164
131 149
174 171
172 170
167 160
157 154
152 150
148 147
145 144
141 58
57 138
109 41
107 40
20 32
46 122
39 130
50 60
35 53
78 34
113 31
74 151
21...

result:

ok ok (1000 test cases)

Test #23:

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

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
86 158
104 216
111 272
60 92
29 129
260 13
70 102
277 47
207 239
292 165
180 198
211 232
18 147
217 231
299 22
38 236
290 301
307 196
215 234
278 144
192 250
251 266
9 17
28 170
289 298
41 73
77 114
121 221
275 74
80 127
174 176
188 210
308 15
50 82
224 248
252 264
285 304
12 39
87 154
157 160
1...

result:

ok ok (1000 test cases)

Test #24:

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

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
14 15
104 110
124 116
70 106
109 79
46 64
77 20
17 66
105 55
44 53
61 67
108 33
22 31
62 78
56 71
30 39
52 86
120 27
16 25
28 59
82 92
21 34
7 58
73 84
91 101
8 48
3 76
125 23
26 29
85 112
114 75
122 1
18 24
45 60
68 95
65 102
13 36
96 10
4 90
94 99
103 123
63 54
6 41
42 74
97 119
12 38
49 72
98 ...

result:

ok ok (1000 test cases)

Test #25:

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

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
138 21
38 62
16 65
75 107
166 49
77 3
4 7
128 130
52 54
155 164
41 80
64 20
146 6
158 17
114 125
66 92
142 11
58 113
74 13
55 131
144 39
46 24
120 135
32 88
90 129
57 76
123 97
70 141
149 157
108 133
22 28
60 151
63 81
95 1
12 68
104 44
9 18
33 36
99 127
132 35
83 98
140 147
5 152
19 31
126 156
1...

result:

ok ok (1000 test cases)

Test #26:

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

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

result:

ok ok (1000 test cases)

Test #27:

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

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
2 3
10 12
13 15
20 21
23 25
26 28
33 34
36 37
38 39
40 42
44 46
48 49
50 51
52 53
56 57
60 63
64 67
70 71
72 75
76 77
78 79
80 84
86 88
89 91
92 93
95 96
97 98
99 101
102 106
108 110
111 117
119 122
123 125
126 127
128 133
134 135
138 140
143 149
150 151
152 153
155 163
165 166
168 170
175 180
1...

result:

ok ok (1000 test cases)

Test #28:

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

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
3 4
6 7
8 10
16 17
20 21
22 24
25 26
30 34
43 44
45 50
52 53
56 57
58 60
61 62
64 66
67 68
70 73
79 81
83 84
86 89
92 93
94 99
100 101
106 107
110 114
117 119
121 124
125 127
130 131
133 134
135 138
140 145
148 149
157 160
161 163
166 172
173 176
177 179
180 181
185 186
187 188
190 192
193 194
1...

result:

ok ok (1000 test cases)

Test #29:

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

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

result:

ok ok (1000 test cases)

Test #30:

score: 0
Accepted
time: 50ms
memory: 26256kb

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
1 4
5 6
7 12
14 16
18 20
22 28
29 31
34 36
37 41
42 43
48 49
51 52
53 54
55 57
58 60
61 62
65 66
67 68
69 70
73 74
75 79
80 85
86 87
88 89
90 92
93 95
96 98
103 104
105 113
117 118
119 120
121 124
125 129
134 137
141 142
144 145
147 148
149 158
159 161
162 56
2 3
8 9
10 11
13 15
17 19
21 23
24 25...

result:

ok ok (1000 test cases)

Test #31:

score: 0
Accepted
time: 44ms
memory: 26180kb

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
1 2
4 6
8 10
14 16
17 18
19 21
24 26
27 30
31 32
33 37
43 47
48 50
54 55
59 60
63 67
69 70
71 72
73 79
80 84
88 90
91 93
95 96
97 98
101 102
103 104
105 106
108 109
111 112
113 115
116 119
123 125
126 127
132 134
135 137
138 140
141 145
146 147
148 150
156 158
159 160
161 162
164 165
166 167
169...

result:

ok ok (1000 test cases)

Test #32:

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

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

result:

ok ok (1000 test cases)

Test #33:

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

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
15 50
127 44
62 45
106 19
41 93
101 96
59 64
140 141
20 47
66 107
81 21
113 100
30 52
32 97
6 9
63 144
139 99
22 28
118 2
7 98
120 159
112 73
37 128
89 94
85 83
104 134
56 152
36 154
5 137
150 74
146 54
29 61
57 24
38 70
123 164
10 46
111 115
16 76
80 162
42 149
156 35
39 69
86 153
131 142
75 151...

result:

ok ok (1000 test cases)

Test #34:

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

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
1430 1428
1426 1424
1423 1422
1421 1417
1416 1414
1412 1411
1409 1407
1405 1404
1402 1400
1399 1396
1394 1393
1391 1388
1384 1382
1381 1380
1379 1377
1376 1374
1373 1369
1367 1363
1361 1359
1358 1357
1356 1355
1354 1348
1346 1345
1343 1408
1342 1341
1340 1338
1335 1334
1329 1328
1327 1326
1322 142...

result:

ok ok (100 test cases)

Test #35:

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

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
485 2069
294 1956
2360 2359
1109 272
1108 995
2122 1106
311 1129
1098 1364
1097 1829
1093 1082
281 1081
1080 1009
1079 547
502 1623
1074 2127
1073 1069
322 459
1064 2295
1063 1061
1252 1059
501 1405
1057 165
1052 408
1123 1051
39 1422
1046 910
1045 1879
1040 2158
1038 1036
1033 1560
1032 2163
1031...

result:

ok ok (100 test cases)

Test #36:

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

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
20 19
18 17
16 1
3 4
5 15
6 2
9 14
7 8
10 12
11 13
0
246 243
242 241
235 233
228 224
232 219
218 217
215 213
229 211
239 208
234 205
204 201
197 193
191 187
185 184
250 183
180 178
176 189
175 188
182 174
172 171
202 170
169 168
167 216
166 165
244 194
163 162
161 160
207 159
158 156
153 151
149 2...

result:

ok ok (100 test cases)

Test #37:

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

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
5453 3655
9 4161
4033 5578
686 5569
4190 5559
3508 236
1190 758
5192 5374
73 3036
5268 5553
5523 5552
3165 3284
3838 4130
5412 3182
4451 5345
1175 1876
2574 4805
1058 5542
953 5048
3419 5531
4027 5530
2723 3050
3782 2141
3763 3578
3357 5515
2123 5510
4842 4207
5439 228
1857 2673
4105 1553
4990 ...

result:

ok ok (100 test cases)

Test #38:

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

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
78 894
1287 102
516 1636
286 930
1103 1120
264 324
427 632
702 64
1830 564
531 694
1846 735
651 660
482 1537
771 131
1441 414
1127 650
497 1434
1516 363
22 792
596 1828
168 1658
1399 852
1070 1371
1696 202
161 219
1418 640
273 1767
115 141
957 454
899 224
1470 122
942 1660
315 327
1209 505
1911 ...

result:

ok ok (100 test cases)

Test #39:

score: 0
Accepted
time: 39ms
memory: 26884kb

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
9 205
278 291
59 298
217 222
303 127
225 234
13 58
129 32
48 68
191 33
38 100
144 251
67 96
221 296
297 40
41 97
188 248
283 54
104 158
196 220
299 21
45 51
87 124
176 250
79 99
130 199
236 238
346 85
113 145
155 169
175 224
274 117
150 167
192 230
275 293
306 14
162 163
164 241
258 272
315 316
...

result:

ok ok (100 test cases)

Test #40:

score: 0
Accepted
time: 50ms
memory: 26180kb

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
4 12
69 300
335 369
401 406
410 535
714 795
879 881
391 92
38 56
65 228
344 352
437 494
504 565
579 662
731 738
745 755
767 875
883 905
450 623
45 82
130 528
533 554
571 581
597 621
735 743
761 859
886 890
637 1
6 43
80 151
282 351
362 389
435 461
492 497
582 611
617 624
664 687
768 800
834 849
...

result:

ok ok (100 test cases)

Test #41:

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

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
14 23
27 29
55 56
57 58
61 73
100 104
114 115
117 128
136 141
151 162
165 170
173 182
192 198
200 202
210 220
227 235
237 241
254 258
262 268
75 10
15 20
32 35
38 39
52 60
66 69
74 82
83 94
108 118
121 142
144 147
181 185
205 207
226 236
245 247
257 269
275 279
24 8
11 12
22 30
45 48
49 53
54 76...

result:

ok ok (100 test cases)

Test #42:

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

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

result:

ok ok (100 test cases)

Test #43:

score: 0
Accepted
time: 40ms
memory: 27824kb

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
1 8
10 13
16 17
20 23
24 27
29 35
36 38
42 43
45 51
53 55
57 58
62 63
64 66
67 70
71 72
73 76
78 83
84 85
86 89
91 92
96 98
101 105
106 109
112 114
115 117
118 119
121 122
124 130
133 137
139 142
145 149
151 152
153 157
160 164
165 166
167 170
171 174
175 176
178 182
183 184
185 186
188 189
192...

result:

ok ok (100 test cases)

Test #44:

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

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
1 8
12 13
18 19
20 22
23 25
26 30
31 32
33 38
39 40
49 53
54 56
57 58
65 66
68 71
72 74
75 77
80 81
82 84
86 87
89 93
95 96
99 103
104 106
108 110
112 114
115 116
117 120
122 123
124 128
129 130
131 132
133 134
135 136
140 141
144 146
147 149
152 154
155 157
158 159
160 166
167 168
169 170
175 1...

result:

ok ok (100 test cases)

Test #45:

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

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

result:

ok ok (100 test cases)

Test #46:

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

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
1 3
4 6
7 10
14 15
16 17
19 20
21 24
25 30
31 33
35 36
39 44
45 46
51 52
54 55
56 57
58 59
67 68
69 73
75 77
79 80
81 82
84 86
89 90
91 92
93 98
99 101
102 103
104 109
110 114
115 117
118 119
120 121
122 125
126 127
128 129
131 134
143 144
145 146
147 148
149 151
152 154
157 158
160 161
164 166...

result:

ok ok (100 test cases)

Test #47:

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

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
1 2
6 9
10 11
14 15
17 18
19 20
21 22
23 26
27 28
30 31
35 37
38 41
45 50
51 52
54 55
56 57
58 59
60 62
65 66
69 71
73 74
80 81
82 87
89 91
92 93
94 95
96 97
107 108
109 113
119 122
125 128
129 130
131 132
134 135
136 137
139 142
145 146
152 155
156 158
159 164
165 166
167 170
172 176
179 181
18...

result:

ok ok (100 test cases)

Test #48:

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

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
12 14
24 40
47 63
70 74
77 82
83 84
94 112
143 149
180 189
202 205
206 209
216 226
229 237
242 243
244 245
246 259
273 281
289 290
291 294
300 302
303 306
308 314
327 330
341 344
355 368
378 387
398 408
413 415
438 477
486 491
501 510
520 529
535 541
548 555
557 560
561 566
570 572
576 582
587 ...

result:

ok ok (100 test cases)

Test #49:

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

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
39 64
66 77
80 110
134 139
144 157
161 169
173 174
177 193
207 208
221 230
130 7
24 46
61 78
86 109
131 135
165 186
210 213
215 170
205 31
37 42
43 50
65 67
82 83
90 92
113 127
168 176
179 181
197 198
211 227
228 162
2 20
21 26
44 68
79 85
112 116
124 132
145 150
172 188
190 192
202 41
206 4
5 1...

result:

ok ok (100 test cases)

Test #50:

score: 0
Accepted
time: 115ms
memory: 33092kb

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
21135 21134
21133 21132
21131 21130
21129 21127
21125 21124
21123 21122
21120 21116
21115 21113
21112 21110
21109 21108
21107 21106
21105 21101
21100 21099
21098 21097
21095 21093
21091 21090
21089 21087
21086 21085
21084 21083
21082 21079
21078 21077
21073 21072
21071 21070
21066 21062
21060 2105...

result:

ok ok (10 test cases)

Test #51:

score: 0
Accepted
time: 132ms
memory: 34452kb

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
931 1118
997 1034
1966 1965
1964 1963
1962 1957
1954 1953
1951 1949
1947 1946
1945 1944
1943 1942
1941 1937
1936 1931
1929 1927
1925 1924
1922 1921
1918 1917
1916 1915
1913 1911
1909 1907
1906 1905
1900 1897
1896 1893
1891 1888
1886 1885
1884 1883
1882 1876
1871 1869
1864 1863
1861 1853
1849 1847
...

result:

ok ok (10 test cases)

Test #52:

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

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
23350 24745
16835 30440
28750 24443
8821 30436
2748 13870
30208 30429
10126 30427
7522 30425
6995 12296
6226 16906
14865 30421
7207 18161
14914 30393
6002 14666
23516 30372
13485 9841
13085 17876
9969 30366
6610 30364
21031 30359
11466 19551
12120 1673
5894 30353
18439 3075
11296 24132
809 2382...

result:

ok ok (10 test cases)

Test #53:

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

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
6989 9695
2570 12912
11394 2974
7502 3987
9025 12857
9092 10393
2043 949
1915 11013
2280 4560
2692 11009
6469 8414
2672 8485
12667 10711
2810 2797
7545 668
2921 11954
3176 2541
2980 12453
2610 7841
2864 3093
7607 247
6104 7291
2732 6933
4355 8205
12699 3097
6971 8894
10956 2820
7367 9090
11382 ...

result:

ok ok (10 test cases)

Test #54:

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

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
5174 23041
3062 7809
20795 22197
33002 6573
22336 3538
3377 24999
8104 16898
3746 14449
21455 2591
23861 18298
3894 25204
31988 18985
35784 829
5288 24998
31375 20247
27812 38677
28653 20994
10223 28901
37006 16242
11681 12223
10591 17976
19292 13986
15780 32024
3643 27819
5792 18886
3897 2819...

result:

ok ok (10 test cases)

Test #55:

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

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
4632 20679
3369 21855
13237 18672
3817 14855
21583 2327
4457 17583
3794 14944
21380 24013
10076 10343
19318 24187
2157 13817
16252 16872
19971 6267
11042 16091
18751 21090
1385 1940
5048 14056
25262 25442
750 4050
4062 5115
6274 23173
1069 2610
4113 10356
14983 18910
22125 6095
12512 13967
163...

result:

ok ok (10 test cases)

Test #56:

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

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
580 865
1694 1921
3673 4980
5182 8602
9193 9379
9726 11440
12906 13543
15024 16506
19520 20231
23860 24092
26675 28380
31434 32448
35697 24145
413 5749
6272 6461
7622 7871
9322 9459
9500 9908
9954 10574
10963 12603
12982 13422
13635 15998
18071 18147
19716 20210
20911 21151
22044 23339
24081 2...

result:

ok ok (10 test cases)

Test #57:

score: 0
Accepted
time: 90ms
memory: 31756kb

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
2 13
14 15
18 19
21 27
28 31
33 35
36 39
40 41
50 56
57 59
64 66
68 69
73 78
79 83
89 93
94 95
97 98
100 106
107 109
110 111
113 114
120 122
123 128
130 135
136 150
154 157
158 159
168 176
178 179
181 190
192 194
195 196
197 199
200 202
205 206
208 211
212 218
225 230
231 232
236 237
239 242
243...

result:

ok ok (10 test cases)

Test #58:

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

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

result:

ok ok (10 test cases)

Test #59:

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

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
3 7
8 10
11 16
17 18
21 22
23 25
26 27
28 30
32 35
36 37
38 39
41 42
44 45
49 50
51 55
56 57
58 59
61 63
65 67
68 71
75 76
77 80
81 85
86 87
88 89
90 94
97 99
107 109
110 112
115 117
118 119
120 123
124 125
127 128
130 131
132 135
137 140
141 142
144 145
146 148
150 151
153 154
155 156
157 158
...

result:

ok ok (10 test cases)

Test #60:

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

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
1 2
7 11
12 13
14 15
17 21
26 27
28 29
30 32
35 37
38 41
42 43
46 48
50 51
52 54
55 57
59 62
64 66
70 72
73 74
84 88
90 91
93 94
95 97
98 100
101 104
108 110
112 114
118 119
123 127
128 131
135 140
142 145
146 147
148 151
155 157
158 160
163 166
167 168
171 172
174 175
176 182
186 191
194 199
2...

result:

ok ok (10 test cases)

Test #61:

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

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

result:

ok ok (10 test cases)

Test #62:

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

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
1 2
5 6
9 10
13 17
18 19
22 24
25 27
29 30
31 32
33 34
35 39
40 41
43 44
47 49
51 52
53 54
55 59
62 63
65 66
67 68
69 72
74 75
76 78
79 81
86 87
89 92
93 94
95 96
97 98
100 101
103 104
107 109
111 113
115 117
118 119
124 127
129 130
131 132
133 136
139 140
141 142
145 147
148 149
150 151
153 157...

result:

ok ok (10 test cases)

Test #63:

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

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
1 2
3 4
5 7
9 11
12 14
16 17
20 22
24 25
27 28
30 32
34 36
37 38
39 40
41 42
43 46
47 48
50 53
57 58
61 62
63 64
66 67
68 69
72 73
74 75
76 78
79 81
82 84
85 88
90 91
92 93
94 98
99 100
102 103
104 106
107 109
110 113
115 116
117 119
121 123
124 125
127 129
130 141
142 143
144 154
155 158
160 ...

result:

ok ok (10 test cases)

Test #64:

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

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
8 9
40 71
78 81
82 109
117 118
159 167
177 178
182 188
191 202
226 229
234 245
255 277
285 287
293 296
315 317
318 335
340 344
345 350
360 367
372 373
382 383
386 408
426 449
456 473
504 510
511 515
518 523
540 554
561 565
568 574
611 622
638 640
675 681
683 688
689 691
696 700
706 716
720 728
...

result:

ok ok (10 test cases)

Test #65:

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

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
5 25
30 36
44 63
65 71
79 84
123 134
147 148
151 162
174 189
197 210
213 217
218 219
222 223
235 243
248 252
255 266
276 277
279 285
303 316
318 323
335 360
367 370
371 381
463 486
506 532
539 541
561 567
568 571
582 606
613 629
639 656
668 676
707 729
732 741
746 756
788 789
791 797
806 821
8...

result:

ok ok (10 test cases)

Test #66:

score: 0
Accepted
time: 280ms
memory: 57188kb

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
63240 180810
10401 178409
83326 83895
182115 41051
62290 72594
149697 49949
166828 49195
198477 79976
101362 45492
170770 117559
14288 29229
146324 134034
66171 149552
144486 2141
166114 67341
126162 171747
71595 187330
9286 37584
28428 29718
39525 192121
154893 109193
142744 64369
143875 22866
1...

result:

ok ok (1 test case)

Test #67:

score: -100
Wrong Answer
time: 260ms
memory: 54688kb

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:

28277
198137 178304
101235 199991
168463 199985
172267 199975
154252 78631
90021 102454
181756 172260
30794 199955
187497 196489
187195 199922
170125 199908
56360 199904
29827 199903
167177 199745
156675 19633
26175 134448
41573 199872
15773 199869
53162 144976
130908 151925
75766 199801
158476 4148...

result:

wrong answer worse than author's solution: expected 30281, found 28277 (test case 1)