QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#33604#4206. Event HoppingSuffixTree#100 ✓64ms18644kbC++171.5kb2022-06-04 08:54:522024-05-26 00:09:20

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 61ms
memory: 18580kb

input:

100000 100000
825913690 825916363
333322014 333324481
302015784 302018251
841002775 841005448
810249910 810252583
803554045 803556718
379590599 379593066
413477311 413479778
304105333 304107800
856802878 856805551
355907399 355909866
365590374 365592841
813775597 813778270
816058339 816061012
383873...

output:

1
impossible
1
impossible
impossible
impossible
31336
impossible
impossible
impossible
impossible
27166
16274
impossible
impossible
impossible
impossible
impossible
impossible
21353
17890
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
67...

result:

ok 100000 lines

Test #2:

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

input:

100000 100000
389680865 389680885
532001242 532004287
460483812 460491583
691010527 691018298
489353103 489356770
593534107 593537042
509433341 509441112
846177578 846179089
586840272 586848043
834393248 834401019
474044207 474051978
614427322 614435093
574678657 574686428
557256443 557262524
502657...

output:

80801
80800
80800
80799
80799
80799
80798
80798
80798
80798
80797
80797
80797
80797
impossible
80796
80796
80796
80796
impossible
80797
80795
80795
80795
80795
impossible
80796
80796
80794
80794
80794
80794
impossible
80795
80795
80795
80794
80793
80793
80793
impossible
80794
80794
80794
80794
80793...

result:

ok 100000 lines

Test #3:

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

input:

100000 100000
1 2
1 2
5 6
5 6
9 10
9 10
13 14
13 14
17 18
17 18
21 22
21 22
25 26
25 26
29 30
29 30
33 34
33 34
37 38
37 38
41 42
41 42
45 46
45 46
49 50
49 50
53 54
53 54
57 58
57 58
61 62
61 62
65 66
65 66
69 70
69 70
73 74
73 74
77 78
77 78
81 82
81 82
85 86
85 86
89 90
89 90
93 94
93 94
97 98
97...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100000 lines

Test #4:

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

input:

100000 100000
407280099 407284136
197925316 197929353
463232919 463236956
248771331 248775368
314921613 314925650
454125447 454129484
215159269 215163306
376796712 376800749
343418796 343422833
126014235 126018272
315022538 315026575
242069911 242073948
479849211 479853248
414950399 414954436
254079...

output:

99999
99998
99998
99997
99997
99997
99996
99996
99996
99996
99995
99995
99995
99995
99995
99994
99994
99994
99994
99994
99994
99993
99993
99993
99993
99993
99993
99993
99992
99992
99992
99992
99992
99992
99992
99992
99991
99991
99991
99991
99991
99991
99991
99991
99991
99990
99990
99990
99990
99990
...

result:

ok 100000 lines

Test #5:

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

input:

100000 100000
861047815 861052922
578273225 578278332
622183211 622188318
822908739 822913846
546318726 546323833
461573168 461578275
480101364 480106471
456455954 456461061
575234560 575239667
464851862 464856969
897159412 897164519
722826860 722831967
755036709 755041816
811213709 811218816
445680...

output:

99999
99997
99995
99993
99991
99989
99987
99985
99983
99981
99979
99977
99975
99973
99971
99969
99967
99965
99963
99961
99959
99957
99955
99953
99951
99949
99947
99945
99943
99941
99939
99937
99935
99933
99931
99929
99927
99925
99923
99921
99919
99917
99915
99913
99911
99909
99907
99905
99903
99901
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 29ms
memory: 17140kb

input:

100000 100000
107067593 107068563
375121029 375132523
244489164 244489510
371625987 371628227
63502583 63505678
622119714 622149239
792197805 792202711
692512281 692515198
196552919 196554193
677923903 677926489
680041239 680046357
697562945 697565212
206418851 206420890
410143641 410145269
63943786...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100000 lines

Test #7:

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

input:

8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

output:

3
4
impossible
0
impossible

result:

ok 5 lines

Test #8:

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

input:

100000 100000
432053319 432056406
486393780 486396867
318945639 318948726
557737437 557740524
505903620 505906707
312861162 312864249
530084091 530087178
378401259 378404346
590749815 590752902
384158514 384161601
397824663 397827750
305937021 305940108
418238994 418242081
311718972 311722059
421174...

output:

99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
99999
...

result:

ok 100000 lines

Test #9:

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

input:

100000 100000
460767811 460773658
363280780 363286627
318744181 318750028
587618476 587624323
349815139 349820986
654104713 654110560
522640765 522646612
667874398 667880245
722245651 722251498
442864297 442870144
522664153 522670000
660805375 660811222
710639356 710645203
484196740 484202587
355358...

output:

77828
77828
77829
77828
77829
77827
77827
77829
77827
77826
77826
77828
77827
77826
77825
77825
77827
77826
77826
77825
impossible
77824
77826
77825
77825
77825
impossible
77824
77824
77825
77824
77824
77824
impossible
77824
77823
77823
77825
77823
77823
77823
impossible
77824
77823
77822
77823
7782...

result:

ok 100000 lines

Test #10:

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

input:

100000 100000
639515864 639521231
667143094 667144538
647258206 647258690
462233258 462234230
475801547 475802613
524127311 524128428
543287190 543289381
535841282 535843238
585211823 585213845
734658645 734658899
537776171 537783441
730349191 730354503
616233528 616234443
679161417 679162801
660817...

output:

1
1
2
1
2
impossible
1
2
impossible
impossible
1
2
impossible
impossible
impossible
1
2
impossible
impossible
impossible
impossible
1
2
impossible
impossible
impossible
impossible
impossible
1
2
impossible
impossible
impossible
impossible
impossible
impossible
1
2
impossible
impossible
impossible
im...

result:

ok 100000 lines

Test #11:

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

input:

100000 100000
164052333 164057764
912985943 912991682
753321224 753326963
252870907 252876338
171530820 171536251
236458425 236463856
250957493 250957879
174416256 174416562
183948393 183949360
197480808 197481798
860359313 860365052
230757856 230757886
873570491 873576230
156416347 156421778
276301...

output:

1
1
1
impossible
impossible
impossible
impossible
impossible
7192
impossible
impossible
impossible
25139
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
13851
impossible
impossible
impossible
impossible
impossible
impossible
20104
impossible
impossi...

result:

ok 100000 lines

Test #12:

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

input:

100000 100000
315393285 315400120
494155875 494162710
292427685 292434520
447445485 447452320
395815906 395818904
573530730 573537565
368815645 368822480
424944665 424951500
688228865 688235700
742956710 742963545
690696300 690703135
467270322 467271382
746182830 746189665
642078945 642085780
628101...

output:

90192
90191
90191
90190
90190
90190
90189
90189
90189
90189
90188
90188
90188
90188
impossible
90187
90187
90187
90187
impossible
90188
90186
90186
90186
90186
impossible
90187
90187
90185
90185
90185
90185
impossible
90186
90186
90186
90184
90184
90184
90184
impossible
90185
90185
90185
90185
90183...

result:

ok 100000 lines

Subtask #2:

score: 10
Accepted

Test #13:

score: 10
Accepted
time: 1ms
memory: 8168kb

input:

1000 100
67878298 387720407
270457472 922959000
286470357 618323410
260791474 282940414
301337446 553875076
478221503 724555102
380447228 437131400
191801427 465825895
366088873 431222136
49483883 103442781
699926238 720636919
253150351 291688158
411085513 727726933
444078045 496386017
420626857 822...

output:

1
2
2
impossible
1
2
1
2
impossible
2
2
impossible
impossible
impossible
1
impossible
impossible
impossible
impossible
impossible
2
impossible
2
impossible
1
1
impossible
1
1
1
1
impossible
2
impossible
2
impossible
1
1
impossible
impossible
impossible
1
2
impossible
impossible
1
2
impossible
imposs...

result:

ok 100 lines

Test #14:

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

input:

1000 100
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 100...

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

result:

ok 100 lines

Test #15:

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

input:

1000 100
219652137 219887840
411750082 411985785
295784206 296019909
323361457 323597160
263257192 263492895
228373148 228608851
311812010 312047713
189246450 189482153
197024649 197260352
214230968 214466671
209045502 209281205
282113432 282349135
277870778 278106481
394308060 394543763
318175991 3...

output:

999
998
998
997
997
997
996
996
996
996
995
995
995
995
995
994
994
994
994
994
994
993
993
993
993
993
993
993
992
992
992
992
992
992
992
992
991
991
991
991
991
991
991
991
991
990
990
990
990
990
990
990
990
990
990
989
989
989
989
989
989
989
989
989
989
989
988
988
988
988
988
988
988
988
988
...

result:

ok 100 lines

Test #16:

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

input:

1000 100
146460236 650840147
213248988 712234443
271625877 765585418
268035474 762542588
155957999 659365570
108300122 614352264
161735587 665204546
244432982 734605513
84404294 596250403
472975048 964576612
128756912 628710941
130473656 631636782
324178293 813816145
197620586 692901130
353485130 84...

output:

impossible
1
impossible
impossible
1
impossible
impossible
impossible
1
1
impossible
1
impossible
1
impossible
impossible
1
1
impossible
impossible
1
impossible
1
1
1
impossible
impossible
impossible
impossible
1
1
1
impossible
impossible
impossible
impossible
1
1
impossible
impossible
1
1
1
1
impos...

result:

ok 100 lines

Test #17:

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

input:

1000 100
734527256 734722851
176171640 176781511
73713312 74323183
347545391 348155262
741959866 742155461
727094646 727290241
304244550 304854421
256064741 256674612
692278736 692474331
678391491 678587086
757020681 757216276
324370293 324980164
327419648 328029519
720248821 720444416
253015386 253...

output:

1
impossible
1
impossible
246
334
impossible
impossible
impossible
477
impossible
379
impossible
impossible
393
196
impossible
271
122
impossible
impossible
impossible
impossible
impossible
207
impossible
impossible
190
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100 lines

Test #18:

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

input:

1000 100
549 550
689 690
273 274
760 761
414 415
639 640
420 421
592 593
308 309
55 56
952 953
181 182
2 3
476 477
262 263
329 330
261 262
875 876
78 79
711 712
771 772
871 872
328 329
585 586
185 186
471 472
191 192
611 612
758 759
538 539
24 25
518 519
903 904
748 749
547 548
435 436
81 82
459 460...

output:

impossible
impossible
impossible
554
impossible
impossible
impossible
661
712
333
impossible
impossible
impossible
impossible
impossible
impossible
329
impossible
101
416
impossible
268
impossible
676
impossible
131
impossible
impossible
impossible
337
impossible
417
impossible
231
impossible
146
im...

result:

ok 100 lines

Test #19:

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

input:

1000 100
41916637 42739142
57513660 58326077
21867551 172652993
148410501 243619298
80759769 81439087
1165860 77201426
122988614 155997027
100181236 100563028
185001902 185375949
176810589 177691863
141890410 142849915
92309958 240703409
40538462 236387490
22164234 22167602
144201862 144991292
19678...

output:

2
1
2
impossible
impossible
impossible
impossible
1
1
3
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
1
2
impossible
impossible
impossible
impossible
1
impossible
impossible
2
impossible
2
impossible
1
impossible
impossible
impossible
i...

result:

ok 100 lines

Test #20:

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

input:

5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

output:

2
impossible

result:

ok 2 lines

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #21:

score: 15
Accepted
time: 18ms
memory: 9532kb

input:

5000 100000
444771902 444813193
517939554 517980845
420657958 420699249
565300331 565341622
489902965 489944256
550146534 550187825
621579964 621621255
541970916 542012207
504932889 504974180
509970391 510011682
548990386 549031677
531606875 531648166
611628833 611670124
424167693 424208984
43593562...

output:

4999
4998
4998
4997
4997
4997
4996
4996
4996
4996
4995
4995
4995
4995
4995
4994
4994
4994
4994
4994
4994
4993
4993
4993
4993
4993
4993
4993
4992
4992
4992
4992
4992
4992
4992
4992
4991
4991
4991
4991
4991
4991
4991
4991
4991
4990
4990
4990
4990
4990
4990
4990
4990
4990
4990
4989
4989
4989
4989
4989
...

result:

ok 100000 lines

Test #22:

score: 0
Accepted
time: 18ms
memory: 12696kb

input:

5000 100000
688560220 703238347
121237680 134739514
589367489 602957567
728869127 745336729
9219545 23878334
488274497 501448797
849072503 861443731
23334524 37448893
956275044 970586285
583628356 597394100
810104747 824856103
110253553 124899493
522891845 536665379
912913517 928831291
329446513 344...

output:

72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
72
...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 19ms
memory: 13444kb

input:

5000 100000
464713443 865027233
131041097 776120588
45181466 960870814
305598230 729604420
388398945 419250976
829797468 854954202
59180550 180848104
418991469 450843968
275526402 990751155
640426851 978213959
46548208 208716873
689084357 728560507
219423180 394015921
201718277 911951270
258428409 5...

output:

impossible
2
impossible
impossible
1
impossible
impossible
1
2
impossible
impossible
impossible
2
1
2
impossible
impossible
impossible
impossible
impossible
2
impossible
impossible
impossible
impossible
impossible
1
1
1
1
2
impossible
2
impossible
impossible
impossible
2
impossible
2
2
1
impossible
...

result:

ok 100000 lines

Test #24:

score: 0
Accepted
time: 14ms
memory: 12804kb

input:

5000 100000
3332 8295
1298 1301
3332 6719
256 259
3332 7099
3100 3103
3332 7455
3332 7206
3332 6992
2222 2225
3332 7911
3332 5859
3332 5283
882 885
3332 7140
3332 7799
3332 8188
3332 5152
684 687
3332 8006
3332 6388
3332 5578
2296 2299
3332 6404
3332 6117
3332 6889
3332 8013
3332 6673
766 769
3214 3...

output:

1666
1665
1666
1664
1665
1666
1663
1664
1665
1666
1662
1663
1664
1665
1666
1661
1662
1663
1664
1665
1666
1660
1661
1662
1663
1664
1665
1666
1659
1660
1661
1662
1663
1664
1665
1666
1658
1659
1660
1661
1662
1663
1664
1665
1666
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1656
1657
1658
1659
1660
...

result:

ok 100000 lines

Test #25:

score: 0
Accepted
time: 19ms
memory: 12980kb

input:

5000 100000
106741929 106921680
156160205 175598414
216333515 216371881
237965835 238081617
168929422 187733290
117356436 117550772
106097434 106256274
1190918 250349491
192208804 192332169
49069875 49210901
100968287 122786354
118052438 118153860
79495925 79616884
20277321 219406065
37893097 379428...

output:

impossible
2
1
impossible
1
impossible
impossible
impossible
impossible
2
impossible
1
1
2
1
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
2
impossible
2
2
impossible
impossible
impossible
impossible
impossible
impossible
1
impossible
impossible
2
impossible...

result:

ok 100000 lines

Test #26:

score: 0
Accepted
time: 13ms
memory: 13208kb

input:

5000 100000
16556641 518715667
35819610 537917279
160182127 659847537
412975745 911120150
343031225 840328922
173114086 673351051
308055584 805641921
450309603 946317782
136721684 634969297
262246714 761137290
199423249 700712784
59770455 558589524
495643630 994130260
214959376 715949915
473575893 9...

output:

1
1
impossible
1
impossible
1
impossible
impossible
impossible
1
impossible
1
impossible
1
1
impossible
impossible
1
1
impossible
impossible
impossible
1
1
impossible
1
impossible
1
impossible
impossible
impossible
1
impossible
impossible
impossible
1
1
impossible
impossible
impossible
1
1
impossibl...

result:

ok 100000 lines

Test #27:

score: 0
Accepted
time: 19ms
memory: 12900kb

input:

5000 100000
1029 1030
4728 4729
1779 1780
4341 4342
3223 3224
1826 1827
2210 2211
685 686
1419 1420
1845 1846
3074 3075
3071 3072
1449 1450
1838 1839
642 643
2374 2375
2864 2865
1246 1247
112 113
3623 3624
705 706
4367 4368
241 242
4432 4433
893 894
2121 2122
1925 1926
1203 1204
2151 2152
4107 4108
...

output:

impossible
2645
impossible
3625
impossible
73
impossible
impossible
impossible
1385
impossible
294
impossible
impossible
impossible
1201
218
197
1406
425
3081
impossible
impossible
impossible
2713
3044
impossible
469
168
impossible
impossible
2168
impossible
3505
593
impossible
impossible
impossible...

result:

ok 100000 lines

Subtask #4:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #28:

score: 15
Accepted
time: 24ms
memory: 16064kb

input:

100000 100
339859414 339860443
735166371 735174392
348212836 348213865
888215072 888223093
792396206 792404227
329405875 329405966
323863609 323864638
349411621 349412650
805520775 805526215
780236547 780238983
878461536 878469557
329490782 329490797
689599070 689607091
333606181 333607210
778431645...

output:

1
impossible
1
1
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
27759
impossible
impossible
impossible
6549
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossib...

result:

ok 100 lines

Test #29:

score: 0
Accepted
time: 19ms
memory: 16344kb

input:

100000 100
280307395 780690393
181760327 682061905
249141989 749145209
101786854 602796452
340240072 840752657
462512152 963603974
278949510 779337310
449036112 949680311
109301519 610340212
150526076 651104530
358730138 858979032
68024728 568795044
246222731 746352341
323835391 824440662
17574686 5...

output:

impossible
1
1
impossible
impossible
impossible
impossible
1
1
impossible
1
1
1
1
impossible
1
impossible
1
1
1
1
impossible
impossible
1
1
impossible
1
1
1
impossible
1
1
impossible
1
1
1
impossible
1
1
1
1
impossible
1
1
1
impossible
impossible
impossible
impossible
1
impossible
1
1
1
1
1
1
1
impo...

result:

ok 100 lines

Test #30:

score: 0
Accepted
time: 24ms
memory: 16336kb

input:

100000 100
37531 37532
31892 31893
34221 34222
44773 44774
89978 89979
21900 21901
61685 61686
82235 82236
36098 36099
28834 28835
84481 84482
70886 70887
82077 82078
41874 41875
46072 46073
35264 35265
35193 35194
4306 4307
64390 64391
9820 9821
6247 6248
12022 12023
41716 41717
31919 31920
13011 1...

output:

25296
31189
impossible
impossible
37894
48145
53829
12181
32792
impossible
6662
12366
27899
impossible
impossible
87018
impossible
46497
21534
54333
18163
impossible
impossible
12578
29638
impossible
2822
8396
impossible
59485
impossible
impossible
56389
29711
impossible
impossible
impossible
35036
...

result:

ok 100 lines

Test #31:

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

input:

100000 100
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 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

result:

ok 100 lines

Test #32:

score: 0
Accepted
time: 24ms
memory: 16328kb

input:

100000 100
994730204 997656824
997559746 999567570
437348231 440622053
186684423 190058231
354732010 357982869
88038861 91159348
586962168 590266642
589162214 592446488
887112000 890350184
558903873 562255286
137259291 140476440
75063570 78383641
73162753 76265253
817355711 820703630
124571212 12768...

output:

317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
...

result:

ok 100 lines

Test #33:

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

input:

100000 100
469284050 469287411
619016600 619019961
614909458 614912819
654522204 654525565
689268222 689271583
498202094 498205455
679480990 679484351
417423820 417427181
611813977 611817338
498124791 498128152
638681811 638685172
436544549 436547910
526226112 526229473
524451504 524454865
735169399...

output:

99999
99998
99998
99997
99997
99997
99996
99996
99996
99996
99995
99995
99995
99995
99995
99994
99994
99994
99994
99994
99994
99993
99993
99993
99993
99993
99993
99993
99992
99992
99992
99992
99992
99992
99992
99992
99991
99991
99991
99991
99991
99991
99991
99991
99991
99990
99990
99990
99990
99990
...

result:

ok 100 lines

Test #34:

score: 0
Accepted
time: 18ms
memory: 16424kb

input:

100000 100
6059124 201337475
38781686 38782031
4828068 4829350
55491778 55496029
44594840 53249244
157539214 157543225
6323925 234008984
4875446 248654555
672428 203042073
75561632 75565875
181604802 181605327
78707086 78710336
101917893 140682994
16658418 16662566
44321226 44327781
238892713 238895...

output:

2
impossible
2
impossible
2
impossible
impossible
3
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
2
2
1
impossible
1
impossible
1
impossible
impossible
impossible
1
impossible
impossible
1
3
impossible
impossible
impossible
impossible
impossible
impossible
2...

result:

ok 100 lines

Subtask #5:

score: 20
Accepted

Test #35:

score: 20
Accepted
time: 45ms
memory: 17352kb

input:

100000 100000
903318459 905410836
903528407 905653109
925180437 927048927
473524826 475597377
362562616 364539688
644980844 646918450
242583398 244653279
506338025 508361063
481496693 483530832
970053326 972147109
794840350 796900045
130664210 132709680
634100524 636336820
844429264 846504591
652483...

output:

500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
500
...

result:

ok 100000 lines

Test #36:

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

input:

100000 100000
280978238 281996879
128582305 129520369
326480847 327450886
613575910 614525870
773187456 774194521
499427531 500501109
206817453 207828231
147432355 148457712
276397611 277442951
238269352 239211898
864332415 865500617
189404293 190348043
898692256 899607594
395766418 396755456
306101...

output:

impossible
434
impossible
248
338
332
390
impossible
607
771
246
impossible
421
impossible
628
117
549
impossible
impossible
impossible
382
impossible
495
impossible
impossible
357
impossible
522
impossible
54
impossible
impossible
impossible
464
impossible
impossible
225
255
484
60
86
244
579
363
7...

result:

ok 100000 lines

Test #37:

score: 0
Accepted
time: 36ms
memory: 17364kb

input:

100000 100000
315328227 565342348
172493343 423278396
47077854 218308141
77736924 280882803
578420376 829121844
456477365 706164084
572351871 823109648
47238838 218708768
818302749 971917023
250574858 500783122
101021436 327649552
386731775 636229046
560750614 811328057
649806442 888787931
89426598 ...

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 100000 lines

Test #38:

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

input:

100000 100000
532703099 533766917
18747285 19717390
259741440 260161102
33247104 34339796
221460611 222216066
101759380 103356345
868641980 869660917
400488522 402221013
626943992 628192337
732367406 733994895
796371835 798306228
496636511 498600178
946211536 947345154
866952254 868236697
743150932 ...

output:

impossible
367
impossible
impossible
105
3
impossible
12
impossible
impossible
8
impossible
108
impossible
impossible
impossible
126
impossible
impossible
impossible
impossible
impossible
251
impossible
impossible
impossible
impossible
impossible
277
54
impossible
impossible
50
impossible
34
impossi...

result:

ok 100000 lines

Test #39:

score: 0
Accepted
time: 37ms
memory: 17352kb

input:

100000 100000
92218679 95179758
317492416 320745639
733100351 736164573
961855441 965128977
837782167 840987990
17497768 20657218
448274654 451383491
900836773 903892815
285698089 288672515
717206068 720360660
350272947 353502098
539452749 542535367
320153387 323421078
549859328 552774077
407596307 ...

output:

317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
317
...

result:

ok 100000 lines

Test #40:

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

input:

100000 100000
744013029 744524903
471220871 471690214
120307805 120799735
926899213 927378946
753737949 754240556
361494837 361945312
133903676 134394731
330399973 330949740
34749028 35247553
430334132 430795521
362526758 363012637
266295097 266798513
702502851 703011578
848053622 848544848
78244603...

output:

impossible
685
impossible
1091
162
impossible
impossible
impossible
321
345
impossible
impossible
369
impossible
impossible
impossible
945
404
impossible
impossible
151
349
impossible
923
impossible
1194
654
impossible
impossible
impossible
333
89
975
1373
impossible
203
282
537
impossible
579
impos...

result:

ok 100000 lines

Subtask #6:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #41:

score: 30
Accepted
time: 51ms
memory: 18588kb

input:

100000 100000
45338 45339
20395 1000000000
6585 6586
931 1000000000
923 1000000000
24298 1000000000
40846 40847
4076 4077
24494 24495
74342 74343
24688 1000000000
47492 47493
31668 31669
30225 30226
43598 43599
9419 1000000000
64728 64729
12267 12268
3980 1000000000
11332 11333
43692 43693
26667 266...

output:

impossible
9000
impossible
1
impossible
1
impossible
40444
impossible
impossible
34781
impossible
impossible
impossible
1
impossible
44933
2
impossible
impossible
10591
1
1
43245
impossible
8266
impossible
28258
64748
impossible
9242
40573
impossible
11864
impossible
1
impossible
impossible
1
imposs...

result:

ok 100000 lines

Test #42:

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

input:

100000 100000
541959065 754638675
594740335 751073689
765443594 961718898
231375507 798855755
66471236 950465813
290764047 483071588
4154672 10830377
882221874 922991215
187151153 867730791
48863332 905081761
189566492 503939677
112976248 418891667
294016427 992655870
690795398 764996187
610602517 9...

output:

impossible
2
impossible
1
impossible
1
impossible
impossible
impossible
1
1
impossible
impossible
2
1
1
2
impossible
impossible
2
impossible
1
2
impossible
impossible
2
1
2
1
impossible
1
impossible
impossible
impossible
impossible
2
impossible
impossible
impossible
impossible
2
impossible
1
1
1
imp...

result:

ok 100000 lines

Test #43:

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

input:

100000 100000
19542271 191089782
149032073 149041707
181429167 181435991
101779997 101784930
81055203 81059415
15708062 241024787
49045930 49048523
233862992 233863783
17677880 17684809
168245654 168246413
3139902 203969327
143708592 143711797
73844607 73849510
32115298 32122898
28097294 82643864
11...

output:

impossible
impossible
impossible
1
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
1
2
2
impossible
impossible
impossible
2
1
2
1
impossible
impossible
2
1
impossible
2
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 100000 lines

Test #44:

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

input:

100000 100000
53056 53057
17318 17319
1467 1468
60695 60696
76776 76777
99652 99653
60218 60219
53395 53396
48308 48309
52994 52995
96609 96610
92674 92675
25891 25892
34172 34173
98219 98220
35088 35089
7180 7181
44768 44769
64496 64497
152 153
22533 22534
47935 47936
25034 25035
68015 68016
19299 ...

output:

34766
8061
52428
11249
impossible
impossible
impossible
impossible
73992
65993
25713
48341
impossible
31006
impossible
impossible
9749
impossible
impossible
64939
impossible
28197
impossible
6805
impossible
impossible
impossible
impossible
2041
14422
15656
impossible
3590
impossible
impossible
impos...

result:

ok 100000 lines

Test #45:

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

input:

100000 100000
778620172 931549055
135677879 418338032
461194727 517884862
91978453 263976981
653770031 883360138
315818226 863893161
356572897 716843878
397544805 403463335
461701209 850667358
366165671 507516502
692235054 805140271
315474989 630038373
138385340 426648757
10964737 751149399
81940890...

output:

1
1
1
impossible
1
impossible
1
1
1
1
impossible
2
1
impossible
1
impossible
impossible
impossible
2
impossible
impossible
2
impossible
impossible
1
2
2
2
1
impossible
1
1
1
impossible
1
2
impossible
impossible
1
impossible
1
1
1
1
1
2
1
impossible
impossible
2
impossible
impossible
impossible
impos...

result:

ok 100000 lines

Test #46:

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

input:

100000 100000
218439861 218440431
122945853 122946125
61992595 61995529
230500806 230504632
221859690 221869444
155859983 205637253
126985523 126994883
130348312 130350747
176199072 176208829
8150056 8159893
49670926 186564148
127256248 197517947
245268715 245276112
48141792 48146670
171651649 17165...

output:

1
impossible
impossible
1
3
2
impossible
impossible
1
1
1
impossible
impossible
3
impossible
2
1
impossible
impossible
impossible
impossible
impossible
1
impossible
1
impossible
impossible
1
2
2
impossible
impossible
1
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impo...

result:

ok 100000 lines