QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113623#2766. Unique Citieslmeowdn100 ✓173ms49812kbC++142.8kb2023-06-18 22:08:352023-06-18 22:08:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-18 22:08:35]
  • 评测
  • 测评结果：100
  • 用时：173ms
  • 内存：49812kb
查看
  • [2023-06-18 22:08:35]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=2e5+5;
int n,m,h[2][N],r[2],f[2][N],d[2][N],mxd,a[N],cnt[N],son[2][N],cur,id[N],anc[2][N];
vi e[N];

int find(int i) {return i==id[i]?i:id[i]=find(id[i]);}
void del(int r,int x) {
  cnt[a[x]]--; id[x]=find(anc[r][x]);
  if(!cnt[a[x]]) --cur;
}
void add(int x) {
  cnt[a[x]]++; id[x]=x;
  if(cnt[a[x]]==1) ++cur;
}
void mdf(int rt,int u,int l) {
  for(int x=find(u);x&&d[rt][x]>=l;x=find(x)) del(rt,x);
}
void dfs1(int u,int fa,int dep) {
  if(dep>mxd) r[0]=u, mxd=dep;
  for(int v:e[u]) if(v!=fa) dfs1(v,u,dep+1);
}
void dfs2(int r,int u,int fa) {
  h[r][u]=0, d[r][u]=d[r][fa]+1;
  for(int v:e[u]) if(v!=fa) {
    dfs2(r,v,u), chmax(h[r][u],h[r][v]+1);
    if(h[r][u]==h[r][v]+1) son[r][u]=v;
  }
}
void dfs3(int r,int u,int fa) {
  id[u]=u; cnt[a[u]]++; anc[r][u]=fa;
  if(cnt[a[u]]==1) ++cur;
  if(son[r][u]) {
    int smx=-1, mx=h[r][son[r][u]];
    for(int v:e[u]) if(v!=fa&&v!=son[r][u])
      chmax(smx,h[r][v]);
    mdf(r,fa,d[r][u]-smx-1);
    dfs3(r,son[r][u],u);
    mdf(r,fa,d[r][u]-mx-1);
    if(find(u)!=u) add(u);
  }
  for(int v:e[u]) if(v!=fa&&v!=son[r][u]) {
    dfs3(r,v,u);
    if(find(u)!=u) add(u);
  }
  del(r,u); f[r][u]=cur;
}

signed main() {
  n=read(), m=read();
  rep(i,2,n) {
    int u=read(), v=read();
    e[u].eb(v), e[v].eb(u);
  }
  rep(i,1,n) a[i]=read();
  dfs1(1,0,0);
  dfs2(0,r[0],0);
  dfs3(0,r[0],0);
  rep(i,1,n) if(d[0][i]>d[0][r[1]]) r[1]=i;
  rep(i,1,m) cnt[i]=0; cur=0;
  dfs2(1,r[1],0);
  dfs3(1,r[1],0);
  rep(i,1,n) {
    if(d[0][i]>d[1][i]) printf("%d\n",f[0][i]);
    else printf("%d\n",f[1][i]);
  }
  return 0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 1ms
memory: 18420kb

input:

2 1
1 2
1 1

output:

1
1

result:

ok 2 lines

Test #2:

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

input:

1842 848
740 1093
1299 922
801 1560
265 1664
1043 65
1430 427
80 233
4 1238
1623 1473
1569 274
953 1485
1259 649
1671 1409
246 542
742 1517
720 1120
1527 1328
1167 1531
1056 1130
673 1222
192 980
1393 913
446 688
135 23
1065 1787
978 1481
1765 1720
310 202
1406 1451
475 523
104 774
1531 829
169 396
...

output:

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

result:

ok 1842 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 18296kb

input:

951 908
777 679
676 510
34 425
424 889
78 4
924 408
151 905
399 942
606 776
275 332
616 900
513 372
911 130
465 430
126 303
380 603
506 505
592 38
917 270
435 815
591 773
63 66
417 642
301 693
814 454
735 671
899 674
925 846
254 898
845 569
703 659
707 241
482 715
646 282
274 925
861 374
699 488
903...

output:

302
286
491
486
478
563
380
32
497
563
115
30
581
428
510
491
374
565
242
418
469
550
410
229
499
386
274
588
487
276
279
536
445
203
483
56
565
361
129
140
533
437
229
68
442
559
570
502
493
212
588
96
330
405
262
526
464
516
258
541
554
264
475
441
544
476
406
222
468
397
531
591
406
39
320
198
60...

result:

ok 951 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 15992kb

input:

1817 365
1516 74
1811 1805
1036 311
1769 1663
1029 473
1596 310
337 888
324 426
385 315
1780 1684
1750 794
895 1029
1108 1194
566 613
489 1230
1727 1520
170 302
731 1171
591 295
1165 1233
304 835
1607 404
1035 1675
158 735
1553 1764
1390 1078
197 980
1176 1626
16 1218
1530 1146
1692 1477
1513 574
32...

output:

0
129
0
0
0
224
1
203
0
0
0
0
229
0
239
0
1
0
0
0
162
0
0
0
0
113
1
0
0
0
0
200
208
0
218
0
2
0
72
0
161
0
0
195
0
0
0
33
0
132
0
0
1
0
146
118
147
0
66
0
0
70
240
177
0
165
0
4
0
1
3
68
243
2
1
2
0
1
0
0
230
208
0
250
12
3
195
0
69
0
0
6
1
114
218
0
0
199
0
0
0
0
1
27
157
1
0
0
0
1
0
163
1
0
1
168
...

result:

ok 1817 lines

Test #5:

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

input:

2000 5
1695 1417
623 8
1319 1473
329 1662
879 1654
108 555
1765 1258
1808 962
893 532
779 664
1507 1612
435 250
1645 349
666 992
921 24
1343 1974
50 1258
1497 2000
1156 1076
227 1921
413 543
737 294
218 554
1735 32
234 1718
1615 1126
1620 1915
1722 10
1031 871
871 674
626 1527
1792 148
101 1837
893 ...

output:

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

result:

ok 2000 lines

Test #6:

score: 0
Accepted
time: 5ms
memory: 18512kb

input:

2000 6
462 1865
693 166
1818 5
444 1736
1133 1670
1356 760
1732 919
1485 126
1655 1476
957 1185
343 1431
968 52
1595 764
1541 1498
1729 1457
558 387
1458 480
1199 1759
979 1230
512 700
278 1058
1894 496
191 1524
411 103
415 1628
1524 715
41 1128
291 1115
1599 1613
114 1990
564 1439
805 1273
504 1051...

output:

6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
...

result:

ok 2000 lines

Test #7:

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

input:

2000 3
246 351
568 1925
1167 1934
847 1223
1203 894
1076 1886
1394 1834
704 1777
1483 1744
40 963
619 509
1738 212
1498 77
286 144
1946 456
626 647
1653 658
1216 1418
29 1320
754 1874
667 1585
457 589
1784 1793
1788 1104
488 818
1452 224
1259 1855
653 1931
1253 1413
1352 227
1919 122
1675 563
767 19...

output:

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

result:

ok 2000 lines

Test #8:

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

input:

2000 8
1053 321
1821 1638
946 445
1686 570
532 192
1306 987
70 1362
1564 1337
737 1540
1686 1533
1776 1864
1212 1891
476 1618
1031 815
883 939
1487 177
1659 1116
794 434
473 1040
1867 1424
108 1095
1788 1612
791 937
958 1545
161 1053
1594 1053
668 1900
918 1270
889 1119
635 1747
1126 271
420 551
572...

output:

1
1
2
2
2
1
4
1
3
2
2
3
1
1
1
1
1
3
2
3
1
2
1
1
3
2
1
1
1
2
2
3
1
1
2
2
2
3
3
2
2
3
3
1
1
1
1
2
1
3
1
4
1
1
1
2
2
4
2
2
3
4
3
1
1
2
3
1
2
1
1
2
1
2
1
3
2
3
3
2
1
4
1
2
2
1
3
1
1
2
1
3
2
3
2
2
2
1
3
2
1
2
2
3
4
1
4
2
2
2
1
2
2
3
1
3
1
2
1
3
1
2
2
2
3
1
1
1
1
2
3
1
2
1
3
2
1
2
1
1
2
1
1
1
2
3
2
3
2
1
...

result:

ok 2000 lines

Test #9:

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

input:

2000 10
1446 902
516 588
381 360
1588 766
1162 1333
951 1610
567 1665
329 998
527 1126
1770 1847
156 925
305 384
704 831
171 888
387 1139
450 904
341 1897
999 617
1643 1611
894 1636
57 1221
993 459
660 826
1336 1639
37 652
734 871
950 1234
254 1561
151 675
1585 230
1255 595
92 321
1711 913
1986 231
...

output:

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

result:

ok 2000 lines

Test #10:

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

input:

2000 4
1037 1229
171 1052
87 746
329 1413
1527 1925
1120 349
208 1815
535 1430
432 102
634 707
490 334
1139 933
1492 1110
907 1412
1480 197
324 926
1324 565
1638 937
1122 1238
823 87
387 1159
1261 1829
715 295
1822 1058
1595 1596
1525 1416
288 364
110 1536
137 68
807 85
376 165
33 76
1495 1172
780 6...

output:

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

result:

ok 2000 lines

Test #11:

score: 0
Accepted
time: 5ms
memory: 18420kb

input:

2000 9
203 1192
632 234
1825 844
1559 1036
596 742
33 1345
1254 1183
1592 1737
886 760
836 50
793 1955
115 1040
1067 1943
153 456
1819 1456
1563 1366
664 209
583 1574
1120 1737
1385 1354
852 284
945 1668
225 1963
341 928
1351 979
479 1652
1353 1333
1907 1933
1487 21
1737 600
1913 395
1336 888
338 32...

output:

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

result:

ok 2000 lines

Test #12:

score: 0
Accepted
time: 1ms
memory: 18264kb

input:

2000 6
1425 1140
781 2
1556 1112
1953 1556
475 1556
1019 251
1556 543
1556 1186
1556 983
273 1556
1556 1783
1963 1340
1645 1556
1556 300
1556 1551
1556 346
525 1556
1556 1289
1556 1257
1556 1729
1556 974
1556 888
1556 1738
1556 716
315 1556
1220 1556
1556 353
1001 1469
1556 1335
1556 374
1556 1263
1...

output:

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

result:

ok 2000 lines

Test #13:

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

input:

2000 5
1443 1122
821 1362
1348 1904
268 600
502 241
1837 820
622 355
413 684
527 314
1648 822
1702 1812
299 194
1553 1040
265 863
892 1789
1979 329
341 11
169 207
845 960
1592 323
1408 350
982 1569
1704 1561
1091 1759
471 1354
1782 1730
1992 779
1171 782
752 955
80 1938
770 304
333 1094
1329 1655
98...

output:

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
4
5
5
5
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
...

result:

ok 2000 lines

Test #14:

score: 0
Accepted
time: 2ms
memory: 15208kb

input:

2000 1
1230 354
1787 355
1656 683
905 469
1820 1452
101 369
1502 355
754 356
659 355
511 1462
705 471
251 442
1711 355
1973 925
650 822
1934 1160
1358 995
1571 818
355 115
1076 1336
487 355
108 570
774 731
355 1849
1349 1398
490 1168
31 1670
1874 29
699 347
355 1684
272 355
22 1960
643 874
355 1722
...

output:

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

result:

ok 2000 lines

Test #15:

score: 0
Accepted
time: 5ms
memory: 15640kb

input:

2000 10
1292 134
1644 1008
144 364
765 709
1671 1188
1624 1836
390 900
913 1540
719 1691
295 259
534 1316
1360 296
1228 387
386 1355
1546 1095
1412 1102
141 1266
1267 1198
1292 1300
1030 424
1146 1848
596 886
542 1522
951 1952
671 628
763 1220
1222 231
1944 963
1431 1769
792 959
1046 1292
1292 383
1...

output:

1
10
0
1
10
10
1
10
1
0
0
10
10
0
0
10
2
10
0
6
1
1
1
10
10
0
0
1
10
0
0
0
10
10
0
8
1
1
0
10
10
1
10
10
1
0
1
10
10
1
0
0
0
1
0
10
10
10
1
0
9
0
10
9
10
0
0
0
10
10
1
10
10
1
0
1
10
1
0
10
1
10
0
10
10
0
2
2
0
1
1
10
9
10
10
10
10
10
1
10
10
10
0
10
10
10
1
1
0
1
0
0
10
0
1
10
0
10
1
10
10
1
10
0
0...

result:

ok 2000 lines

Test #16:

score: 0
Accepted
time: 1ms
memory: 15600kb

input:

2000 5
305 900
106 900
577 900
900 1017
900 631
134 900
900 1402
900 1652
1324 900
164 900
559 900
900 1342
900 1734
1125 900
824 900
1246 900
291 900
1190 900
900 1782
900 1195
900 1043
584 900
900 1741
900 1965
1188 900
900 1844
900 1264
900 581
900 845
900 1931
900 1326
1877 900
900 1255
900 894
...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 2000 lines

Test #17:

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

input:

2000 4
1890 1838
1103 1956
1614 260
1512 571
85 1838
1838 148
233 169
1838 58
1838 1946
1838 445
1494 1263
1407 301
100 1912
1418 1975
1627 270
1128 1838
674 1867
1752 1668
1268 1651
82 215
999 146
1838 548
250 1543
1274 1838
305 1838
1838 844
1751 1498
1906 10
543 163
122 1838
660 1655
1838 1576
85...

output:

4
4
1
1
1
4
1
4
4
4
4
4
4
4
1
4
1
1
4
4
4
1
4
4
1
4
4
4
4
4
1
4
1
4
4
4
4
4
4
4
1
4
4
4
4
1
4
4
4
4
1
1
4
1
1
1
4
1
4
4
4
4
4
1
4
1
4
4
1
1
4
4
4
4
4
4
1
4
4
1
4
4
4
1
1
1
4
4
1
4
4
4
4
4
4
4
1
1
4
4
4
1
1
4
4
1
4
1
1
4
4
1
4
4
1
1
1
1
4
4
4
1
4
1
4
4
1
4
1
4
4
1
4
4
1
4
4
4
1
1
4
4
4
4
4
4
4
1
4
4
...

result:

ok 2000 lines

Test #18:

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

input:

2000 2
1032 289
236 1488
1762 128
1926 580
349 922
835 1988
835 1377
1112 1586
341 998
635 387
1835 1723
1029 835
1303 1914
314 1481
1662 430
1314 1152
1212 926
554 523
361 949
1924 1477
154 1799
835 1283
324 23
835 1482
321 540
1320 1820
835 1485
835 200
1927 504
1725 1006
220 656
835 1007
364 1717...

output:

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

result:

ok 2000 lines

Test #19:

score: 0
Accepted
time: 2ms
memory: 16620kb

input:

2000 619
1215 1416
174 1576
1559 1503
514 651
1484 1539
1217 1121
752 485
512 719
1010 1903
926 1242
882 309
844 485
1295 460
115 1504
38 1130
1000 1990
1389 57
219 1493
579 1797
281 1347
224 782
1295 1793
224 278
221 1227
300 1686
990 1266
1643 181
1028 1861
803 1762
304 1976
1554 1042
420 1742
180...

output:

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

result:

ok 2000 lines

Test #20:

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

input:

2000 1589
398 1883
874 1438
1025 159
759 1551
206 670
1074 1873
1807 1108
242 1785
719 1380
15 1405
24 804
668 1287
362 181
1471 1396
1813 101
987 1259
1499 471
1283 221
1641 416
1128 1595
497 1235
170 1034
1579 1430
1522 1085
58 419
1517 1503
638 808
760 946
1773 1014
1441 305
1390 1925
1077 37
142...

output:

719
690
800
868
923
972
712
690
587
433
236
105
331
467
293
866
845
284
908
842
437
668
555
38
416
937
554
93
1002
432
935
859
298
650
998
812
871
562
990
895
1029
598
758
117
1075
781
895
962
1124
731
334
709
106
1081
242
634
1032
936
574
1018
708
163
1092
508
913
1076
1065
797
1005
1048
1040
995
4...

result:

ok 2000 lines

Test #21:

score: 0
Accepted
time: 1ms
memory: 18416kb

input:

2000 1174
1718 1701
1663 1817
990 1332
1638 1283
870 674
249 719
430 853
490 287
621 378
501 1386
66 1713
1794 1811
1455 873
998 910
1998 1968
1103 619
726 42
1184 577
1348 204
1567 1700
632 990
1661 1845
1967 1125
728 1178
1361 560
681 1867
130 139
1983 1380
1484 620
1159 1412
989 1065
109 1354
101...

output:

1
0
0
6
139
0
1
252
0
321
8
144
0
0
0
1
1
2
0
0
67
368
374
274
3
115
0
343
1
0
0
0
30
0
315
0
134
205
213
170
0
250
168
0
398
0
327
0
0
0
0
0
0
1
263
0
378
247
1
0
1
0
3
0
288
236
0
0
0
0
310
0
328
79
0
0
0
391
0
0
0
301
228
0
269
0
391
0
0
0
332
4
0
206
0
317
111
313
71
236
0
0
281
0
193
1
1
0
0
19...

result:

ok 2000 lines

Test #22:

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

input:

2000 144
1589 315
1662 685
726 522
959 721
1420 1935
1591 1075
687 1198
538 3
1410 428
363 1984
621 928
1494 773
325 1051
500 538
669 853
1960 839
318 160
1358 62
637 1323
88 624
1850 538
538 1616
1719 1701
700 1350
117 538
2000 1821
314 1828
1832 1889
1120 1243
1631 1849
939 1758
531 95
390 538
825...

output:

1
1
1
2
1
1
2
3
1
1
2
2
2
2
2
1
2
3
4
1
1
3
2
2
1
3
1
2
2
1
2
4
1
1
5
6
4
2
3
4
2
1
3
1
1
2
4
2
2
2
1
2
1
4
1
1
2
1
3
2
1
1
1
2
1
1
2
1
3
1
2
3
1
1
2
4
1
3
5
1
1
2
1
2
1
1
1
1
2
3
2
1
1
1
1
4
3
1
3
2
1
3
2
2
2
2
5
2
3
1
2
1
5
2
1
1
1
1
1
1
2
6
4
1
2
3
1
2
1
1
2
2
1
3
1
1
1
1
2
4
2
1
1
2
3
1
4
2
1
1
...

result:

ok 2000 lines

Test #23:

score: 0
Accepted
time: 1ms
memory: 15612kb

input:

2000 1539
610 682
1567 1833
455 673
1603 1799
211 138
1579 1009
1441 335
1472 116
1802 1558
256 1034
1176 930
1607 1868
937 1762
1866 1088
54 352
201 411
244 1374
253 324
1048 1554
1197 1284
935 1300
374 1562
1609 1792
1576 1240
805 1997
925 1563
1951 1035
1431 401
1846 1342
809 1304
335 1113
1229 1...

output:

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

result:

ok 2000 lines

Test #24:

score: 0
Accepted
time: 1ms
memory: 16792kb

input:

2000 519
1773 1636
553 814
1028 682
317 1210
1168 13
206 173
1498 1425
1663 1246
1165 1262
1618 134
375 9
1998 546
1415 670
432 1363
1435 1017
400 1395
323 1614
169 906
284 146
776 549
24 58
1001 1552
563 1898
1638 1180
1135 1449
15 1074
1649 1557
1094 1643
527 241
24 1545
1274 1200
1968 1187
1004 9...

output:

4
4
12
3
4
16
3
4
12
4
12
3
3
6
2
10
5
4
3
13
2
4
3
3
3
3
12
3
10
2
3
4
2
3
8
5
10
10
11
2
3
4
10
14
3
3
11
5
3
7
3
13
2
4
3
6
6
3
11
2
13
4
2
5
3
6
12
13
6
3
14
10
4
8
3
3
5
2
13
14
9
3
6
4
3
6
11
2
6
6
4
3
5
2
4
14
4
12
5
2
5
11
5
4
5
2
2
12
4
3
10
11
3
3
10
13
3
6
7
12
6
3
6
4
12
4
3
4
6
4
3
3
13...

result:

ok 2000 lines

Test #25:

score: 0
Accepted
time: 5ms
memory: 16820kb

input:

2000 568
1955 1424
1169 799
1607 1094
1731 805
1542 349
38 1167
1030 463
1127 222
1326 328
1183 1140
1914 1363
1945 347
1333 1127
1007 625
1086 869
62 153
140 541
1533 693
1442 996
984 1362
1245 785
1771 140
749 940
1535 1351
1279 1372
1148 1570
162 1579
386 416
1324 1641
252 93
45 1823
1467 1190
17...

output:

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

result:

ok 2000 lines

Test #26:

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

input:

2000 460
1762 905
1762 593
903 1762
1038 1762
1026 1762
1762 1974
16 851
1762 214
751 1271
1762 1868
1762 1011
1762 815
1762 1983
1345 1762
1762 1955
1134 625
1762 1723
1762 740
419 1956
1762 434
1148 1762
1762 233
39 1762
1189 1762
444 1762
541 1762
1762 1918
1762 1010
1762 601
1591 1762
1913 1762
...

output:

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

result:

ok 2000 lines

Test #27:

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

input:

2000 1870
195 1081
1072 11
706 155
1893 180
236 761
1895 1174
1239 1526
547 1716
1944 304
153 719
620 1064
739 1506
491 1514
679 1415
384 1562
1826 36
550 446
560 505
1993 359
984 1761
327 4
96 461
513 809
732 991
240 53
7 1707
54 330
1768 602
1493 134
496 1577
610 187
1545 1976
1223 221
1447 1916
5...

output:

535
753
351
85
815
175
371
516
101
464
154
13
528
277
244
321
283
768
449
313
219
666
797
388
1
93
776
155
302
771
272
683
634
93
645
484
365
728
368
779
759
634
86
599
582
713
700
47
534
296
9
25
96
10
368
345
133
315
372
661
397
783
636
696
736
660
231
62
462
162
174
102
356
797
302
771
728
760
14...

result:

ok 2000 lines

Test #28:

score: 0
Accepted
time: 5ms
memory: 16100kb

input:

2000 1091
1068 386
1827 1070
1001 1488
808 125
397 1056
1838 1342
1163 1626
839 567
672 1780
740 1626
1718 897
288 101
1086 1049
1626 1839
1946 372
1530 227
1030 1592
1626 1780
1828 1709
1626 55
1351 390
260 666
1626 1046
621 680
1047 1626
176 1626
1538 1287
1004 272
1187 292
273 1440
1857 310
1973 ...

output:

428
194
2
449
574
314
187
451
441
374
703
2
379
75
400
89
179
3
601
1
2
383
141
288
289
192
2
455
252
162
59
507
402
2
696
2
81
97
2
153
95
2
2
93
277
2
2
673
427
115
700
84
517
2
1
2
589
153
2
583
2
373
19
2
187
505
629
262
384
15
561
125
351
659
2
579
2
459
694
378
673
29
2
2
577
28
2
334
403
241
...

result:

ok 2000 lines

Test #29:

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

input:

2000 1959
377 463
1434 1542
343 638
567 1086
1626 1251
342 28
841 785
835 557
638 1562
541 1291
1224 638
1973 422
1602 341
1643 1875
638 1034
15 1128
1729 638
654 1491
384 1876
370 638
70 1986
1315 1467
675 1894
1980 1549
1822 1451
1230 638
1138 496
900 217
1947 470
1548 727
211 1141
136 1193
1322 1...

output:

2
45
0
1
278
0
0
222
0
78
2
0
0
0
1
0
0
235
0
0
0
281
1
116
0
0
2
234
1
228
3
0
0
0
0
0
1
0
232
225
194
0
263
1
1
0
0
68
209
0
1
0
1
0
206
1
98
112
236
57
0
44
0
28
2
62
0
123
0
0
202
0
91
0
43
1
0
211
165
0
195
0
4
1
0
0
1
0
11
0
1
163
1
148
2
136
1
250
302
126
1
2
168
98
1
143
200
65
45
1
0
0
1
1
...

result:

ok 2000 lines

Test #30:

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

input:

2000 492
235 1628
1289 1628
468 1628
1628 667
1628 220
1628 973
1628 92
172 1628
1628 882
1628 1260
1628 316
1628 1055
1628 1213
1987 1628
1628 136
1156 1628
1628 282
1276 1628
974 1628
1628 1772
1628 1214
229 1628
419 1628
1628 1031
873 1628
636 1628
165 1628
182 1628
567 1628
1403 1628
779 1628
75...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 2000 lines

Test #31:

score: 0
Accepted
time: 1ms
memory: 18356kb

input:

2000 266
115 1606
1219 795
108 49
1606 965
1114 166
1005 1645
744 1671
538 1354
1606 267
230 1465
1872 599
1784 172
431 1601
1737 474
1606 334
821 1172
86 520
1606 1235
1709 1044
72 838
1015 914
649 1606
627 1030
1051 1606
1528 1340
1606 1185
1695 1774
1187 1606
13 691
1329 1366
1606 500
1606 567
16...

output:

1
263
258
1
259
120
158
1
1
1
1
245
79
264
263
1
1
26
1
244
162
239
1
231
202
1
133
1
1
254
1
1
1
212
218
1
1
245
231
257
81
245
1
261
1
254
4
258
248
1
1
165
1
249
135
185
262
258
188
231
202
255
1
1
1
1
263
10
1
188
130
264
1
123
1
1
1
240
1
1
195
261
256
1
1
123
254
1
1
1
182
1
1
258
1
249
1
1
1
...

result:

ok 2000 lines

Test #32:

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

input:

2000 1192
34 1120
699 1974
440 726
1440 1321
1709 1305
946 1419
1927 915
1023 1686
226 1037
1607 646
448 613
189 1233
448 496
657 1092
1911 777
1977 1012
714 1637
1604 306
820 1992
1047 1803
1805 448
344 1164
448 535
448 1558
629 185
7 448
52 859
1161 1575
1556 1787
902 524
643 1673
94 438
1236 459
...

output:

1
142
0
397
0
224
1
0
250
0
264
0
0
0
0
1
301
0
94
3
0
181
307
0
1
1
40
1
0
0
120
1
248
26
66
0
98
116
1
0
1
212
1
0
0
0
1
0
381
1
284
134
1
372
0
0
1
251
0
276
157
1
349
118
1
1
0
1
0
319
1
0
0
172
1
0
0
383
1
1
0
358
126
305
1
105
0
1
0
0
0
0
9
188
282
292
125
48
1
0
324
1
0
1
0
362
1
314
0
370
33...

result:

ok 2000 lines

Subtask #2:

score: 32
Accepted

Test #33:

score: 32
Accepted
time: 48ms
memory: 21628kb

input:

115391 1
32067 50006
1710 5850
21016 66364
72998 34367
24783 10670
49950 93666
81835 81234
53480 68963
87357 43320
93905 30509
72528 92224
520 100511
54804 2917
58490 23858
93643 87530
90737 65205
60740 110812
9553 90266
70028 67222
108045 88982
35584 110286
53518 21733
108735 26404
108228 109796
92...

output:

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

result:

ok 115391 lines

Test #34:

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

input:

114976 1
74053 36053
62978 89255
32367 21913
113882 44280
60815 35782
107811 95272
109039 78845
22484 41688
1781 111596
111506 59375
19869 45586
84990 81214
38638 90205
14928 14370
10758 5465
87745 5949
66720 6357
76134 26466
91805 105936
31792 68220
74216 108462
60158 67410
69489 50297
74956 63776
...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 114976 lines

Test #35:

score: 0
Accepted
time: 11ms
memory: 20776kb

input:

28388 1
10509 15648
25863 14495
26973 2553
22819 7801
5054 15080
6091 12384
4727 3538
14600 14672
4481 9533
26520 23761
6729 3525
15678 8426
7628 26890
25846 26267
10186 5633
21692 25057
17882 26693
25518 13361
6875 371
27786 23632
24474 21637
1387 8015
22050 3422
8420 25752
26814 7209
11499 21112
5...

output:

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

result:

ok 28388 lines

Test #36:

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

input:

200000 1
17564 189544
118109 130056
39153 56739
138814 48828
103560 16598
174399 8469
146229 189678
173046 95721
168793 168656
21067 78280
169301 178753
63496 153947
22754 181712
34926 22205
41248 16310
81136 35768
87905 3442
89999 119217
108408 136055
153855 175444
177272 157293
174568 5857
71023 5...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #37:

score: 0
Accepted
time: 151ms
memory: 49808kb

input:

200000 1
35713 32997
199904 59024
24108 108224
75623 8060
169202 44171
166898 189166
52691 184504
91052 94474
3355 161889
76684 4006
13328 59307
83889 5391
139095 198059
194946 197068
147175 102095
68329 10784
45563 111710
123071 177610
156268 186570
149699 52604
191299 78685
68117 130476
132359 860...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #38:

score: 0
Accepted
time: 157ms
memory: 37240kb

input:

200000 1
15065 142612
651 173717
153862 68423
150849 147717
192561 152722
165359 180378
34627 59508
140908 24495
180671 177962
183330 27822
155654 53394
20596 1741
76236 52151
167441 5306
73654 149981
97720 142937
10793 84081
124721 123748
185212 150311
170407 158310
125015 73861
36456 121189
39975 ...

output:

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

result:

ok 200000 lines

Test #39:

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

input:

200000 1
86027 61282
69968 35175
136022 154753
52733 39599
97774 24158
25263 138562
112124 6412
183205 101112
112094 38819
113526 47859
137031 122132
165018 84375
76900 182974
29302 174006
34918 73123
23660 37001
141115 33742
61282 24152
150734 61282
22552 49677
106054 193519
84741 62724
6470 178907...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #40:

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

input:

200000 1
28426 75100
141794 24004
167055 168353
178427 10860
34348 190354
192106 81422
75263 134731
54229 108154
90586 122196
172392 58237
84932 15421
79435 77253
185144 24679
63387 23340
68674 72825
137398 109447
33249 46900
99738 44920
92707 125920
163133 64180
83887 123053
152655 83838
133345 953...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #41:

score: 0
Accepted
time: 104ms
memory: 26616kb

input:

200000 1
69183 39245
163717 95756
76286 79561
100403 156730
144012 28043
198819 127959
64878 40226
57715 170431
64896 172859
44376 76276
154716 52042
193460 121983
98422 173076
114307 113862
51895 51986
193923 26201
116458 6275
6786 5649
175035 64551
148902 26238
129547 45157
151907 50571
76031 8614...

output:

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

result:

ok 200000 lines

Test #42:

score: 0
Accepted
time: 106ms
memory: 26480kb

input:

200000 1
196045 146636
176533 42271
166724 196028
139244 76615
148314 148067
178418 115890
192238 183829
32675 57585
185089 143473
101515 59837
190250 186401
150802 188721
50798 191609
47863 142815
183786 28970
184954 58810
13430 196707
133210 193546
49302 49747
109810 162864
98935 133593
169908 210...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #43:

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

input:

200000 1
58527 148510
90024 104304
46291 148510
148510 193006
51631 148510
148510 117266
148510 53357
166103 148510
148510 127112
148510 105363
148510 171703
56809 148510
148510 60920
164837 148510
148510 181377
67076 148510
148510 94358
8910 148510
43101 148510
148510 64867
148510 46788
148510 4249...

output:

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

result:

ok 200000 lines

Test #44:

score: 0
Accepted
time: 145ms
memory: 40416kb

input:

200000 1
66730 123320
47115 79350
85283 171708
156551 17983
140238 171549
93983 190883
146694 145897
48194 48325
186569 69965
165293 107104
105458 137156
117295 132479
49962 144513
135589 103731
120064 134791
163864 155625
175728 67758
190171 179156
102382 51967
50807 154114
8247 142134
101115 87765...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #45:

score: 0
Accepted
time: 107ms
memory: 36760kb

input:

200000 1
119243 17471
67473 185473
190254 145264
53666 71426
9704 176027
198823 89774
71677 118558
159294 5996
185413 50972
191335 108317
37995 17944
145264 181582
159163 179684
129331 153479
109731 88138
42760 145264
145264 60498
145264 128517
142009 99861
97187 193109
58740 36290
25804 155500
1772...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #46:

score: 0
Accepted
time: 109ms
memory: 36128kb

input:

200000 1
180791 170350
48720 135071
182635 17624
64784 50175
87186 159402
159402 66047
160362 52459
124401 33646
32003 80049
87225 130074
159402 154274
25488 50341
70872 198001
159175 3485
95007 34608
179653 31222
41151 186981
62308 59184
161512 53729
198034 28649
95823 130252
159402 123739
16422 11...

output:

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

result:

ok 200000 lines

Test #47:

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

input:

200000 1
78129 101331
31692 78129
78129 108968
173678 78129
78129 193716
78129 108185
78129 153059
19448 78129
78129 159448
78129 56603
103258 78129
51678 78129
151290 78129
78129 195380
174479 78129
12931 78129
150607 78129
113935 78129
157004 78129
78129 22638
78129 140760
137800 78129
78129 16451...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #48:

score: 0
Accepted
time: 111ms
memory: 41436kb

input:

200000 1
166243 176626
72675 120076
174047 145754
74966 144274
16524 38961
169628 41061
107629 128678
52336 144274
128129 144274
78204 144274
144274 64980
108790 32439
27043 51977
106796 109356
164139 144274
85737 17025
174536 152580
4863 50617
144274 16825
144274 144369
144274 124976
181247 51097
1...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #49:

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

input:

200000 1
120958 155316
149423 10108
115797 62195
102476 192436
162724 195049
138522 47257
60272 15129
74064 169985
15504 93511
172244 101053
40670 60272
60272 125017
51824 61439
136524 7174
168447 66399
170627 141660
67971 173187
111804 29595
163654 33473
153084 1690
60451 11738
133054 181387
14573 ...

output:

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

result:

ok 200000 lines

Subtask #3:

score: 32
Accepted

Test #50:

score: 32
Accepted
time: 67ms
memory: 23260kb

input:

157976 157976
20171 157173
44732 54119
107845 121149
109200 110309
82678 108206
89140 64200
36916 128759
3966 123760
92978 105716
43700 146126
14924 3429
107721 36095
94906 78173
97162 29552
119574 39605
25145 138492
16622 99431
60281 7949
76176 136644
75716 91518
127987 110605
77999 110960
101187 5...

output:

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

result:

ok 157976 lines

Test #51:

score: 0
Accepted
time: 173ms
memory: 48416kb

input:

191205 191205
92326 99995
188142 63029
71973 50899
68069 72878
159479 103397
143191 93854
27574 146981
63427 186167
104978 177629
22355 188155
184293 15184
101908 143833
111535 144687
112209 61685
59401 128258
97717 87496
168079 130237
49319 190230
119632 98368
76193 184597
22790 136093
1080 80811
1...

output:

33816
135610
162660
131426
190598
61940
182394
60206
64348
110918
188484
7222
137922
180624
16470
93248
10468
114842
68032
166390
123722
186038
67156
83116
49318
25192
173746
73986
142500
173072
102348
118504
80854
27648
134168
50044
59926
32322
46458
177450
48524
8924
13134
77972
122644
120576
1412...

result:

ok 191205 lines

Test #52:

score: 0
Accepted
time: 17ms
memory: 19080kb

input:

31916 31916
28412 28009
2363 28056
3659 22074
23712 27943
19416 15321
14887 11666
6379 5654
30082 226
9971 14492
13981 11752
14242 10178
25107 9048
9088 6047
22323 11776
23441 9334
3950 30048
4494 25014
4971 884
25393 13071
31227 25881
16497 526
9601 6205
29829 17598
27236 31125
27869 17549
10603 95...

output:

3667
0
1133
5027
1
0
0
0
0
1
3637
5
2
2219
3691
0
2457
0
2
1
43
6677
0
5771
2
0
0
41
0
1
0
0
0
0
2013
0
0
0
0
4457
0
4763
1203
0
0
0
0
0
1957
5505
1
1945
1
0
4773
0
0
1
6637
0
0
3793
0
0
0
7359
0
6139
0
7839
0
0
31
3
2337
1
0
1111
1755
0
2513
0
3091
1
5
6505
4757
0
0
6663
7381
3041
1
1
1
0
0
6899
0
...

result:

ok 31916 lines

Test #53:

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

input:

200000 200000
8522 80636
158221 20467
137558 179244
63929 46416
190379 127249
10270 105147
121239 184388
113737 34798
56396 169095
120402 121562
6761 197808
73399 128378
119726 13343
39723 137317
13268 23687
132356 26176
102502 51172
139583 73587
58607 81019
197440 135397
159365 82319
53678 122385
1...

output:

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

result:

ok 200000 lines

Test #54:

score: 0
Accepted
time: 145ms
memory: 49748kb

input:

200000 200000
30404 3409
70531 107126
46652 168864
155049 82807
42684 194360
57108 144938
32493 124488
195042 127527
29871 96787
9762 10681
144410 79089
118939 116876
99174 154784
195005 158160
145251 149354
134536 193935
38082 51228
86551 101378
168310 57058
54208 21573
148567 60683
22941 171027
12...

output:

24449
120519
145939
82943
132849
58123
175687
1603
122977
95777
116867
185465
180903
142715
195055
176929
130585
105019
116049
29293
39467
155423
199087
94563
141289
108325
155319
162451
199235
132571
38167
4787
134333
190519
168619
24161
112719
135877
5881
189657
73303
170617
139023
137245
17979
17...

result:

ok 200000 lines

Test #55:

score: 0
Accepted
time: 159ms
memory: 37316kb

input:

200000 200000
186933 177107
92441 81383
190521 1821
2186 115541
122869 138915
148511 26011
101109 53413
167961 155222
66264 61619
179636 120704
152928 138111
154784 103804
92191 54540
120375 62394
50610 56843
191955 157924
191074 86487
103991 100799
188410 33656
72771 176718
90528 132562
133333 1227...

output:

0
1356
0
0
21490
19334
20586
0
0
0
0
2
37778
5162
0
0
17418
0
2830
7168
1
0
12392
49020
0
0
0
0
0
22964
34370
4
44710
0
0
24460
27348
1610
10330
0
30424
31634
30186
45356
9738
47398
28128
0
0
0
1
16050
1912
0
2
1
3
20758
0
0
0
0
0
0
0
0
0
0
5
18164
0
21670
1
0
0
0
2
0
38958
0
2
0
1
0
3
0
0
7860
4450...

result:

ok 200000 lines

Test #56:

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

input:

200000 200000
167212 34112
20142 148936
34112 66373
34112 96158
90469 170283
113613 69844
97299 122194
22944 182551
100918 128420
156800 34112
93916 61574
34112 90392
93661 112560
189023 34112
34112 55479
124767 104947
193130 34112
121382 75571
34112 130896
196643 165089
182259 99136
80945 34112
166...

output:

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

result:

ok 200000 lines

Test #57:

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

input:

200000 200000
146391 118728
89318 93193
127677 67026
11075 199520
41729 106429
104357 55325
122687 152305
189967 97267
10672 183006
32264 171873
195110 185303
181798 64270
82797 7561
61314 51274
80017 89681
120504 80077
72573 59297
196343 122920
192787 163183
66998 160077
195320 74779
11431 118537
8...

output:

416
2411
2438
605
2021
789
1291
1290
1920
823
207
1448
245
2003
1426
947
2416
2504
1234
685
1401
821
1273
879
2290
1587
1879
625
260
1442
1981
1185
278
1382
207
667
2278
2477
1368
2447
1930
1546
953
374
948
968
1126
1903
1147
1819
1782
975
1824
2222
826
1567
1426
1399
822
348
1273
2289
2415
1308
173...

result:

ok 200000 lines

Test #58:

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

input:

200000 200000
27474 179325
118388 47377
195895 53031
4790 190291
101252 124025
134383 166655
96518 73114
168818 112156
20756 121163
129151 158811
96518 44601
110315 68864
95124 96518
104161 155171
70280 14669
159177 2722
182438 44785
171191 128317
1173 90479
74034 178745
197168 9486
44639 177592
880...

output:

582
160
1093
369
315
2
1
792
674
2
1176
1087
1515
860
1
396
1489
4
320
1
2
266
1504
205
618
1
639
962
859
2
587
557
1
1288
746
7
1085
187
893
3
3
2
824
407
1534
2
1596
2
969
3
1579
932
937
784
1
396
1
4
530
355
1251
1032
741
118
1
3
463
539
307
1236
1076
339
307
765
1511
490
1
890
1
35
2
194
22
292
...

result:

ok 200000 lines

Test #59:

score: 0
Accepted
time: 106ms
memory: 26700kb

input:

200000 200000
155086 37292
187780 155944
114019 109282
118454 28834
67112 153412
48605 92199
57590 112546
46892 105612
104534 4148
156801 85234
68202 199137
70617 107093
184025 147881
59461 100783
58055 107638
87976 910
72192 69380
5563 136841
28214 196874
61489 40284
169984 159750
103971 56737
9056...

output:

77
1
2
1
197
186
2
3
15
9
98
3
2
251
1
25
1
2
1
5
4
5
124
4
2
1
2
89
1
1
4
257
2
205
218
96
7
1
3
4
3
155
1
236
181
4
232
1
1
1
1
3
106
211
2
3
4
1
2
234
90
3
220
4
160
17
92
3
4
3
4
2
1
184
2
227
21
4
184
299
1
1
1
164
2
2
163
2
2
3
1
2
3
103
2
1
2
7
2
1
3
85
2
2
6
1
219
76
68
1
1
2
3
1
1
2
113
120...

result:

ok 200000 lines

Test #60:

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

input:

200000 200000
15745 100319
137031 163308
137031 74238
8670 169542
160536 139105
165384 38105
3724 137031
175949 148497
137031 23700
103318 94913
6254 160576
198226 18652
77505 186113
137031 96799
63991 137031
137031 120048
137031 194869
128531 137031
30589 16807
137031 134002
65394 153192
175738 537...

output:

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

result:

ok 200000 lines

Test #61:

score: 0
Accepted
time: 160ms
memory: 44692kb

input:

200000 200000
42520 10919
146151 23492
63770 176520
38645 59738
45468 51939
102427 20734
17749 127453
9228 127608
168021 28945
98352 46851
110937 117471
186453 51219
14827 179115
120622 3408
120353 196170
50482 62225
131129 50978
44228 108472
113626 72897
14327 37534
133836 66657
91724 135176
168210...

output:

8575
33962
108520
50680
57283
27210
101389
2697
19240
21108
80103
14103
38068
15828
21700
24099
52022
50745
96802
89421
96410
106535
102408
116354
66039
87260
20853
43181
44141
39715
81254
88292
64687
82658
90538
45479
62094
72759
68584
80815
77488
73075
107691
60859
33671
33938
70385
97449
18073
27...

result:

ok 200000 lines

Test #62:

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

input:

200000 200000
128545 94483
30010 172433
170859 39469
45243 13594
135300 163442
15375 50868
67053 40987
178499 79431
114646 53208
23629 26412
94409 17798
58971 21253
16007 78625
146007 172604
186787 98789
122705 187324
29180 27052
172388 185777
91946 50710
99057 35568
165353 5806
165713 74934
14411 1...

output:

0
1
13834
15443
30076
1
1
2
9416
8479
0
28229
5383
10421
27535
41824
42136
0
0
36299
1092
2690
2
16243
32907
17694
0
42572
1
2
17695
2
43163
12548
0
45459
377
21153
30038
1
42286
42760
29166
9694
4
31312
1
46113
0
35469
1503
1
21548
4
24172
18911
40191
12450
1
15185
23888
1
12151
3155
5384
12667
452...

result:

ok 200000 lines

Test #63:

score: 0
Accepted
time: 113ms
memory: 35692kb

input:

200000 200000
109959 124362
66262 141737
41668 188511
48183 110217
175402 69971
53590 184827
67998 64689
78409 68037
61314 105024
162337 19035
151990 174914
133125 16916
11173 133327
194837 167348
110314 168860
111578 155741
29224 28368
120990 41240
35870 169402
5795 198814
115627 71228
68484 128779...

output:

1234
1
1
1
2
2
1
2
18875
35439
8023
1
2
1
1
1
1
0
2327
17604
2
30443
0
16025
1
16203
1
0
1
2
1
29439
10146
28769
6392
1529
1
2
3
2
37238
7231
1
23524
0
2
1
10174
2
2
2
2
2
6615
1020
0
3583
0
1
1
1
33716
2
11089
37624
19049
0
1
31484
31784
1
1
1
0
1
1
16020
9699
2
15941
1
2
2
29601
1
1
16471
1859
109...

result:

ok 200000 lines

Test #64:

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

input:

200000 200000
57134 118491
103930 118491
83639 118491
83809 118491
118491 10330
118491 11299
127268 118491
103410 118491
118491 155105
118491 99483
54649 118491
118491 61991
118491 23679
96389 118491
196772 118491
118491 24551
60592 118491
118491 199616
133837 118491
118491 27307
127714 118491
11849...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #65:

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

input:

200000 200000
146675 199694
138298 123378
97999 138298
95319 139996
27960 153584
87245 96324
138298 137209
116993 146154
161996 138298
67860 17463
138298 19117
149057 120769
138298 131321
138298 50065
100092 138298
138298 74606
122020 75874
195658 88832
198703 164262
79974 26283
80979 119249
3588 13...

output:

1
132322
1
35097
1
1
68694
18646
74923
103637
122206
60483
132872
23108
95069
1
1
120752
120479
1
1
120751
1
124790
1
1
99021
98220
1
14454
32231
40154
1
44998
8608
1180
83124
1
1
41260
103789
76525
69984
1
67763
61754
115684
94019
131508
4736
99229
116056
45277
96348
64315
62197
2726
1
104249
86035...

result:

ok 200000 lines

Test #66:

score: 0
Accepted
time: 123ms
memory: 37248kb

input:

200000 200000
153793 16107
196077 3124
47812 175488
178509 40516
86453 171917
26150 65530
82950 161539
74952 32075
84716 7313
144894 29996
10173 162697
12847 33144
46328 174758
26150 101368
26150 154874
37757 81479
182448 158838
181842 70390
171553 26150
161832 12009
49362 166226
144486 16556
23260 ...

output:

1
0
0
46487
18296
12639
0
1
0
0
1
0
0
41018
0
1
0
28345
0
0
0
12641
0
1
12463
35922
0
1
1
1
0
0
1
0
2423
5553
8655
0
1
1
21784
1
11909
39129
46473
46006
1
1
5837
1081
10479
38708
2645
33597
20051
23925
30392
0
0
2127
0
0
1
14105
0
0
34187
39784
1
0
21023
1
1013
0
0
49792
0
0
0
0
0
0
0
11393
44039
0
...

result:

ok 200000 lines

Subtask #4:

score: 32
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #67:

score: 32
Accepted
time: 13ms
memory: 16452kb

input:

26817 23497
18306 8710
18135 13212
2969 7244
705 17197
2501 6738
171 872
14509 11385
17646 24099
24664 17538
16450 22602
15171 25565
25844 2766
5805 9711
14847 4030
19245 16566
22005 6266
9009 11811
22620 22215
20276 19973
5792 2269
23871 19855
9135 5440
23115 23100
6710 1032
12047 16563
10890 13360...

output:

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

result:

ok 26817 lines

Test #68:

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

input:

86626 31945
26456 35006
4929 25920
79082 25441
49732 3252
78973 82422
20487 2574
60610 85047
9018 74928
74804 48904
46002 24785
16088 44564
65208 30235
48118 21416
23369 60681
33422 80969
52360 26882
30665 7295
65654 56247
82204 17425
16512 2866
82976 78244
54812 71303
13238 7526
56465 52908
38545 3...

output:

29578
23241
29293
28049
29756
22431
29555
25855
29586
19549
19345
28317
19896
28498
17003
9651
9645
26267
16264
9900
27287
27521
25021
23155
21132
24013
28825
24656
28203
2223
529
19436
10920
28269
28023
29513
24958
15380
28682
29671
23768
26304
29419
14813
26744
23661
328
18356
28350
12975
3356
275...

result:

ok 86626 lines

Test #69:

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

input:

123932 19808
20471 76915
60144 41254
12488 109360
103601 60576
103684 113890
100693 14352
117912 37107
49169 116387
96195 8756
15463 35514
7369 28678
35937 22513
61263 66052
13868 35356
29655 52847
43084 31407
93315 104654
118110 88148
110549 21136
92470 24571
9135 10393
25141 93624
90481 41497
1133...

output:

2
0
9649
0
7891
0
0
0
0
7647
15619
0
1
1728
8594
0
0
0
2
0
0
6432
1
1
0
0
0
14675
0
0
1
0
0
0
1
6758
13769
0
0
0
0
0
13503
0
1
0
12461
4330
0
0
0
2
0
0
14046
0
10695
1
13811
3757
2
0
0
0
0
2651
0
12084
2
148
0
15002
3431
13028
6
0
0
11299
1191
6693
4091
14927
8505
0
2
4251
1481
0
14215
0
0
0
0
0
121...

result:

ok 123932 lines

Test #70:

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

input:

200000 9
130927 101074
59833 195229
163322 59336
49244 102837
59802 165484
14201 33521
148530 25187
91247 17288
121515 171287
142558 146745
184085 69562
124610 45120
68573 97996
21186 112855
151289 188047
160970 50568
131379 94335
8359 73847
44580 187491
198209 46947
75844 102544
98144 71126
176963 ...

output:

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

result:

ok 200000 lines

Test #71:

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

input:

200000 2
62635 150471
3236 73260
36196 47550
122065 126366
87919 59404
148619 147069
16128 85555
41769 87629
2832 133279
154613 123693
34926 157980
188401 138782
97574 157997
22972 7895
30077 95106
65599 83240
48805 128230
62044 181866
187307 28951
38008 192090
130570 92708
174988 100284
159205 1108...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 200000 lines

Test #72:

score: 0
Accepted
time: 136ms
memory: 37308kb

input:

200000 8
641 76684
199218 71915
151549 193887
146591 164473
136230 100209
100336 99280
21055 144125
170223 45823
137826 8232
163902 12880
55281 150932
163078 25971
193954 160216
121219 144952
22155 131156
75668 133105
89840 188407
185198 108929
140088 59903
42176 169157
136705 103523
57921 172651
16...

output:

8
8
8
0
8
0
0
0
0
8
0
0
3
0
0
0
0
8
0
0
8
0
1
0
8
0
0
8
8
8
8
0
8
8
0
0
8
8
8
1
2
8
2
8
8
0
8
8
0
0
0
0
2
0
8
1
0
0
0
0
0
0
0
0
8
0
0
0
8
0
0
0
8
0
3
8
8
1
0
8
0
0
8
1
3
0
2
0
8
8
1
8
8
8
8
0
1
0
2
8
8
0
0
0
0
0
0
0
8
8
8
0
8
0
8
0
8
0
0
8
0
2
0
0
0
8
0
8
1
1
0
8
8
0
8
0
0
0
0
0
8
8
1
0
0
0
8
0
0
8
...

result:

ok 200000 lines

Test #73:

score: 0
Accepted
time: 96ms
memory: 24784kb

input:

200000 5
170071 110442
20078 168613
114026 186978
80752 138928
187253 120314
16968 16795
127013 196189
127013 19139
45186 57546
93121 182447
50831 10169
191516 120346
73715 106945
167374 96071
30896 56443
87459 18562
15648 198487
127013 182497
123858 42549
52154 189351
174579 96037
127013 176694
417...

output:

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

result:

ok 200000 lines

Test #74:

score: 0
Accepted
time: 104ms
memory: 29616kb

input:

200000 2
153014 110301
99041 114779
178571 184419
186021 97541
157900 20855
141948 114535
25862 151972
4748 90605
34418 193180
195234 10773
111030 167071
129096 104272
131376 178508
2314 9439
145199 150324
31078 109364
171634 38759
157665 29723
71824 114056
107406 194523
66061 128882
40110 22495
131...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 200000 lines

Test #75:

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

input:

200000 5
16646 194831
191076 101875
185031 160475
98340 30248
184746 25911
84803 20298
49323 80709
41182 105278
1006 197066
172107 175490
173241 29621
132902 147101
146046 99696
94045 190252
185160 121350
81851 64178
12760 73665
169532 128982
95239 42232
173157 103817
196254 18556
84230 36080
40541 ...

output:

5
1
2
2
5
2
5
5
5
5
5
5
2
5
5
5
2
5
5
2
1
5
5
1
5
5
5
5
5
2
5
5
2
2
5
2
1
5
5
1
2
5
5
1
5
5
5
5
5
3
5
5
1
5
5
5
5
5
2
1
5
5
5
5
2
5
1
5
2
1
5
5
3
1
5
5
5
5
1
5
1
5
5
1
1
5
2
5
2
5
2
5
1
5
5
1
5
1
5
1
5
5
5
5
1
2
1
5
5
2
5
5
2
5
5
5
1
2
5
5
5
2
5
5
5
5
5
2
5
1
5
2
5
5
5
2
1
5
2
1
2
5
5
5
5
2
2
2
5
1
...

result:

ok 200000 lines

Test #76:

score: 0
Accepted
time: 114ms
memory: 26780kb

input:

200000 10
80800 101672
49837 58709
17649 35586
6453 184047
55955 105724
41313 45727
26606 114813
184822 16074
12542 77529
16133 119489
79857 183942
114461 173072
22911 92011
17386 63576
120774 172899
9451 67769
121440 37748
38648 113983
69144 113025
37051 76624
15900 196273
35348 48748
102837 29388
...

output:

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

result:

ok 200000 lines

Test #77:

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

input:

200000 5
7376 36288
65615 139374
37894 36288
164527 36288
29659 37793
2178 36288
36288 186278
147173 36288
161663 159296
167192 69775
59110 36288
36288 99221
101491 36288
36288 116895
58368 118862
9594 36288
184315 429
90672 161443
36288 92925
19513 171005
167960 88052
36288 19938
180987 77386
15116...

output:

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

result:

ok 200000 lines

Test #78:

score: 0
Accepted
time: 136ms
memory: 43048kb

input:

200000 4
137299 112733
157436 191539
76671 153709
45011 98452
74273 179319
10273 42772
15934 183276
130213 99508
35911 132282
121198 4319
38582 199390
66740 161689
175829 109767
119199 124600
52144 133901
146976 49947
178435 99839
195606 193255
42746 178679
129920 25499
135269 104405
100463 82907
49...

output:

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
...

result:

ok 200000 lines

Test #79:

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

input:

200000 5
39527 13504
161318 187902
143443 148589
161318 53080
137281 119107
39 161076
100834 123187
161318 148883
35470 17784
125816 162817
152939 112364
163316 59322
174326 179264
43108 161318
186360 147010
69695 161318
195512 169451
182309 112516
109872 157531
68868 66428
60265 90412
29836 90120
1...

output:

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

result:

ok 200000 lines

Test #80:

score: 0
Accepted
time: 114ms
memory: 34856kb

input:

200000 6
64503 66383
169564 148682
147016 41581
143173 128522
179249 80506
84865 64503
63540 64503
39230 165109
38229 22133
64503 196024
103950 131050
16287 25115
37160 117019
10325 46603
8561 45700
136408 104563
52896 11811
76316 48905
185973 84055
92785 119463
37173 156719
35434 157090
164056 9866...

output:

6
6
1
1
6
0
6
0
0
6
6
0
6
1
6
0
0
0
0
0
0
3
0
0
0
1
0
0
1
6
0
2
0
6
0
0
6
1
0
6
6
6
6
1
6
0
6
2
6
0
1
6
1
6
1
6
6
6
1
1
0
6
0
6
6
0
1
3
2
1
0
1
0
0
0
0
6
0
6
0
0
0
6
6
6
6
1
6
1
1
0
1
0
1
1
0
6
0
1
1
0
0
1
6
1
6
1
1
6
6
6
6
6
1
6
6
0
0
1
1
1
0
6
0
0
6
0
1
6
6
6
6
6
0
1
0
0
6
0
6
6
0
0
1
1
0
6
6
0
0
...

result:

ok 200000 lines

Test #81:

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

input:

200000 7
177635 9191
79617 9191
9191 40192
195017 9191
157471 9191
59139 9191
60571 9191
9191 96046
107036 9191
9191 96601
9191 113484
9191 74307
9191 116805
9191 124295
44086 9191
84565 9191
162824 9191
177431 9191
194722 9191
50169 9191
56611 9191
47786 9191
9191 148076
9191 43601
174340 9191
9191...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #82:

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

input:

200000 4
104917 12124
79285 103420
78399 50732
152261 69208
51744 108046
74590 95404
137420 95130
154286 16479
155446 183243
78399 95899
79996 156480
157782 78399
109627 189148
184994 78399
117082 114002
150231 78399
170137 57947
126084 156420
78399 48984
5571 78399
5039 107642
97244 192850
78399 62...

output:

4
4
4
1
4
4
4
4
4
4
4
1
4
4
4
4
1
1
4
4
4
4
4
4
1
4
4
1
4
4
4
1
1
4
1
4
4
1
4
1
4
4
4
4
1
4
1
1
1
1
1
4
4
4
4
4
4
1
4
1
4
1
4
4
4
1
4
4
4
4
4
4
1
4
1
4
4
4
4
4
1
4
1
4
4
4
4
1
4
4
4
1
4
4
4
1
4
1
4
4
4
4
1
1
4
4
4
4
4
4
1
4
4
4
1
4
4
1
1
1
4
4
1
4
4
1
4
4
4
1
4
4
1
1
4
4
1
4
4
4
1
1
4
1
1
1
4
1
1
4
...

result:

ok 200000 lines

Test #83:

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

input:

200000 5
2848 12299
2848 17464
72776 144898
73438 55858
22857 145698
92301 100014
51430 115330
197141 21351
165511 28072
90439 102198
199092 130420
152907 76964
125360 94365
88522 57811
117372 46489
2848 107912
176060 167849
21180 173356
144425 119437
164914 140317
112097 31273
176443 110750
195460 ...

output:

0
1
5
5
1
5
5
5
5
5
5
1
1
5
5
5
0
5
1
0
5
5
1
1
5
5
0
0
1
0
0
1
0
0
1
5
0
0
0
1
0
0
5
5
0
0
5
1
5
0
0
0
0
5
0
5
5
5
5
1
0
0
0
5
5
5
5
1
0
1
0
0
5
0
1
5
0
0
5
5
0
0
5
0
1
5
0
0
5
0
5
0
5
1
1
0
5
0
5
1
0
1
0
0
0
0
5
0
0
5
5
0
0
5
5
1
0
1
5
5
0
5
0
0
0
5
0
0
5
5
0
5
5
0
1
5
5
5
0
1
1
0
0
0
5
0
0
1
5
0
...

result:

ok 200000 lines

Test #84:

score: 0
Accepted
time: 111ms
memory: 24940kb

input:

200000 166
31662 159458
30747 149127
115304 192802
109351 36633
8435 62292
194304 38101
39415 63662
165364 133072
164888 59338
120813 96438
83821 56441
69700 27986
150386 139266
164125 46714
104996 132297
79789 20573
57008 162371
188645 136651
19857 110063
2287 150848
155538 2863
163351 44397
48080 ...

output:

2
1
2
2
5
3
1
2
7
2
2
2
2
1
2
3
2
3
2
2
1
4
2
4
2
3
4
3
2
2
2
2
1
2
4
3
3
1
3
3
2
2
3
3
5
3
3
4
3
2
1
2
3
2
2
2
2
2
1
2
2
3
3
5
2
3
3
2
3
1
3
3
3
4
5
2
2
4
2
2
6
2
2
2
4
2
2
2
2
2
5
1
1
2
1
6
1
4
1
2
1
3
2
3
1
2
2
2
2
1
2
9
1
2
2
2
2
4
2
4
4
5
2
6
2
1
2
1
2
2
1
1
2
2
5
1
2
7
2
2
3
2
5
2
1
2
7
3
2
2
...

result:

ok 200000 lines

Test #85:

score: 0
Accepted
time: 161ms
memory: 49784kb

input:

200000 164
120321 31474
117164 16038
126970 31244
177259 192353
133312 174696
151059 45014
84556 182714
183733 114
26512 164908
36357 199814
15356 131892
50762 93930
71012 75455
132951 72628
140197 89654
123856 190785
155843 105303
2880 156080
80877 46263
176702 156641
81466 58191
47984 106265
85714...

output:

164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
164
...

result:

ok 200000 lines

Test #86:

score: 0
Accepted
time: 160ms
memory: 37248kb

input:

200000 275
59891 44605
60007 113984
117358 101959
62038 2237
10888 138966
127871 17141
154050 7530
31973 190376
87484 135943
131136 120851
41851 43726
65995 83646
101221 89876
36746 84970
108314 35382
197821 190326
74246 137129
106266 173512
77866 156502
45812 15009
38072 16563
62993 96451
108681 97...

output:

0
0
0
2
275
1
0
0
275
0
0
0
0
0
275
0
0
1
275
2
275
275
275
275
275
0
275
275
275
1
275
0
275
2
0
0
275
275
0
0
275
275
275
0
2
275
1
0
0
0
0
275
275
0
275
2
275
275
0
0
0
0
275
275
275
0
275
0
0
275
4
0
275
275
275
0
275
275
0
1
0
0
0
275
275
0
0
0
275
275
1
275
0
0
275
0
0
2
0
0
0
275
275
0
0
275
...

result:

ok 200000 lines

Test #87:

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

input:

200000 156
4052 14
186877 109607
192326 178841
99531 135376
36207 93447
81412 156536
92805 185761
55208 171522
147609 186950
71563 13158
163939 190609
161971 117377
112883 130671
100540 77074
154095 158528
44323 42491
109607 7836
171151 134517
109607 61661
167471 160972
20861 72130
108559 57378
1491...

output:

1
2
2
2
2
9
3
1
2
1
2
4
3
1
1
1
1
1
1
2
1
1
4
1
2
1
2
1
3
2
6
1
2
1
4
2
6
2
1
2
3
3
2
1
1
1
3
1
2
3
2
1
1
3
4
2
1
2
2
2
3
4
2
2
1
2
2
2
3
3
1
1
1
2
2
3
2
3
2
2
2
1
2
2
2
1
4
1
3
3
3
1
2
1
3
2
1
1
1
2
1
1
5
1
1
1
2
2
1
1
1
2
5
1
4
1
2
1
2
1
1
2
1
2
1
1
1
2
2
1
1
2
1
2
3
2
2
4
1
3
2
1
2
2
2
2
1
2
3
2
...

result:

ok 200000 lines

Test #88:

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

input:

200000 145
191549 157078
14220 33074
179065 77464
189140 11156
199565 5523
157127 193294
145881 127901
143008 185114
10144 101590
162412 64914
10673 107769
81844 117846
56942 54295
70441 59439
36611 139981
147049 90629
141172 83636
54063 133640
53444 170325
76991 166808
181738 88379
47828 73719
1959...

output:

145
145
145
145
145
145
145
145
145
145
145
143
145
145
143
144
145
145
145
145
145
145
138
145
145
145
36
145
145
10
145
138
145
145
141
144
145
145
145
145
145
138
145
145
145
145
145
145
145
145
145
132
145
141
145
145
145
145
145
145
145
145
145
145
140
145
145
145
145
145
145
145
145
145
145
14...

result:

ok 200000 lines

Test #89:

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

input:

200000 494
29976 69581
134515 167694
182691 55160
115315 86589
34589 152675
72544 50938
180786 51669
58095 192258
71216 160749
27630 21477
23849 199612
62992 75389
128391 148160
84604 165599
95521 187457
52185 30416
138567 125418
98700 5408
187562 103177
98700 68895
31021 9079
144858 189064
151526 1...

output:

222
1
1
360
265
326
348
313
3
347
2
4
2
1
312
3
294
234
18
122
2
230
121
224
2
96
114
295
4
169
198
108
2
1
131
272
77
1
1
2
2
328
99
148
91
163
292
162
192
2
3
2
260
308
237
172
105
356
147
310
1
291
111
359
1
1
5
333
262
3
2
39
261
262
2
225
123
1
320
191
4
277
313
1
1
133
295
261
291
2
168
9
2
2
...

result:

ok 200000 lines

Test #90:

score: 0
Accepted
time: 108ms
memory: 26768kb

input:

200000 215
151593 58547
174431 76986
102884 53880
51699 124703
152923 55457
89195 57570
155102 54700
169055 2141
11701 21180
143371 143034
75563 46243
73624 95776
61424 133947
114198 28185
58127 50207
10309 177744
81752 36709
38072 44697
120163 15239
183925 59914
31369 182860
116459 70297
109868 844...

output:

4
0
3
107
1
18
65
6
44
0
139
103
3
3
24
21
3
134
0
4
2
2
153
3
106
123
62
3
110
106
61
63
4
0
3
30
141
4
0
0
3
1
4
26
51
3
1
2
1
49
1
4
0
5
70
151
136
4
0
5
0
1
5
5
1
93
4
65
3
5
104
0
2
0
86
0
40
0
96
1
145
4
3
21
3
6
3
94
57
2
166
0
5
0
6
0
3
52
3
1
3
1
3
4
0
107
166
0
3
0
8
145
0
0
3
0
0
166
162
...

result:

ok 200000 lines

Test #91:

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

input:

200000 273
107881 164428
192397 69213
177747 76385
135050 177747
57282 180170
107094 192812
139765 158053
325 147899
182970 81666
187256 177747
71059 140754
144446 178640
64439 177747
133377 114595
172514 29343
177747 46321
42424 177747
62321 27811
155497 177747
177747 82334
73159 138462
162953 1777...

output:

1
3
4
2
2
1
2
3
3
1
2
2
2
2
1
2
1
2
2
1
2
2
2
2
1
2
3
1
2
5
1
3
4
1
2
2
1
2
2
2
2
2
3
2
2
3
2
3
1
1
4
1
2
2
2
1
4
1
4
3
2
2
2
3
2
1
1
5
2
2
1
3
2
2
2
2
2
2
5
3
2
1
2
1
1
2
1
1
1
5
2
2
1
3
2
1
4
3
3
2
2
2
2
5
2
3
4
3
2
2
1
1
1
1
1
1
1
2
2
2
2
1
2
2
2
1
2
1
3
2
2
1
2
2
4
2
2
3
1
2
1
2
2
1
1
3
3
1
1
4
...

result:

ok 200000 lines

Test #92:

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

input:

200000 473
151579 185448
73082 195009
122623 169430
68635 78398
61265 41862
114981 44873
88025 29319
55039 161328
126399 62609
119837 85222
92892 80237
148871 92917
57420 176295
48319 71326
12935 98124
57310 196867
149573 83625
90530 58556
141920 70247
104169 4884
102847 193647
102753 165235
124529 ...

output:

473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
401
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
473
...

result:

ok 200000 lines

Test #93:

score: 0
Accepted
time: 114ms
memory: 33140kb

input:

200000 379
31303 10013
11673 138402
159249 170724
126854 102191
133940 125485
107358 82104
165676 114506
114558 56726
111614 73091
111055 59494
1631 199360
173935 83974
139369 89889
113222 26204
9117 183854
55756 170163
105153 22470
149751 193479
171322 111808
111808 7190
143283 129796
167752 152736...

output:

379
379
379
2
379
379
379
379
379
4
379
1
379
1
379
1
1
379
379
4
379
379
379
1
28
1
379
188
5
379
2
185
379
379
379
1
379
379
5
379
379
355
379
3
379
379
379
379
379
379
379
379
2
379
379
3
379
3
2
3
379
326
379
379
379
2
343
379
1
379
379
379
3
2
379
2
379
379
379
2
379
379
379
379
1
2
3
379
3
2
3...

result:

ok 200000 lines

Test #94:

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

input:

200000 202
179745 14572
94754 9231
106273 21493
14386 196320
58948 190712
73669 92861
34822 171403
122694 77825
47006 94754
94754 81566
65514 4179
36285 122028
80365 62949
8016 118329
88070 127668
120823 19794
69269 153566
182021 8665
175551 28587
84922 48567
7573 128718
14283 62515
120897 166971
56...

output:

3
3
5
202
4
3
3
202
202
4
4
202
202
3
202
202
4
3
4
202
1
202
5
1
0
3
202
0
1
202
3
202
3
175
4
3
4
4
1
4
4
202
202
5
3
3
4
3
202
5
202
202
202
0
5
202
5
4
5
3
202
3
2
3
5
4
3
3
5
202
0
202
3
3
202
202
3
202
3
3
202
4
0
202
4
1
3
202
202
202
202
5
3
4
202
4
202
202
202
202
3
202
4
3
3
3
3
4
5
4
4
4
...

result:

ok 200000 lines

Test #95:

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

input:

200000 341
93147 115187
93147 146942
93147 151212
85145 93147
35155 93147
113691 93147
89189 93147
187972 93147
148105 93147
93147 39315
93147 170461
93147 144614
11860 93147
177135 93147
135173 93147
131634 93147
139022 93147
93147 57696
56143 93147
93147 8325
93147 151190
93147 78642
172346 93147
...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #96:

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

input:

200000 154
56157 141083
126266 198763
169871 101263
130183 13376
198763 56435
198763 81620
162421 198763
134948 177115
50394 3116
193291 198763
140506 142315
124387 36425
173394 147276
10809 145375
2762 198763
198763 119775
175208 1774
71432 759
198763 116110
198763 122900
128721 25535
148813 27469
...

output:

1
1
1
1
154
154
129
1
154
154
154
1
154
1
1
154
154
154
154
154
154
1
154
1
1
154
154
154
1
154
1
154
154
154
154
154
1
1
154
154
154
1
154
1
154
154
153
154
154
154
1
1
154
154
1
154
1
154
154
154
1
154
154
1
154
154
154
1
154
1
154
1
154
154
1
1
154
154
154
154
1
1
154
1
154
146
1
154
154
154
154
...

result:

ok 200000 lines

Test #97:

score: 0
Accepted
time: 123ms
memory: 37292kb

input:

200000 299
18500 103700
196962 129612
42840 11856
102939 143692
134590 103700
88269 4867
40450 103700
153142 199275
184148 106877
173631 132693
45748 181512
26156 190414
162878 3789
29157 35025
176834 105724
4845 32495
66998 139749
744 28727
10877 29599
39181 103700
125488 63584
142597 196257
103700...

output:

0
1
299
299
0
0
0
299
0
1
1
0
0
1
0
299
0
299
299
0
299
0
1
0
299
299
299
299
1
1
299
1
0
0
0
299
1
0
1
0
299
1
0
1
299
1
299
0
299
1
1
0
0
0
1
0
0
1
299
1
299
1
0
299
0
0
0
299
299
299
0
0
0
0
1
0
299
296
299
299
299
0
299
1
299
0
0
1
299
299
299
299
299
0
299
1
1
1
0
299
0
299
0
1
299
0
299
1
1
1
...

result:

ok 200000 lines

Test #98:

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

input:

200000 198538
85368 152521
89576 109430
82260 132897
189625 127699
16955 36552
35639 41691
111931 169582
198460 69965
165877 51321
116967 121065
179108 92371
120514 135247
156633 106818
126980 165154
119286 81657
75212 195014
99938 168199
84972 135900
19904 23597
183613 55895
127398 168350
128654 36...

output:

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

result:

ok 200000 lines

Test #99:

score: 0
Accepted
time: 170ms
memory: 49812kb

input:

200000 3027
53907 100754
149655 67844
109221 152989
151488 182454
5498 186263
30904 45209
120282 99523
172864 59120
161079 135835
13583 89122
79404 33404
34248 192405
94696 90457
140027 120708
109938 8774
165233 165991
198620 14256
773 154918
174502 198751
7836 76612
52426 15077
114816 160599
76231 ...

output:

3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3012
3027
3027
3027
3027
3027
3027
3027
3027
2989
3027
3027
2928
3027
1465
3023
3027
3027
3027
3027
3027
3024
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3027
3020
3027
3022
3027
3027
3027
3027
3027
...

result:

ok 200000 lines

Test #100:

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

input:

200000 136096
86849 73157
163636 100878
12958 64070
156332 52054
3723 170929
65794 124071
132879 114996
59775 77370
21981 184939
126570 99223
145064 57285
79850 23370
119702 166072
129421 38217
135508 11036
127917 25887
164514 180432
179341 173905
14035 73244
119318 66318
8813 87341
160927 159199
52...

output:

0
0
16141
0
10015
0
0
0
0
28271
0
0
0
7075
0
41266
0
0
0
0
0
4
0
0
1
30027
0
0
24178
18749
1
26974
28781
0
1
0
16159
0
25019
0
0
6561
25180
0
0
0
0
1
5
1893
23472
1
1
38428
5860
0
0
17234
34629
3
0
0
41345
38579
30448
27287
0
41243
0
22976
35080
3
1
1
2
4094
0
1
0
20813
21249
39962
40796
0
0
25727
0...

result:

ok 200000 lines

Test #101:

score: 0
Accepted
time: 98ms
memory: 24768kb

input:

200000 26570
153476 91274
123148 3804
120794 153476
42999 1585
70024 23131
182377 153476
166100 120771
156110 175750
24159 153476
6582 145557
89649 26974
193443 92878
71361 153476
150007 75644
30239 136015
156707 65534
172259 153476
33914 61730
29702 137741
87758 64357
181535 148429
161108 104897
99...

output:

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

result:

ok 200000 lines

Test #102:

score: 0
Accepted
time: 103ms
memory: 28696kb

input:

200000 26667
36601 23808
132929 155021
182940 75779
187851 162525
84597 71608
13828 175096
169755 163437
115853 7479
191352 114906
18007 62601
32720 22079
97529 69025
15875 162741
133253 49516
103023 127317
59458 165453
154164 188750
16597 255
155820 139949
29489 191078
74270 104328
85993 144154
359...

output:

586
331
839
1142
260
485
727
609
781
108
931
39
891
74
987
740
186
61
20
969
133
481
119
1036
1037
108
1026
702
1120
478
111
371
227
203
617
106
730
226
66
540
370
282
1185
757
880
472
75
142
558
1024
1052
1143
285
711
700
476
515
1090
473
249
688
34
488
860
701
636
883
215
1092
926
413
641
210
709
...

result:

ok 200000 lines

Test #103:

score: 0
Accepted
time: 109ms
memory: 27232kb

input:

200000 38337
198525 101212
28808 182147
165257 172762
111077 158727
3650 33941
76447 779
87142 179711
15919 90846
123503 46784
40238 180813
116525 138968
165548 188775
177868 93299
39643 69724
55943 62429
199367 120818
32990 15186
169678 50904
720 142736
64791 44937
98744 4822
76888 57767
175144 527...

output:

581
1
5
12
164
456
243
98
187
262
4
2
0
0
546
325
327
267
349
0
252
317
254
519
397
2
2
27
2
277
362
1
1
320
465
2
0
0
63
191
2
137
62
508
1
4
3
189
419
630
160
574
0
94
2
192
1
0
601
1
1
534
0
94
217
2
0
599
316
485
460
134
449
300
6
388
243
214
0
96
395
308
290
208
246
451
189
222
396
454
173
381
...

result:

ok 200000 lines

Test #104:

score: 0
Accepted
time: 109ms
memory: 26768kb

input:

200000 31319
137318 127139
74448 114804
194292 59195
197606 60152
47787 19084
65789 78749
104327 166073
44230 75949
148497 194804
169752 137200
51573 85240
123119 69604
83397 164127
49255 143521
29025 6889
50129 121793
158585 104187
28309 76982
72345 11552
193749 190787
40699 9721
170659 80316
99673...

output:

0
222
0
0
0
324
117
0
1
32
3
262
124
1
0
6
4
163
2
0
319
0
101
92
0
1
288
259
0
1
12
321
207
19
97
2
0
324
0
20
0
345
335
1
41
1
335
0
1
0
69
2
0
2
144
166
242
0
331
306
27
105
2
3
0
0
2
0
0
27
25
0
2
239
0
3
0
161
0
0
1
14
1
0
2
0
2
1
0
39
0
287
2
0
347
284
1
4
0
2
1
3
3
0
1
263
142
2
3
0
0
131
0
2...

result:

ok 200000 lines

Test #105:

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

input:

200000 11494
16787 7415
158322 37647
182373 71312
196604 112467
35569 186256
193891 107853
117677 195649
158322 81051
121439 158322
2150 47802
125249 158322
158322 113299
79601 158322
61849 158322
88600 158322
158322 133062
105648 143025
64476 186970
28374 110442
158322 174798
115181 158322
64207 17...

output:

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

result:

ok 200000 lines

Test #106:

score: 0
Accepted
time: 123ms
memory: 38580kb

input:

200000 78797
23678 106280
171580 35971
108194 42720
80862 187319
97983 53147
18182 99348
189281 1944
119535 182546
66337 21929
42379 17983
122821 146292
11185 117085
35327 197694
67885 50313
1855 60663
132493 103572
157679 27790
17984 82866
27298 102920
165711 199343
145697 89486
37600 24304
84415 2...

output:

33922
15590
22112
30776
35451
18345
32194
1402
23543
20548
33325
27374
31632
10069
3207
11654
15363
14185
10842
33601
33608
1755
15361
3935
29587
20806
17929
15557
30375
14002
21449
20488
25553
23062
31541
31174
11642
13454
22322
24335
36773
15616
3212
35102
21130
26720
27133
8916
36026
26844
28768
...

result:

ok 200000 lines

Test #107:

score: 0
Accepted
time: 96ms
memory: 39232kb

input:

200000 12847
147771 45146
15473 70659
154963 19759
181374 54620
174601 154963
196445 146080
154963 40287
126670 83914
116469 164085
101651 70997
164457 189115
93026 98294
188674 154963
104339 52365
178079 189939
154963 30408
153922 14262
62929 106037
191207 84059
120583 114831
193506 139552
44829 17...

output:

9543
10218
12725
1
4935
12801
1
12432
12503
12784
2994
12580
7992
1
2
12045
1
0
12842
905
10506
1
4447
12742
1
11324
11082
1
2583
1
1
11130
12837
8085
12826
12842
2
1
12517
12779
1
11389
12710
12834
0
12705
1
1
12825
11992
12820
1
1
12825
1
1
1
1
12821
12529
3190
1
1
1
11856
3801
11543
1
12316
12552...

result:

ok 200000 lines

Test #108:

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

input:

200000 190067
128708 116050
12671 96937
13416 86375
73382 102662
30302 113726
90417 66033
56915 146361
184119 119217
47480 59525
181603 103140
99316 132961
59309 96441
119231 30762
101858 1161
93814 127438
56736 99282
178406 186937
40526 64697
128708 125241
35801 72558
166781 70162
128708 159745
194...

output:

0
9007
1409
1
4632
4
10835
0
1
0
5683
13564
3
0
1
2694
0
0
0
0
0
1811
10020
1
1
13672
1
5808
11821
0
1
0
1
9552
0
0
0
1
12285
14750
1
0
12288
1
1
1
2
8614
0
0
0
10370
0
0
5
6542
0
0
0
2
1
0
0
14225
1
0
0
0
1
14793
11851
1
11606
0
2
12041
8527
14069
12146
10454
3583
886
2
0
1
140
10752
848
9343
0
231...

result:

ok 200000 lines

Test #109:

score: 0
Accepted
time: 41ms
memory: 24976kb

input:

200000 99537
166492 152929
138418 166492
16690 166492
168689 166492
166492 13891
166492 174148
166492 11789
130447 166492
166492 44579
166492 150194
166492 148635
166492 19374
166492 158588
65542 166492
45401 166492
67862 166492
52684 166492
166492 57240
76649 166492
166492 195318
166492 6382
64189 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200000 lines

Test #110:

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

input:

200000 28692
98355 152391
164802 152773
112170 103109
112170 57898
112170 118406
53719 2131
44527 157577
30592 31956
111479 124537
75174 23287
142129 31153
14320 39809
139318 112170
112170 198585
8418 182781
36870 20135
112170 191943
76113 176699
55095 132340
85251 112170
28574 33674
51813 43611
913...

output:

1
1
27209
28360
28336
26357
18252
20512
25557
28218
27839
17293
1
16616
24234
15533
26093
25201
7416
1
27957
28144
19246
27006
20020
27825
1
1
28337
24992
28074
1
1
28202
28338
24896
6335
15384
1
26526
28259
1
28198
26345
1
1
19247
28360
24991
1
1
28142
14020
27460
27383
3053
1
27150
27935
28072
1
2...

result:

ok 200000 lines

Test #111:

score: 0
Accepted
time: 119ms
memory: 37208kb

input:

200000 87484
196389 196925
151542 6764
42386 113117
161192 24984
194242 83984
196925 99671
171093 196925
142005 32809
196925 113560
144926 178585
179177 117898
196925 6869
141615 173689
109136 196925
43505 120662
131154 83958
115714 114619
3714 15348
82716 95753
49657 11472
80224 124716
48489 91519
...

output:

0
19081
1
1
18192
0
0
0
0
1
24303
11042
1
1
1
0
0
1
0
0
0
1
12350
0
1
1
36108
13057
0
28797
0
35915
15012
5685
1
16953
26348
27125
26882
0
1581
6926
0
0
31021
1
0
34881
7385
0
0
30298
1
21378
0
966
1
0
0
0
20851
0
1
23040
1
0
1
0
1
0
7986
1
18906
0
537
29279
1
1
576
0
21790
0
17897
1
0
1
0
1
1
14140...

result:

ok 200000 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-11-29 19:55:10 | 开源项目