QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300256#370. Cityzjy0001100 ✓134ms16092kbC++141.1kb2024-01-07 21:56:372024-01-07 21:56:38

Judging History

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

  • [2024-01-07 21:56:38]
  • 评测
  • 测评结果：100
  • 用时：134ms
  • 内存：16092kb
查看
  • [2024-01-07 21:56:37]
  • 提交

Encoder

#include"Encoder.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2.5e5+5;
const ldb BL=1.024;
vector<int>G[N];
int tim,dfn[N],sz[N],pwD[512];
inline void dfs(int u,int fa){
    dfn[u]=++tim,sz[u]=1;
    for(auto v:G[u])if(v!=fa)dfs(v,u),sz[u]+=sz[v];
    int k=lower_bound(pwD,pwD+512,sz[u])-pwD;
    sz[u]=pwD[k],tim=dfn[u]+sz[u]-1,Code(u,k+512ll*dfn[u]);
}
void Encode(int n,int*U,int*V){
    for(int i=0;i<n-1;++i)G[U[i]].push_back(V[i]),G[V[i]].push_back(U[i]);
    for(int i=pwD[0]=1;i<512;++i)pwD[i]=max(pwD[i-1]+1,(int)(pwD[i-1]*BL));
    dfs(0,0);
}
源文件, 语言: C++14

Device

#include"Device.h"
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const ldb BL=1.024;
int pwE[512];
void InitDevice(){
    for(int i=pwE[0]=1;i<512;++i)pwE[i]=max(pwE[i-1]+1,(int)(pwE[i-1]*BL));
}
int Answer(LL X,LL Y){
    int a=X>>9,b=pwE[X&511],c=Y>>9,d=pwE[Y&511];
    return a<=c&&c<a+b?1:c<=a&&a<c+d?0:2;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 4ms
memory: 11804kb

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:

521 3072 2050 4608 4097 1025 3587 1536 2560 5120

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
5120

result:

ok

Test #2:

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

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:

521 4096 2048 3072 5120 4609 1538 1028 3585 2560

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
5120

result:

ok

Test #3:

score: 8
Accepted
time: 4ms
memory: 13920kb

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:

521 4096 3584 2564 4608 5120 3075 2054 1536 1025

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
5120

result:

ok

Test #4:

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

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:

521 2048 4096 1026 3072 3585 5120 2565 1536 4609

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
5120

result:

ok

Test #5:

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

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:

521 4608 3072 5120 3584 2562 2048 1029 1537 4098

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
5120

result:

ok

Test #6:

score: 8
Accepted
time: 4ms
memory: 11876kb

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:

520 4096 4608 2563 2053 1536 3073 1025 3584

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
4608

result:

points 1.0

Test #7:

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

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:

521 3074 2560 5120 1538 1024 3584 2048 4096 4609

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
5120

result:

ok

Test #8:

score: 8
Accepted
time: 4ms
memory: 13996kb

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:

516 1536 2049 2560 1025

input:

Interaction has been finished!

output:

1
0
0
0
2
1
2
2
1
2
2560

result:

points 1.0

Test #9:

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

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:

518 2048 2562 3584 1537 3073 1024

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
3584

result:

points 1.0

Test #10:

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

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:

519 2560 2050 1024 3072 3584 4096 1540

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
4096

result:

points 1.0

Test #11:

score: 8
Accepted
time: 4ms
memory: 11980kb

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:

517 1539 2560 1024 2049 3072

input:

Interaction has been finished!

output:

0
1
0
1
1
1
0
2
0
2
2
2
2
0
2
3072

result:

points 1.0

Test #12:

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

input:

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

output:

515 2048 1025 1536

input:

Interaction has been finished!

output:

1
1
1
2
2
0
2048

result:

points 1.0

Subtask #2:

score: 92
Accepted

Test #13:

score: 92
Accepted
time: 68ms
memory: 11952kb

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:

696 243201 294912 99328 336897 184834 349697 254464 226304 361984 309250 244736 139264 16385 338944 297985 176640 329217 329728 82944 222211 148502 126464 186880 220672 200704 65536 11778 4608 357888 86017 307712 333314 303616 327169 165913 116736 68608 232960 13312 252934 143872 98816 172033 339969...

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: 66ms
memory: 11872kb

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:

696 199680 294401 183808 146944 78849 133632 176642 180738 159745 267267 1206 37888 39938 208384 224770 265216 261120 300544 37377 237580 50176 286720 18433 101377 30720 22019 211459 288768 26115 74752 254469 103942 94216 135682 344064 51718 313344 303105 320001 65536 240640 24584 327680 242176 2161...

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: 66ms
memory: 13908kb

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:

696 101888 251904 231936 51742 338438 302080 166912 25601 66561 107030 18950 331264 241664 108033 130560 106496 169472 119816 22540 68608 147969 280065 190976 349184 121856 79873 275456 16896 87553 246272 188946 195073 362499 253952 237569 140804 309760 33280 48131 319511 85504 217088 180235 313859 ...

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: 58ms
memory: 11880kb

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:

696 164864 360448 353798 165376 285696 120832 103424 56322 3102 177664 215046 337926 15366 265218 137278 218651 85518 55814 93702 283142 324096 357890 69150 306178 315394 203278 300032 182272 228864 33792 204800 353294 278528 28162 267266 340480 156160 246798 322050 124928 110086 155648 138254 25139...

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: 126ms
memory: 13912kb

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:

947 105896962 137307649 62290944 100408832 33192960 6584320 114337792 104389121 107437568 46699520 118832128 119631361 114315776 31619584 28110848 64884226 2528768 125551617 137871874 120782337 17521665 17078784 28942336 94506497 56222720 23288835 108699136 91229184 31690241 114953217 78274048 46714...

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: 134ms
memory: 15964kb

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:

948 122112513 71421952 34823680 827904 74552320 99369994 129674756 91501056 75730432 116872194 14311427 127782401 81723396 74733570 73892918 78936576 19184128 61639684 35709961 5486598 126127616 58806273 70608384 55033344 11019780 98269697 71050242 19168770 124510721 5596162 135692800 34677761 48630...

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: 124ms
memory: 14032kb

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:

948 98848768 22586377 103043591 62538752 122081282 17216512 95674880 49912322 30982656 11462144 87260672 121628161 131836485 102600192 23667207 11722761 99277318 131489280 41900544 38753792 69665792 92620800 72115200 61931520 23679492 30372868 47035905 129456128 119592448 120476672 16628736 13452339...

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: 120ms
memory: 13920kb

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:

950 101760512 139739650 27807746 5720715 145735170 22926336 58268160 36590080 105747456 87573504 107450880 76882944 7919616 16678912 5893632 21374526 13179392 26819584 52778502 37974528 125530624 47828992 133842432 12833280 96190464 73516546 90381318 66985984 56374278 116627968 92748800 46439950 109...

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: 116ms
memory: 14028kb

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:

957 98902528 116762112 61711872 34138624 88138240 55040000 3145216 87639040 93213696 50215936 30285824 13568000 59076096 74055168 69720064 32270336 70345216 96094208 15776256 96374784 68960768 87286784 83231744 27999232 11746816 67103744 57652224 96226304 111481344 105456640 86275072 62441984 100747...

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: 128ms
memory: 13976kb

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:

960 117473792 15272448 4067328 31672320 81853952 102355968 79149568 118891520 79761408 4134912 37024768 81827328 48676864 80073728 7764992 10625536 46598656 69014016 122489344 11570176 102793728 98594816 13505536 18388480 99846144 52617728 28836864 41896960 33068032 106547712 119929344 79835648 1038...

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: 122ms
memory: 13924kb

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:

961 17572352 95201280 72325632 86061056 101143552 30733824 12395520 566272 56706048 7021568 113300480 48717824 60932096 121591296 124486656 85591552 35447808 36010496 77092352 98017792 58692608 61509120 46334464 45662208 315392 92482048 39418368 13117952 74245632 49068032 2442752 55423488 100979712 ...

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: 120ms
memory: 13848kb

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:

961 4320256 62012928 118208000 50769408 81613824 62137856 72876032 97928704 29219328 75800576 84343808 45565440 7193088 116833280 100360704 13468160 31911424 58471936 1480192 83379200 90034176 116764160 23943680 51234304 95904768 42608640 64783360 26661888 97788928 102368768 124439552 112010240 5144...

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: 128ms
memory: 13932kb

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:

952 23427116 57868800 64214016 25314816 39251456 80765440 78740992 134752257 108459008 65422848 70979584 74273280 10035712 37690880 82616832 59681792 126586396 83705856 275456 120934912 68865024 109505028 154627585 47017984 144261632 154924032 26965507 10569752 92929536 42121216 28326472 112822272 3...

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: 128ms
memory: 13916kb

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:

949 107427842 55408640 36090882 84312576 140357122 60163073 90056192 72743936 54565899 129359360 112048640 128796673 23451652 106432529 64480769 86092800 1373184 62762505 9523209 105017856 45618191 55998464 59824640 28411392 103990786 8698368 78612992 27781632 140518912 60699266 26890240 103877634 1...

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: 56ms
memory: 11880kb

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:

696 356352 154631 365568 295424 328708 176128 87552 113152 90624 349699 117760 321537 319490 189440 316416 121344 337408 3078 74240 168962 188418 261638 129536 239620 361472 264192 283139 184832 107010 7697 324612 364032 66562 157697 301568 313856 18992 209920 323646 331776 10752 161283 39936 105472...

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: 66ms
memory: 13916kb

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:

696 118272 120832 228480 189952 38912 4608 359937 270345 4097 111104 25093 163843 330754 83456 194560 78848 355843 127488 128002 256513 67586 187392 300544 168960 217600 304133 64000 174601 185856 333313 86016 73237 277504 305155 31745 39939 167936 350720 249344 44046 297490 353792 346112 268289 180...

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: 58ms
memory: 14040kb

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:

695 159233 184326 3624 261120 52736 7684 213543 239617 291350 80386 194560 274945 98304 27661 334336 102400 300544 299520 289280 325637 206848 87552 312832 349701 37376 309248 193025 181762 358915 160778 359937 235520 317443 83456 208384 111106 259588 290920 351745 243201 319491 80896 48128 297987 2...

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: 120ms
memory: 13984kb

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:

960 77450240 2903040 96944640 65465345 69669377 58333697 61987840 66752001 22089729 90417152 85698048 21578753 38616064 125288961 21712897 4184577 116016640 20874241 126650881 52361216 39279105 8483840 66014720 9797120 71332353 122738688 44431873 65520641 78299136 80452609 123914753 69281793 8029286...

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: 122ms
memory: 14036kb

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:

960 62968320 110890496 106238465 4887040 55019008 126237697 7332353 94130689 78367232 33976832 90199552 31706624 10574848 16146944 78529536 92367872 95418880 46311936 79958529 105803264 67663360 36541440 26560512 103014400 45103616 52573697 99672576 96050176 83654144 106620928 55941121 41910785 9461...

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: 126ms
memory: 13920kb

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:

960 32444928 108923904 48713216 125571073 48613377 80793088 103804928 9708032 40144384 105499137 76821505 112402944 110055424 105560064 114031617 82363393 71262720 106078209 61395968 49002497 68670464 103233537 34629633 104041984 15723520 125561857 7760385 59746817 16181761 77159936 34140160 2119526...

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: 128ms
memory: 13924kb

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:

958 26923522 55608320 54178304 36042240 113914883 69955584 124454400 25099267 84698112 96675840 173025792 54270976 84380673 74134016 90288128 104532993 6688768 71586816 86813696 120833024 94029824 63282176 109048320 14249984 86731265 111036928 97233409 108702721 41805824 106268672 114253827 10450790...

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: 124ms
memory: 16092kb

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:

959 66934273 67578882 84444160 50769920 27555841 55403010 88983552 37649922 38302722 124548609 7321602 35082241 4482560 90453505 56383489 57557504 3455490 61084674 28925953 63863298 25277953 72032769 40786945 119805441 7322624 119553537 127262721 101210625 23584770 20814848 79943169 84520960 1029463...

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: 112ms
memory: 14040kb

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:

959 125733890 57799168 33555969 81420290 76645888 93837314 105085953 568321 52480000 84459520 116848641 6819841 44062720 95992833 67616258 1632769 107345920 107589122 16907264 14860800 89483265 89539072 61051394 9957377 99170817 104591872 64773122 115862529 118537730 72136706 113687042 126812162 103...

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: 114ms
memory: 15968kb

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:

958 84368896 39503875 87793665 106641920 52286978 100301312 120534528 97128960 14192643 104049152 59026432 111144961 108654080 7748098 104719872 122478593 19277827 55849984 32778243 26389505 26782210 3495939 64530945 8890882 27175426 63084033 125276674 90412032 57756674 117516288 55528960 52294658 6...

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: 128ms
memory: 13924kb

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:

958 84033027 26504705 9478146 98547714 33445378 35888640 27935232 97423363 28124674 81778690 11052032 127766016 11312128 104301572 114831363 122735616 63053826 31699968 45817344 76706305 41646080 130164736 97454594 40437249 90963456 42181632 122917376 43795456 81509376 102665216 14359041 114418176 8...

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: 128ms
memory: 13928kb

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:

957 63436288 3806209 1385473 131660288 21318659 52953089 90375680 67179520 11212290 102584833 87408128 32019970 74629120 97634817 50101762 120035840 104833026 24898050 79247360 57998339 30654468 123553797 125839876 34304 98167297 97004033 93935617 40116228 47575552 63438849 7528962 80171008 49264641...

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: 128ms
memory: 13924kb

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:

955 76579328 47645696 65690625 77126144 5461507 8555521 15190534 131189766 115891206 54709761 23257605 7816195 39566336 54487555 69384705 82418177 122985478 64981504 124322818 13849089 114186240 75012097 33204224 55566851 94586885 33739780 42522625 123828224 32695811 87037442 40690692 130595846 4378...

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 繁體中文 简体中文

服务器时间: 2024-11-29 12:32:08 | 开源项目