QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303341#370. CityNATURAL6100 ✓140ms12592kbC++141.3kb2024-01-12 09:02:112024-01-12 09:02:12

Judging History

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

  • [2024-01-12 09:02:12]
  • 评测
  • 测评结果：100
  • 用时：140ms
  • 内存：12592kb
查看
  • [2024-01-12 09:02:11]
  • 提交

Encoder

#include<bits/stdc++.h>
#include "Encoder.h"
using namespace std;
int n,dfn[250010],tot,pos[250010],siz[250010],S[250010];
vector<int>e[250010];
inline bool cmp(int x,int y){return S[x]<S[y];}
inline void dfss(int rt,int da)
{
	S[rt]=1;
	for(int i:e[rt])
	{
		if(i==da)continue;
		dfss(i,rt);S[rt]+=S[i];
	}
	sort(e[rt].begin(),e[rt].end(),cmp);
	return ;
}
inline void dfs(int rt,int da)
{
    dfn[rt]=pos[rt]=++tot;
    for(int i:e[rt])
    {
        if(i==da)continue;
        dfs(i,rt);
        pos[rt]=max(pos[rt],pos[i]);
    }
    int s=1,lim=pos[rt]-dfn[rt]+1;
    while(s<lim)s<<=1;tot=max(dfn[rt]+s-1,tot);
    siz[rt]=s;
    return ;
}
void Encode(int N,int A[],int B[])
{
    n=N;
    for(int i=0;i<n-1;++i)
    {
        e[A[i]].emplace_back(B[i]);
        e[B[i]].emplace_back(A[i]);
    }
    dfss(0,0);dfs(0,0);
    for(int i=0;i<n;++i)
	Code(i,dfn[i]|((31-__builtin_clz(siz[i]))<<21));
    return ;
}
Source code, Language: C++14

Device

#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
void InitDevice(){return ;}
int Answer(long long S,long long T)
{
    int Mx=(1<<21)-1,dfns,dfnt,sizs,sizt;
    dfns=S&Mx,dfnt=T&Mx;
    sizs=1<<(S>>21);sizt=1<<(T>>21);
    if(dfns<=dfnt&&dfnt<=dfns+sizs-1)return 1;
    if(dfnt<=dfns&&dfns<=dfnt+sizt-1)return 0;
    return 2;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 6ms
memory: 9532kb

input:

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

output:

8388609 6 4194308 11 2097162 2097154 4194312 3 5 9

input:

Interaction has been finished!

output:

0
1
0
1
1
0
0
1
1
2
2
0
2
2
2
2
2
0
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
2
2
2
0
2
2
8388609

result:

ok

Test #2:

score: 8
Accepted
time: 0ms
memory: 9552kb

input:

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

output:

8388609 3 9 7 5 2097156 4194312 6291462 2097154 10

input:

Interaction has been finished!

output:

0
1
0
1
0
1
1
0
1
2
2
1
0
2
1
2
1
2
2
2
2
2
0
2
2
2
0
2
2
2
2
2
2
2
2
2
0
2
0
2
2
2
2
2
2
8388609

result:

ok

Test #3:

score: 8
Accepted
time: 6ms
memory: 9656kb

input:

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

output:

8388609 9 8 6291462 10 5 4194311 6291460 3 2097154

input:

Interaction has been finished!

output:

0
0
0
1
0
0
0
1
1
2
1
1
1
0
2
0
1
2
2
2
2
0
2
2
1
0
0
2
0
2
0
1
2
0
2
2
2
2
2
2
2
2
2
2
2
8388609

result:

ok

Test #4:

score: 8
Accepted
time: 6ms
memory: 9672kb

input:

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

output:

8388609 4 9 4194306 7 2097160 11 6291462 3 2097162

input:

Interaction has been finished!

output:

0
0
1
0
0
0
1
1
0
2
0
1
2
2
1
0
1
2
2
0
0
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
8388609

result:

ok

Test #5:

score: 8
Accepted
time: 0ms
memory: 9532kb

input:

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

output:

8388609 3 10 4 11 4194313 8 6291462 2097159 4194306

input:

Interaction has been finished!

output:

0
1
1
1
0
1
0
0
1
2
1
0
2
2
0
1
0
2
2
0
0
2
2
2
2
2
2
0
1
2
2
2
2
2
0
2
2
2
2
2
2
2
2
2
2
8388609

result:

ok

Test #6:

score: 8
Accepted
time: 0ms
memory: 9624kb

input:

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

output:

8388609 7 5 4194310 6291460 3 2097160 2097154 9

input:

Interaction has been finished!

output:

0
0
1
1
0
0
0
1
1
2
2
2
2
2
2
2
2
2
2
2
2
0
1
1
1
0
2
1
0
0
2
2
2
2
2
1
8388609

result:

points 1.0

Test #7:

score: 8
Accepted
time: 6ms
memory: 9656kb

input:

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

output:

8388609 4194313 7 4 4194309 2 10 6 11 2097155

input:

Interaction has been finished!

output:

1
0
0
1
1
1
0
0
0
2
2
0
1
2
2
2
2
0
2
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
2
2
2
2
8388609

result:

ok

Test #8:

score: 8
Accepted
time: 6ms
memory: 9548kb

input:

5 10
4 1
0 4
0 2
2 3
0 4
2 0
1 0
3 0
2 4
4 1
4 3
1 2
2 3
1 3

output:

6291457 3 2097156 5 2097154

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
6291457

result:

points 1.0

Test #9:

score: 8
Accepted
time: 0ms
memory: 9604kb

input:

7 21
4 1
2 5
0 6
0 4
0 2
5 3
0 4
1 0
0 6
0 2
0 5
3 0
4 1
6 4
2 4
4 5
4 3
6 1
1 2
1 5
1 3
2 6
5 6
3 6
2 5
2 3
5 3

output:

6291457 4 4194309 7 2097155 2097158 2

input:

Interaction has been finished!

output:

1
0
1
1
1
0
1
2
2
2
2
2
2
2
2
2
2
2
1
1
1
6291457

result:

points 1.0

Test #10:

score: 8
Accepted
time: 0ms
memory: 9544kb

input:

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

output:

6291457 7 4194310 2 8 5 3 6291460

input:

Interaction has been finished!

output:

1
1
1
1
0
1
1
2
2
2
2
2
2
2
2
2
2
2
1
1
0
0
2
1
0
2
2
2
6291460

result:

points 1.0

Test #11:

score: 8
Accepted
time: 0ms
memory: 9548kb

input:

6 15
0 3
1 4
1 5
4 2
0 1
1 0
0 5
4 0
0 3
0 2
1 5
4 1
1 3
2 1
5 4
3 5
5 2
3 4
2 4
3 2

output:

6291457 4194307 6 2 2097157 4

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
6291457

result:

points 1.0

Test #12:

score: 8
Accepted
time: 0ms
memory: 9656kb

input:

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

output:

4194305 2 2097155 4

input:

Interaction has been finished!

output:

1
1
1
2
2
0
4194305

result:

points 1.0

Subtask #2:

score: 92
Accepted

Test #13:

score: 92
Accepted
time: 76ms
memory: 10520kb

input:

700 244650
407 643
680 336
573 208
466 455
159 648
575 549
50 567
251 211
211 481
530 513
136 334
112 492
175 396
643 483
265 132
20 160
174 550
251 90
99 236
579 374
670 613
495 379
251 170
652 61
495 467
27 317
202 484
420 592
542 354
565 650
35 88
216 681
277 219
299 171
220 647
418 433
434 660
2...

output:

23068673 2098505 196 322 2097194 4195529 2097215 1397 1122 85 4194470 1348 449 2097745 47 2097351 1272 2097162 11 710 4195417 10486041 398 1223 1091 1058 771 4194882 523 91 2097866 163 4194318 174 2097181 10487007 342 757 1089 573 6292850 434 321 2098417 2097189 4195113 354 361 1266 2098204 4194841 ...

input:

Interaction has been finished!

output:

0
0
0
0
1
0
1
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
1
1
1
0
1
0
0
0
1
0
0
0
0
1
...

result:

points 1.0

Test #14:

score: 92
Accepted
time: 58ms
memory: 10508kb

input:

699 243951
59 192
191 301
270 524
135 496
647 573
174 262
662 43
371 50
655 434
123 242
209 46
612 646
11 533
156 443
322 462
329 558
417 383
283 263
615 504
29 520
391 135
546 535
54 264
382 651
541 427
536 456
295 169
645 303
494 21
282 179
329 490
191 67
697 55
226 276
32 160
226 482
392 56
144 1...

output:

23068673 694 2097941 869 327 2097586 296 4195188 4195166 2097979 4195576 23068706 388 4194835 695 4195437 1263 1227 954 2097539 8389838 542 768 2097271 2097316 134 4194394 4195405 785 4194404 424 6292753 6291675 8389014 4194610 170 6292004 1000 2098116 2098162 501 1237 8388703 988 1240 12584022 13 2...

input:

Interaction has been finished!

output:

1
0
1
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
1
1
1
0
0
1
1
0
0
1
0
0
...

result:

points 1.0

Test #15:

score: 92
Accepted
time: 72ms
memory: 10508kb

input:

700 244650
32 619
369 483
58 148
484 103
190 630
589 659
90 204
515 464
215 254
688 658
454 3
286 582
158 246
90 164
648 13
602 240
237 8
36 620
31 558
515 560
302 39
373 418
288 388
50 516
26 514
190 467
190 439
600 35
258 421
148 214
251 111
50 62
10 530
624 466
666 637
666 692
285 650
137 686
280...

output:

23068673 486 1313 1214 12583667 6291691 1156 1540 2097794 2097915 10486172 6292080 252 1327 2097570 374 455 1542 8388958 8389241 746 2097239 2098210 1365 200 356 2097697 1223 600 2097558 1329 10487123 2098531 4194315 1307 2098409 6291553 1102 556 4195055 10486007 404 1411 8390115 4195349 2098484 209...

input:

Interaction has been finished!

output:

1
1
0
1
1
1
0
0
0
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
1
1
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
...

result:

points 1.0

Test #16:

score: 92
Accepted
time: 70ms
memory: 10516kb

input:

700 244650
230 624
291 145
565 474
12 535
152 335
438 692
136 13
199 155
255 47
546 152
293 254
427 131
71 388
31 231
124 522
503 23
320 545
322 480
674 535
247 415
301 163
226 63
560 367
361 103
391 149
483 661
262 632
337 79
45 59
182 489
526 425
275 369
256 598
42 487
125 63
661 23
181 152
366 29...

output:

25165825 1134 482 6291922 1135 185 2009 1940 4196054 12584454 1308 6292724 6291857 6293041 4194413 14681092 12584073 10487631 6293205 6293360 6291635 341 4194780 12584717 4194575 4194611 10486986 246 1332 1186 1656 1229 10486225 154 4195946 4194418 407 1099 10485798 4194640 2019 6293426 1098 1048679...

input:

Interaction has been finished!

output:

1
0
1
1
0
1
1
0
1
0
0
1
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1
1
1
0
1
0
0
1
0
1
0
1
...

result:

points 1.0

Test #17:

score: 92
Accepted
time: 122ms
memory: 12480kb

input:

250000 250000
98377 99261
85304 211210
196850 193036
80796 130416
3160 72100
145991 142897
200915 46448
218676 213491
89680 96159
73896 8598
61659 226081
22401 122629
228272 20662
17177 215756
118511 136128
95692 43162
78229 30135
134970 150179
163578 188576
213241 99059
203107 94390
139934 51361
18...

output:

44040193 5288803 2750735 1303194 993344 336976 75990 989407 3201023 1010617 308640 896025 2973802 989953 358947 348380 5486680 111312 3017907 4195811 2957900 2263015 167705 349920 2869547 1271283 4378358 1022900 792272 2456833 3085225 1400426 87569 1469613 14870008 5114265 9429484 687409 1473498 316...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #18:

score: 92
Accepted
time: 116ms
memory: 12472kb

input:

250000 250000
58662 187031
88005 38197
22682 178770
111851 15764
207630 198631
64191 185171
168598 129456
142337 237430
215849 182270
211116 93208
20 204879
130122 42963
11672 121189
75991 33257
87185 128123
33289 2936
144056 47212
140138 18041
2913 20891
194901 213077
39452 3187
187440 25628
73551 ...

output:

44040193 2344932 177207 1514469 1124263 212877 8785677 6399171 498173 206100 4475692 5569057 2246627 6387869 4408207 14897158 183929 1392507 7584835 9960905 7466163 143245 3370378 72619 1614105 7437010 2474137 4269887 5586696 2354546 5370403 3771 3612480 1664177 176234 408223 2526767 3766367 154815 ...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #19:

score: 92
Accepted
time: 118ms
memory: 12548kb

input:

250000 250000
212557 2865
205598 91456
106547 166169
2385 60328
54909 26698
82002 112166
121929 240217
123410 133417
93989 61456
92642 225604
49143 8681
1263 131585
214794 141276
12589 67655
51160 187118
83743 12235
86483 172453
29872 111146
249757 78807
216189 2378
57530 180918
106038 234952
16366 ...

output:

44040193 1175654 8436190 9595985 718734 5101649 306952 1136666 4831691 209559 353104 782235 2990221 15542335 1120857 6344421 8741552 7468031 856191 562850 189080 500780 1149158 490133 714986 6344456 6519361 2721797 875829 1057657 1059654 304163 824903 5456186 2659061 410785 5431085 893869 1074687 77...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #20:

score: 92
Accepted
time: 140ms
memory: 12532kb

input:

250000 250000
108989 180679
6618 123314
146792 97095
101695 18624
109138 21259
130176 235020
131970 224224
32023 110376
126943 90247
7024 8229
55250 106561
44259 206501
157785 107293
88446 38793
62937 119441
158397 243678
83221 104131
184687 105512
101778 195126
76695 8559
31678 182822
58730 237755
...

output:

44040193 744303 5194884 4206758 21143601 5237968 76964 450032 299525 772771 647854 785205 572905 187820 249132 173248 14745644 224467 5247 6701801 309768 904112 378602 959614 221629 705415 4742962 6955616 510700 6727456 841743 680983 10854709 4402464 6979507 199995 324277 4862925 13288323 4782747 57...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #21:

score: 92
Accepted
time: 104ms
memory: 12476kb

input:

250000 250000
128536 214028
128536 203182
145589 67326
128536 148506
128536 118881
128536 221940
128536 82743
128536 76287
128536 207959
128536 126237
128536 33353
143121 245162
128536 140279
128536 149583
128536 146645
119187 41695
128536 122057
128536 1126
128536 97289
239043 83867
17254 163707
12...

output:

39845889 189671 156946 117088 290368 98405 275875 230930 100997 167805 251802 213479 237019 269710 126215 136021 286992 133017 169314 241387 188082 131027 100034 102705 209286 247510 113570 263636 187956 158046 148735 97181 120930 179006 168497 300297 11810 82734 290715 125693 152572 219873 2115126 ...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #22:

score: 92
Accepted
time: 124ms
memory: 12548kb

input:

250000 250000
198759 59913
198759 106050
198759 138903
198759 182095
198759 99282
198759 26662
198759 143423
198759 119590
198759 110285
198759 106764
198759 187588
198759 232194
198759 183411
198759 74226
198759 26210
198759 37134
198759 20394
198759 175287
198759 190555
198759 165099
198759 54430
...

output:

37748737 68317 183201 171711 149240 14460 105569 56619 71328 56787 172069 225445 14166 201126 15576 164489 184519 243479 39664 97694 190534 102783 112909 178541 138099 100743 193049 146662 246866 233188 128200 92512 56750 124207 81686 210523 39783 104094 203836 55459 36902 151163 152804 242025 17731...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #23:

score: 92
Accepted
time: 114ms
memory: 12468kb

input:

250000 250000
184772 157900
184772 132155
184772 166876
184772 64405
184772 137509
184772 4522
184772 200709
184772 35336
184772 206423
184772 164177
184772 75085
184772 43926
184772 203078
184772 111955
184772 143339
184772 48472
184772 203381
184772 124891
184772 53181
184772 233575
184772 191324
...

output:

37748737 134800 20111 57129 6893 94835 148496 174193 167917 214830 163683 70764 199289 206561 88177 81943 2318 231106 231962 48150 108285 218710 204944 240420 236485 166451 19678 223314 172617 61063 196055 170545 192082 94789 160281 20312 95170 2286 162762 24761 28201 28617 140213 186569 202373 2086...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #24:

score: 92
Accepted
time: 132ms
memory: 12464kb

input:

250000 250000
230824 15636
230824 208607
230824 150840
230824 175213
230824 27372
230824 196695
230824 235943
230824 201709
230824 37092
230824 220813
230824 77183
230824 86286
230824 239581
230824 119137
230824 63155
230824 10112
230824 180498
230824 15837
230824 147783
230824 244036
230824 176382
...

output:

37748737 158416 209645 69143 202331 9448 209889 57739 103007 141386 59851 2025 236042 161098 65482 95858 172193 145912 217070 164340 11860 29982 65607 130348 200067 20945 249612 42177 156160 102795 99703 80399 72966 199675 78512 101610 47961 198539 7556 52692 158438 240647 113330 189924 15942 38450 ...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #25:

score: 92
Accepted
time: 124ms
memory: 12484kb

input:

250000 250000
58738 89012
241722 74087
241722 58508
241722 195367
117601 155982
210156 8731
241722 133766
26861 91965
241722 172806
241722 205939
147422 190803
122741 188023
34509 198117
241722 237277
236733 191382
235687 182460
218974 217284
213346 156152
241722 134502
241722 28571
241722 31231
117...

output:

41943041 15066100 627656 541107 437808 585780 570992 575190 2200714 455146 551239 528928 536876 307753 590047 582913 623870 10661512 577191 15690 220194 547622 6741204 2126999 638124 39641 30492 4677797 10805643 564051 596750 15197754 254415 611076 634989 643780 567610 509367 593474 539424 2533228 2...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #26:

score: 92
Accepted
time: 126ms
memory: 12472kb

input:

250000 250000
26495 54804
17692 109008
175459 12105
214482 13746
240824 131046
65255 113217
55284 75717
149186 198846
77755 108551
161766 100260
200089 208052
79927 67803
166414 91318
49019 16638
50859 113603
112174 66033
82811 201503
95187 31323
55284 191032
168776 146425
55284 243899
55284 109360
...

output:

41943041 4897198 627395 4549040 821983 4350538 2814919 833776 837800 9025158 498477 610836 2594731 6521977 11189984 2876627 810564 8440 9126555 8449257 693598 10810137 651861 720639 269217 4938236 76165 857691 266794 156860 19585303 260798 4938044 541543 2766909 26767 27857 2484835 8639641 2274015 7...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #27:

score: 92
Accepted
time: 62ms
memory: 10496kb

input:

700 244650
275 683
22 179
393 371
237 435
143 394
557 333
541 230
98 280
585 410
289 526
96 82
594 616
228 632
579 661
608 432
442 562
653 561
39 439
401 676
444 681
509 178
94 106
281 608
83 133
71 443
336 396
547 221
133 254
230 498
161 29
492 669
340 312
347 97
191 342
501 573
487 409
611 670
180...

output:

23068673 36 6292384 21 1098 6291541 893 730 270 750 4194434 365 2097205 4194352 1202 40 374 77 6291759 650 4195215 4195504 6292433 407 6292629 13 983 4195374 1155 4195014 10486073 6291522 18 4194885 2098082 1103 6 14680488 1257 14680123 94 324 4195246 476 702 1326 1061 2098246 828 4195564 37 432 209...

input:

Interaction has been finished!

output:

1
1
1
1
1
1
1
1
1
0
1
0
0
0
1
1
1
1
1
1
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
1
1
0
1
1
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
1
0
1
1
0
1
1
1
1
1
1
0
1
0
1
1
1
0
0
0
0
1
0
1
1
1
1
1
1
1
1
0
0
0
1
1
0
1
1
0
1
1
1
0
1
0
0
1
...

result:

points 1.0

Test #28:

score: 92
Accepted
time: 72ms
memory: 10500kb

input:

700 244650
196 541
32 593
557 166
621 105
508 313
485 554
19 348
240 259
569 527
632 184
512 470
648 185
337 22
508 353
216 471
184 608
435 326
515 458
21 521
295 239
209 258
385 364
46 171
76 672
133 219
188 260
41 691
237 575
425 67
314 136
386 281
12 197
560 230
343 568
445 618
537 146
118 628
24...

output:

23068673 480 475 18875758 172 269 34 2098399 8390185 2097185 515 6291464 4194905 4195706 229 1217 242 4195558 683 4194988 2098802 4194649 166 1519 587 1351 6292965 360 8389095 145 2098552 187 10485987 1568 4195815 2097303 4194574 599 1287 1670 8388890 10487265 1267 1295 2098707 4194492 12583236 679 ...

input:

Interaction has been finished!

output:

0
1
1
1
1
0
1
0
1
1
0
1
1
0
1
0
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
1
1
0
1
1
0
0
1
0
0
1
1
1
1
0
0
1
0
1
0
1
0
0
1
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
...

result:

points 1.0

Test #29:

score: 92
Accepted
time: 62ms
memory: 10628kb

input:

700 244650
592 352
634 56
500 199
138 39
242 322
130 457
673 471
9 518
342 498
30 580
199 675
341 437
10 42
623 556
9 595
571 363
680 303
638 685
628 334
219 488
6 501
284 18
511 520
607 102
437 618
234 667
561 224
299 291
386 607
584 171
140 166
679 285
559 393
570 546
64 81
361 110
510 117
519 467...

output:

23068673 2098505 6292837 12583088 1067 262 6291652 12584076 2098294 10486369 4194715 1267 2097708 117 8388880 758 111 624 633 537 6292204 1291 394 592 6292133 254 602 2098420 4195701 4194822 8389927 2097672 1133 4195024 401 1293 4194459 6292520 16777792 2097833 2098276 4195018 412 299 4194934 209771...

input:

Interaction has been finished!

output:

1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
0
1
0
1
1
1
1
1
0
0
1
1
1
1
0
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
1
1
0
1
0
0
1
0
0
0
0
0
1
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
1
0
1
1
0
1
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
0
1
0
0
1
0
0
1
1
0
0
0
0
...

result:

points 1.0

Test #30:

score: 92
Accepted
time: 124ms
memory: 12592kb

input:

250000 250000
110488 29915
32503 19122
163234 216779
32503 244838
32503 56235
40340 188891
32503 63368
32503 62093
32503 21241
156372 239088
86337 206334
32503 107656
186415 11721
32503 19412
1401 170501
238830 1975
32503 2536
32503 92576
146518 16823
50563 21743
32503 103708
70942 36214
52807 18384...

output:

37748737 46924 154156 97018 2128549 2149567 2280605 35904 2126307 2210021 16024 4598 2212709 205532 2167683 2212921 2249081 59322 2221313 2174303 247056 2301823 163462 28610 161286 2152181 226928 2274475 2128457 10388 2110595 2169711 2148987 4452931 2129619 2117977 2296917 2125107 2097755 2181173 50...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #31:

score: 92
Accepted
time: 126ms
memory: 12472kb

input:

250000 250000
56463 84241
17929 232104
78818 231179
7763 119812
78818 216137
78324 54969
78818 53079
195671 35431
112104 106560
39189 167309
78818 155903
113437 200963
78818 237821
123567 124204
78818 147909
78818 187029
78818 186742
78818 118534
100212 204834
148444 245654
61970 65024
25750 71621
7...

output:

37748737 205216 115366 2219041 157644 189934 2181149 2255889 2118581 53688 225436 29102 144690 184042 134142 53372 19014 21022 239466 2107771 117410 43864 218614 248086 97264 233596 2286137 105642 103446 12696 123576 2308121 2337185 246299 2247693 2153931 177854 2137617 2148343 169728 2122925 224800...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #32:

score: 92
Accepted
time: 128ms
memory: 12456kb

input:

250000 250000
246615 82684
47274 30232
139970 60613
210652 81239
179019 172038
41407 219436
132076 211714
29055 38907
49098 236568
48167 185138
47274 170520
47274 574
87166 134649
18240 198023
47274 32445
28748 188954
177984 156977
227404 152029
95667 40783
47274 237786
47274 57531
47274 110575
4727...

output:

37748737 228775 112675 198891 2176734 2296114 10957 98759 181293 244479 2214556 2146952 72597 115833 118751 2173914 2110902 35281 2220624 203431 2292914 35091 2195558 2330940 119763 177365 2176874 2258952 2312936 2232764 47799 232761 2222984 143603 242535 2107036 2171466 2337178 193393 2299604 20766...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #33:

score: 92
Accepted
time: 118ms
memory: 12588kb

input:

250000 250000
169779 129784
65198 110053
158373 24761
66653 10729
75121 98520
225514 227184
130625 47045
145713 42773
75121 130333
75121 2813
75121 240810
75121 90074
222329 218563
59360 201210
81564 72860
236207 96937
79551 226435
14469 249307
222141 72356
88298 101110
75121 208318
75121 105396
484...

output:

39845889 4393572 292121 179261 256299 4416484 42247 148510 4432400 46951 229123 1341 224727 2144446 304002 266074 2187612 153205 232317 85257 78783 310191 208337 249131 270363 2181776 163681 2188208 2169198 280449 70397 4416780 2187600 56715 282937 2200986 2183922 2208430 2144914 128937 52751 201985...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #34:

score: 92
Accepted
time: 122ms
memory: 12480kb

input:

250000 250000
41598 211819
178057 8902
41598 25261
159032 170814
178057 51128
108989 52376
178057 120123
33050 191946
162642 212013
41598 26096
127315 209050
182576 43473
178057 120314
41598 46174
140237 131578
166787 88256
178057 208477
228075 235006
2102 72773
11150 206322
179976 14367
181499 7399...

output:

39845889 2155802 4250769 290921 1291 2287666 4206741 293477 4358489 4228057 2167554 4331929 2267650 128103 2375338 2115186 82931 4318965 4274245 2254710 4291385 2294674 2362570 2124814 2329530 137627 2330200 2159302 2313988 4371961 183007 2346940 289785 2298340 164119 2273470 199997 2157458 87483 42...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #35:

score: 92
Accepted
time: 136ms
memory: 12468kb

input:

250000 250000
163081 132781
63469 11856
30855 50874
182965 210480
165909 208529
182965 69949
19082 85721
145102 24549
63469 98663
63469 230902
182965 247893
91712 244743
182965 246142
63469 92012
51907 109391
111901 86904
63469 12300
104476 112270
35238 54337
52549 37141
182965 87396
130391 140516
6...

output:

39845889 4267453 144523 2310220 4384765 178071 4221665 2101774 2230198 225243 149503 2193606 2360086 239373 2142546 4314697 2233694 21963 4216901 254611 260507 2258958 162727 4331817 2366216 2135874 5475 4295841 2191766 4286565 4376357 4273933 4258421 4196973 265597 2143458 4228529 18575 199489 2465...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #36:

score: 92
Accepted
time: 132ms
memory: 12472kb

input:

250000 250000
209695 203761
124115 27828
226002 88019
177206 117980
53014 34658
79947 249040
192420 90387
105823 50440
227710 118147
68838 70284
192420 168744
28455 61505
2311 93146
192420 12190
103505 37947
211324 154894
212740 208321
132041 90447
48111 234924
192420 180290
192420 120196
104200 491...

output:

39845889 181217 4207680 2384160 272023 4407443 258749 176873 291139 4275165 249709 196453 2360914 275071 4268156 250441 2273496 4330970 217469 4225455 2216460 4308046 4283685 2343852 4265091 4307156 2338328 4243316 305366 4393843 170909 215065 4407423 2333384 206493 4224690 2224150 2352702 4431219 4...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #37:

score: 92
Accepted
time: 122ms
memory: 12480kb

input:

250000 250000
26171 185351
39348 11884
58623 154119
29392 210049
225461 13141
210462 239794
89337 158657
64038 226543
225461 165057
155662 236975
199438 169618
2656 123195
89755 217180
108157 40495
78088 16550
225461 101981
182908 74529
88887 167252
234346 52597
86586 112414
225461 73242
234252 2080...

output:

39845889 4360754 2394196 4383715 4322641 4437307 246109 294985 4325872 4495583 4377580 197458 50395 193993 6402567 4195736 70283 4448127 292525 329529 2245459 324373 47355 4325777 2419718 76299 323327 70827 338005 183938 112131 2319389 8587 2279499 151813 303771 127299 4421019 192973 4420755 2378596...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #38:

score: 92
Accepted
time: 114ms
memory: 12476kb

input:

250000 250000
110575 244888
185589 68626
9376 216813
144676 137788
100619 78212
211391 66989
35209 243254
20195 144006
196216 87366
185399 121645
194646 130354
54752 290
224640 85825
25675 41656
146244 90139
28927 68073
132399 6516
77706 91331
84625 151745
9376 84716
242992 193078
238102 220734
2181...

output:

39845889 305791 2176226 2169125 37477 4210394 2353799 294907 303719 4292862 2334649 283839 4368736 344747 2322564 4447670 10891 4433610 4201098 335005 4462289 6453886 6335066 6341772 75052 2321169 2318324 2389266 6489278 122130 2402950 4261425 331043 2250785 2442490 2117681 4509669 4501721 2188961 2...

input:

Interaction has been finished!

output:

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

result:

points 1.0

Test #39:

score: 92
Accepted
time: 126ms
memory: 12528kb

input:

250000 250000
243362 29519
185329 174397
40158 169929
115163 94741
41201 214325
91993 61762
227404 228662
200708 3028
176550 161431
243362 183064
202244 84426
231033 143840
220682 231042
144308 210950
33871 71003
179193 137456
124230 121297
199243 15562
9791 220563
92161 54686
127414 130262
127103 2...

output:

39845889 336455 257945 2419328 340827 4310926 2240446 6382595 6316329 6359834 2389077 6482146 4313326 174693 4487877 2427464 2413432 6299114 327801 4200976 2237446 62587 2434888 203430 4497177 6459646 6453455 2342600 4947 4397317 4412487 6542173 6319750 6420057 6435597 4410510 158781 6439466 341103 ...

input:

Interaction has been finished!

output:

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

result:

points 1.0
English 繁體中文 简体中文

Server Time: 2024-11-29 16:31:33 | OpenSource Project