QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533335#1139. StationsMinaRagy06#5 48ms4100kbC++20943b2024-08-25 20:29:342024-08-25 20:29:34

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 36ms
memory: 3756kb

input:

0
10
10 1000
4 5
9 0
2 6
5 2
8 3
1 4
8 1
6 0
3 7
3 1000
0 1
1 2
998 1000
166 178
393 452
389 179
622 429
892 866
872 18
899 227
835 637
587 769
504 386
369 577
65 441
523 17
803 221
878 321
637 892
696 473
16 146
840 322
495 986
353 275
330 585
831 402
719 810
704 830
780 940
53 901
894 911
394 482
...

output:

10
8
3
6
1
4
5
7
0
2
9
3
0
1
2
998
218
223
165
11
508
816
365
369
132
114
329
529
80
787
608
66
447
270
680
519
863
579
434
687
402
709
718
962
818
320
207
839
801
701
976
339
454
107
846
907
255
6
307
23
314
963
240
105
373
478
587
139
909
572
584
903
4
136
265
468
198
878
121
243
158
40
76
163
558...

input:

1
59784
0 1 1
1
730 818 2
729
731
0 1 1
1
303 620 2
302
304
3 2 1
2
1 0 1
0
0 1 1
1
931 112 2
930
932
2 0 2
1
3
0 1 1
1
948 832 2
947
949
7 6 2
6
8
27 639 2
26
28
131 800 2
130
132
377 250 2
376
378
570 874 2
569
571
0 1 1
1
7 41 2
6
8
1 2 2
0
2
0 1 1
1
919 92 2
918
920
1 0 1
0
466 117 2
465
467
0 1...

output:

1
731
1
304
2
0
1
930
1
1
947
6
28
132
376
571
1
8
2
1
918
0
465
1
1
993
2
0
0
478
98
277
2
7
40
0
391
92
5
1
7
488
449
389
89
679
183
891
552
14
1
478
300
2
1
1
2
810
1
6
0
0
389
540
934
65
65
0
0
283
707
250
414
0
584
936
1
2
141
1
2
667
1
566
1
75
162
722
7
7
7
1
55
6
2
732
586
661
1
841
788
624
...

result:

ok 

Test #2:

score: 5
Accepted
time: 32ms
memory: 3800kb

input:

0
10
999 1000
235 825
647 906
541 62
613 565
578 619
248 881
769 526
994 607
456 840
66 498
55 390
563 846
932 717
568 140
443 49
369 210
721 37
431 796
632 398
861 25
724 153
403 851
688 315
803 191
213 469
339 674
166 517
236 859
67 199
867 510
804 372
820 443
628 483
835 200
692 488
295 42
5 140
...

output:

999
124
983
716
420
968
575
827
330
603
20
674
111
869
591
570
136
852
363
356
121
249
182
122
188
979
966
652
261
605
563
141
520
663
463
399
731
647
681
491
398
163
890
545
127
883
418
518
817
944
482
822
297
403
981
360
454
142
773
842
206
917
393
259
550
341
335
938
919
422
568
922
630
914
426
9...

input:

1
50048
666 56 2
665
667
867 546 2
866
868
754 101 2
753
755
893 730 2
892
894
648 198 2
647
649
830 222 2
829
831
933 284 2
932
934
756 352 2
755
757
803 772 2
802
804
805 221 2
804
806
874 539 2
873
875
944 910 2
943
945
236 38 2
235
237
541 94 2
540
542
233 140 2
232
234
42 319 2
41
43
148 27 2
1...

output:

665
866
753
892
647
829
932
755
802
804
873
943
235
540
232
43
147
977
504
111
360
173
739
228
394
289
473
546
481
634
128
395
526
715
29
543
611
509
339
802
601
223
411
317
901
569
550
232
94
956
329
978
290
446
400
603
976
383
503
596
450
41
399
416
19
65
688
260
232
252
252
746
934
936
244
67
62
...

result:

ok 

Test #3:

score: 5
Accepted
time: 48ms
memory: 3752kb

input:

0
10
2 1000
1 0
2 1000
0 1
2 1000
0 1
2 1000
0 1
2 1000
0 1
2 1000
0 1
2 1000
0 1
2 1000
1 0
2 1000
1 0
2 1000
0 1

output:

2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1

input:

1
100000
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0...

output:

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

result:

ok 

Test #4:

score: 5
Accepted
time: 40ms
memory: 3800kb

input:

0
10
3 1000
2 1
0 1
3 1000
0 1
2 1
3 1000
2 1
0 1
3 1000
2 0
2 1
3 1000
2 0
1 0
3 1000
2 0
0 1
3 1000
1 0
2 1
3 1000
1 2
0 1
3 1000
0 1
1 2
3 1000
2 0
0 1

output:

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

input:

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

output:

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

result:

ok 

Test #5:

score: 5
Accepted
time: 36ms
memory: 3800kb

input:

0
10
4 1000
0 2
3 1
0 3
4 1000
3 1
3 0
2 1
4 1000
2 0
1 3
3 0
4 1000
0 3
1 2
2 3
4 1000
1 2
0 1
2 3
4 1000
1 3
2 0
2 3
4 1000
1 3
1 0
3 2
4 1000
3 0
1 0
2 1
4 1000
3 2
0 1
3 1
4 1000
1 2
1 0
2 3

output:

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

input:

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

output:

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

result:

ok 

Test #6:

score: 5
Accepted
time: 32ms
memory: 3828kb

input:

0
10
1000 1000
387 293
176 887
976 264
923 398
736 598
406 187
658 331
596 105
514 857
33 784
81 15
194 397
768 286
406 42
586 521
503 384
663 326
451 514
658 489
849 120
531 769
428 756
81 283
14 519
359 542
807 685
707 278
738 700
865 839
728 657
166 155
980 440
364 448
879 37
833 524
358 421
458 ...

output:

1000
724
316
559
445
798
438
571
115
487
620
66
500
675
269
782
179
524
71
716
740
442
910
928
550
744
69
530
343
271
670
54
714
292
889
549
19
186
155
63
296
105
878
545
846
32
266
767
514
732
161
668
338
360
978
70
587
700
0
64
432
202
471
13
142
31
644
852
402
200
472
597
893
661
891
75
591
861
2...

input:

1
50055
875 537 2
874
876
943 948 2
942
944
277 344 2
276
278
41 428 2
40
42
638 231 2
637
639
444 822 2
443
445
873 943 2
872
874
30 730 2
29
31
4 311 2
3
5
952 530 2
951
953
400 455 2
399
401
219 405 2
218
220
838 880 2
837
839
634 520 2
633
635
586 719 2
585
587
499 482 2
498
500
562 455 2
561
56...

output:

874
944
278
42
637
445
874
31
5
951
401
220
839
633
587
498
561
732
454
930
256
118
65
359
149
998
86
670
722
307
928
536
175
309
123
243
109
95
538
295
783
934
611
350
948
451
627
463
333
390
862
660
508
392
422
605
231
401
935
130
63
35
942
240
797
542
620
195
84
13
586
957
938
473
39
736
942
655
...

result:

ok 

Test #7:

score: 5
Accepted
time: 32ms
memory: 3820kb

input:

0
1
1000 1000
502 584
460 198
192 539
565 266
519 363
448 97
907 459
427 458
694 915
546 555
23 843
177 257
733 258
98 274
983 648
708 132
685 763
616 357
880 61
772 108
967 710
238 549
117 105
737 775
495 935
586 688
808 121
970 747
798 332
958 750
58 830
829 120
34 964
168 357
886 646
241 920
100 ...

output:

1000
748
389
97
178
98
278
967
167
726
919
134
353
49
778
144
618
42
519
444
146
526
441
638
762
694
153
450
542
468
904
995
244
843
409
811
174
225
366
741
590
940
347
758
267
482
359
985
493
757
126
513
176
241
974
672
903
592
697
709
58
44
317
105
10
465
947
327
760
567
112
96
257
633
623
64
939
...

input:

1
50046
219 561 2
218
220
868 482 2
867
869
49 499 2
48
50
864 818 2
863
865
771 425 2
770
772
615 746 2
614
616
604 258 2
603
605
878 7 2
877
879
628 796 2
627
629
818 912 2
817
819
992 109 2
991
993
927 957 2
926
928
750 963 2
749
751
497 511 2
496
498
34 570 2
33
35
943 767 2
942
944
22 856 2
21
...

output:

220
867
50
863
770
616
603
877
629
819
991
928
751
498
35
942
23
928
301
624
829
649
52
372
103
541
89
964
432
467
25
390
384
672
972
235
657
125
782
672
498
331
658
39
664
324
332
213
525
235
904
480
172
933
745
430
734
83
799
116
574
433
482
894
924
315
13
301
442
496
834
38
310
130
773
331
661
14...

result:

ok 

Test #8:

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

input:

0
10
4 1000
0 1
1 2
2 3
4 1000
0 1
1 3
3 2
4 1000
0 2
2 1
1 3
4 1000
0 2
2 3
3 1
4 1000
0 3
3 1
1 2
4 1000
0 3
3 2
2 1
4 1000
1 0
0 2
2 3
4 1000
1 0
0 3
3 2
4 1000
1 2
2 0
0 3
4 1000
1 3
3 0
0 2

output:

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

input:

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

output:

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

result:

ok 

Test #9:

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

input:

0
10
6 1000
0 1
1 2
2 3
3 4
4 5
6 1000
0 1
1 2
2 3
3 5
5 4
6 1000
0 1
1 2
2 4
4 3
3 5
6 1000
0 1
1 2
2 4
4 5
5 3
6 1000
0 1
1 2
2 5
5 3
3 4
6 1000
0 1
1 2
2 5
5 4
4 3
6 1000
0 1
1 3
3 2
2 4
4 5
6 1000
0 1
1 3
3 2
2 5
5 4
6 1000
0 1
1 3
3 4
4 2
2 5
6 1000
0 1
1 3
3 4
4 5
5 2

output:

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

input:

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

output:

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

result:

ok 

Test #10:

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

input:

0
3
3 1000
0 1
1 2
3 1000
0 2
2 1
3 1000
1 0
0 2

output:

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

input:

1
18
1 0 2
0
2
1 2 2
0
2
2 1 1
1
2 0 1
1
1 2 2
0
2
1 0 2
0
2
2 0 1
1
2 0 1
1
0 1 1
1
1 2 2
0
2
0 2 1
1
0 2 1
1
2 1 1
1
0 1 1
1
0 1 1
1
0 2 1
1
1 0 2
0
2
2 1 1
1

output:

0
2
1
1
2
0
1
1
1
2
1
1
1
1
1
1
0
1

result:

ok 

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 18ms
memory: 3800kb

input:

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

output:

996
8
9
7
10
265
520
6
11
138
266
393
521
648
775
5
12
75
139
202
267
330
394
457
522
585
649
712
776
839
902
4
13
44
76
107
140
171
203
234
268
299
331
362
395
426
458
489
523
554
586
617
650
681
713
744
777
808
840
871
903
934
3
965
14
29
45
60
77
92
108
123
141
156
172
187
204
219
235
250
269
284...

input:

1
50252
740 386 1
738
862 141 1
861
976 534 1
974
421 396 1
420
867 227 1
865
433 933 1
432
718 724 1
716
446 788 1
444
723 764 3
722
724
725
873 474 3
872
874
877
976 27 1
974
607 155 3
603
608
609
792 527 1
790
415 931 1
413
303 8 1
302
83 159 1
82
874 940 3
873
875
876
299 322 3
267
300
315
373 6...

output:

738
861
974
420
865
432
716
444
724
872
974
603
790
413
302
82
875
300
372
988
944
874
723
157
387
924
221
769
694
903
902
888
783
372
300
517
620
778
312
471
859
420
973
905
424
58
178
697
850
144
175
380
931
65
842
3
344
947
636
238
690
909
199
454
874
660
459
113
278
224
762
699
611
105
5
775
833...

result:

wrong answer Diff at 9-th number: read 724 but expected 722

Subtask #3:

score: 0
Wrong Answer

Test #17:

score: 16
Accepted
time: 36ms
memory: 3820kb

input:

0
10
2 1000000
1 0
997 1000000
830 513
223 672
727 200
763 415
581 440
34 42
267 325
912 693
753 59
401 289
198 641
982 214
41 49
453 107
940 806
905 732
153 482
248 405
102 79
480 837
534 620
564 856
679 178
278 247
899 206
333 672
297 308
407 863
26 752
272 178
204 603
208 10
715 562
785 285
184 5...

output:

2
0
1
997
863
612
436
285
792
563
338
572
483
827
204
749
886
233
379
407
936
880
818
947
702
378
681
426
691
970
193
75
243
464
891
841
788
523
258
488
467
637
781
157
950
706
259
628
724
275
56
94
358
707
591
751
565
133
561
129
946
65
254
148
277
295
251
0
850
929
512
983
63
228
861
291
821
1
853...

input:

1
59859
5 9 2
4
6
1 0 1
0
1 0 1
0
31 85 2
30
32
293 395 2
292
294
732 134 2
731
733
0 1 1
1
2 4 2
1
3
122 328 2
121
123
0 1 1
1
0 1 1
1
1 0 1
0
1 2 2
0
2
897 689 2
896
898
371 213 2
370
372
511 503 2
510
512
7 3 2
6
8
2 1 1
1
570 360 2
569
571
68 81 2
67
69
442 416 2
441
443
384 763 2
383
385
975 95...

output:

6
0
0
32
294
731
1
3
123
1
1
0
2
896
370
510
6
1
569
69
441
385
974
977
2
172
361
191
1
2
245
4
456
1
0
2
369
326
206
2
489
187
989
642
8
1
918
408
976
2
227
1
457
673
19
44
1
66
0
0
1
5
5
40
604
830
60
1
320
2
268
340
32
1
567
2
864
754
2
716
1
66
519
1
1
705
1
374
1
693
39
2
1
1
267
7
1
1
394
1
90...

result:

ok 

Test #18:

score: 16
Accepted
time: 32ms
memory: 3800kb

input:

0
10
999 1000000
719 816
256 855
722 661
705 575
610 707
632 426
296 99
891 512
445 475
76 601
63 756
576 934
73 186
606 363
702 69
48 768
568 128
904 82
223 805
146 382
922 467
347 433
959 614
709 998
296 4
544 64
165 989
856 470
370 230
239 810
911 976
728 952
162 752
682 305
511 782
113 37
576 41...

output:

999
198
11
827
921
744
424
539
395
947
192
613
178
46
545
118
404
515
447
196
919
808
454
934
967
724
806
740
887
572
714
19
239
96
942
708
659
47
483
705
861
990
707
252
364
555
373
669
43
411
42
374
949
214
972
910
765
14
86
433
696
245
429
989
153
734
211
236
38
131
301
100
796
260
49
65
869
114
...

input:

1
50048
781 369 2
780
782
401 256 2
400
402
812 856 2
811
813
341 761 2
340
342
674 69 2
673
675
474 781 2
473
475
967 747 2
966
968
65 275 2
64
66
193 971 2
192
194
41 463 2
40
42
728 383 2
727
729
770 922 2
769
771
9 445 2
8
10
882 496 2
881
883
242 214 2
241
243
898 80 2
897
899
269 748 2
268
270...

output:

780
400
813
342
673
475
966
66
194
42
727
771
10
881
241
897
270
933
339
686
649
230
614
682
862
670
507
506
459
487
841
805
701
654
966
414
135
742
555
663
940
651
837
190
767
421
356
437
503
529
963
521
101
64
766
219
827
827
653
856
549
132
207
641
380
92
175
127
37
57
899
35
541
811
129
929
350
...

result:

ok 

Test #19:

score: 16
Accepted
time: 48ms
memory: 3800kb

input:

0
10
2 1000000
0 1
2 1000000
0 1
2 1000000
1 0
2 1000000
0 1
2 1000000
1 0
2 1000000
0 1
2 1000000
1 0
2 1000000
1 0
2 1000000
1 0
2 1000000
1 0

output:

2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1

input:

1
100000
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
0 1 1
1
1 0...

output:

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

result:

ok 

Test #20:

score: 16
Accepted
time: 40ms
memory: 3816kb

input:

0
10
3 1000000
1 0
0 2
3 1000000
2 0
0 1
3 1000000
2 1
2 0
3 1000000
2 0
2 1
3 1000000
0 1
1 2
3 1000000
1 0
1 2
3 1000000
2 0
2 1
3 1000000
0 1
2 1
3 1000000
2 1
0 1
3 1000000
0 2
2 1

output:

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

input:

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

output:

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

result:

ok 

Test #21:

score: 16
Accepted
time: 36ms
memory: 3896kb

input:

0
10
4 1000000
0 1
2 3
0 2
4 1000000
2 1
3 1
0 2
4 1000000
3 1
3 0
1 2
4 1000000
1 3
2 1
0 2
4 1000000
1 2
1 3
0 3
4 1000000
1 0
1 2
0 3
4 1000000
3 0
0 2
2 1
4 1000000
0 1
2 0
1 3
4 1000000
2 0
0 1
2 3
4 1000000
2 1
3 0
3 1

output:

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

input:

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

output:

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

result:

ok 

Test #22:

score: 16
Accepted
time: 32ms
memory: 3824kb

input:

0
10
1000 1000000
526 757
286 227
877 883
484 370
847 13
425 107
166 745
276 357
746 21
304 131
462 834
317 58
942 423
375 631
977 908
229 838
549 167
518 60
51 772
419 970
909 386
362 829
470 46
218 986
82 787
919 307
947 691
348 900
233 650
253 762
90 850
144 627
954 103
602 268
187 746
568 992
31...

output:

1000
723
367
376
612
13
448
37
774
639
927
607
199
503
508
965
888
610
330
437
820
682
476
353
622
54
81
903
908
806
942
823
874
993
633
752
596
924
587
468
285
572
12
695
339
259
655
910
322
355
151
677
662
52
913
969
738
160
276
452
606
945
628
961
977
516
321
524
766
620
581
862
563
171
556
498
8...

input:

1
50050
783 981 2
782
784
768 770 2
767
769
823 290 2
822
824
909 225 2
908
910
997 293 2
996
998
637 574 2
636
638
836 303 2
835
837
312 47 2
311
313
382 537 2
381
383
264 995 2
263
265
693 620 2
692
694
150 552 2
149
151
264 711 2
263
265
171 61 2
170
172
398 248 2
397
399
543 428 2
542
544
673 13...

output:

784
769
822
908
996
636
835
311
383
265
692
151
265
170
397
542
672
313
740
882
455
299
153
267
566
592
603
237
502
663
924
74
963
63
617
310
678
605
890
741
585
345
52
721
582
188
249
577
798
872
142
34
596
505
463
490
751
581
412
458
269
147
605
332
155
853
994
171
262
745
2
595
985
356
877
430
22...

result:

ok 

Test #23:

score: 16
Accepted
time: 32ms
memory: 4052kb

input:

0
1
1000 1000000
622 589
830 829
709 500
278 363
20 230
963 181
768 29
857 332
787 757
897 285
480 939
855 617
959 84
687 755
667 30
553 1
213 98
987 780
47 851
107 764
130 863
326 832
872 636
85 159
119 330
672 210
134 576
224 282
570 387
53 941
723 69
694 642
707 49
260 390
525 768
78 273
811 220
...

output:

1000
765
43
629
903
831
435
74
175
769
876
240
776
194
124
67
3
955
343
488
854
857
203
750
99
210
466
612
673
828
277
687
365
941
772
158
117
287
20
740
949
953
804
141
666
294
325
877
951
654
610
273
82
616
635
350
644
316
317
476
948
370
392
312
710
834
851
921
742
739
532
66
497
637
598
607
101
...

input:

1
50053
554 653 2
553
555
380 187 2
379
381
817 968 2
816
818
122 477 2
121
123
431 332 2
430
432
103 215 2
102
104
960 167 2
959
961
509 476 2
508
510
306 611 2
305
307
589 424 2
588
590
980 964 2
979
981
205 252 2
204
206
159 791 2
158
160
810 218 2
809
811
241 217 2
240
242
874 79 2
873
875
772 8...

output:

555
379
818
123
430
104
959
508
307
588
979
206
160
809
240
873
773
83
79
560
606
353
248
383
387
481
899
330
914
707
739
200
41
299
114
596
253
516
241
952
290
824
155
14
392
305
803
552
763
621
318
491
460
317
649
70
786
393
333
133
686
560
973
884
725
807
418
343
147
976
754
565
165
220
268
224
2...

result:

ok 

Test #24:

score: 16
Accepted
time: 0ms
memory: 3820kb

input:

0
10
4 1000000
0 1
1 2
2 3
4 1000000
0 1
1 3
3 2
4 1000000
0 2
2 1
1 3
4 1000000
0 2
2 3
3 1
4 1000000
0 3
3 1
1 2
4 1000000
0 3
3 2
2 1
4 1000000
1 0
0 2
2 3
4 1000000
1 0
0 3
3 2
4 1000000
1 2
2 0
0 3
4 1000000
1 3
3 0
0 2

output:

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

input:

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

output:

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

result:

ok 

Test #25:

score: 16
Accepted
time: 2ms
memory: 3884kb

input:

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

output:

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

input:

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

output:

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

result:

ok 

Test #26:

score: 16
Accepted
time: 0ms
memory: 4092kb

input:

0
3
3 1000000
0 1
1 2
3 1000000
0 2
2 1
3 1000000
1 0
0 2

output:

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

input:

1
18
0 2 1
1
0 1 1
1
1 2 2
0
2
0 2 1
1
2 0 1
1
1 2 2
0
2
2 0 1
1
2 0 1
1
0 1 1
1
1 0 2
0
2
0 1 1
1
1 0 2
0
2
0 2 1
1
2 1 1
1
2 1 1
1
1 0 2
0
2
2 1 1
1
1 2 2
0
2

output:

1
1
2
1
1
2
1
1
1
0
1
0
1
1
1
0
1
2

result:

ok 

Test #27:

score: 0
Wrong Answer
time: 36ms
memory: 3800kb

input:

0
10
4 1000000
2 1
1 0
3 2
4 1000000
1 2
0 1
1 3
4 1000000
1 0
2 0
0 3
4 1000000
1 3
1 0
2 0
4 1000000
3 2
0 3
3 1
4 1000000
0 1
1 3
2 1
4 1000000
0 1
0 3
3 2
4 1000000
0 3
1 2
0 2
4 1000000
0 2
3 2
2 1
4 1000000
2 0
2 3
0 1

output:

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

input:

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

output:

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

result:

wrong answer Diff at 15-th number: read 2 but expected 3

Subtask #4:

score: 0
Wrong Answer

Test #34:

score: 10
Accepted
time: 48ms
memory: 3820kb

input:

0
10
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1

output:

2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1

input:

1
100000
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
1 0...

output:

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

result:

ok 

Test #35:

score: 10
Accepted
time: 40ms
memory: 4088kb

input:

0
10
3 1000000000
2 1
2 0
3 1000000000
1 0
2 0
3 1000000000
2 0
0 1
3 1000000000
0 2
1 2
3 1000000000
1 2
1 0
3 1000000000
1 0
2 1
3 1000000000
0 2
1 2
3 1000000000
1 2
1 0
3 1000000000
0 2
1 0
3 1000000000
2 0
1 2

output:

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

input:

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

output:

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

result:

ok 

Test #36:

score: 10
Accepted
time: 36ms
memory: 3820kb

input:

0
10
4 1000000000
3 1
2 0
1 0
4 1000000000
0 3
1 2
3 1
4 1000000000
3 1
0 2
0 1
4 1000000000
2 1
2 3
1 0
4 1000000000
3 1
0 1
2 3
4 1000000000
0 1
3 0
2 3
4 1000000000
2 0
3 0
1 2
4 1000000000
0 2
2 3
1 3
4 1000000000
3 2
2 1
3 0
4 1000000000
2 3
3 0
0 1

output:

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

input:

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

output:

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

result:

ok 

Test #37:

score: 10
Accepted
time: 0ms
memory: 3896kb

input:

0
10
4 1000000000
0 1
1 2
2 3
4 1000000000
0 1
1 3
3 2
4 1000000000
0 2
2 1
1 3
4 1000000000
0 2
2 3
3 1
4 1000000000
0 3
3 1
1 2
4 1000000000
0 3
3 2
2 1
4 1000000000
1 0
0 2
2 3
4 1000000000
1 0
0 3
3 2
4 1000000000
1 2
2 0
0 3
4 1000000000
1 3
3 0
0 2

output:

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

input:

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

output:

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

result:

ok 

Test #38:

score: 10
Accepted
time: 2ms
memory: 3804kb

input:

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

output:

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

input:

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

output:

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

result:

ok 

Test #39:

score: 10
Accepted
time: 0ms
memory: 4084kb

input:

0
3
3 1000000000
0 1
1 2
3 1000000000
0 2
2 1
3 1000000000
1 0
0 2

output:

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

input:

1
18
1 2 2
0
2
1 0 2
0
2
1 0 2
0
2
2 0 1
1
2 1 1
1
0 1 1
1
2 1 1
1
2 0 1
1
1 2 2
0
2
1 0 2
0
2
0 2 1
1
0 2 1
1
0 2 1
1
0 1 1
1
2 1 1
1
2 0 1
1
0 1 1
1
1 2 2
0
2

output:

2
0
0
1
1
1
1
1
2
0
1
1
1
1
1
1
1
2

result:

ok 

Test #40:

score: 0
Wrong Answer
time: 38ms
memory: 3892kb

input:

0
10
4 1000000000
1 3
1 2
0 1
4 1000000000
2 3
3 0
1 3
4 1000000000
2 0
1 3
0 1
4 1000000000
1 2
3 1
1 0
4 1000000000
3 1
0 2
3 2
4 1000000000
2 0
2 1
2 3
4 1000000000
1 2
1 3
2 0
4 1000000000
0 2
2 3
2 1
4 1000000000
2 1
2 0
3 0
4 1000000000
3 0
3 2
1 0

output:

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

input:

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

output:

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

result:

wrong answer Diff at 78-th number: read 2 but expected 3

Subtask #5:

score: 0
Wrong Answer

Test #54:

score: 61
Accepted
time: 28ms
memory: 3804kb

input:

0
10
3 1000000000
1 0
2 1
998 1000000000
928 443
90 795
55 379
957 417
759 300
960 136
309 858
833 370
228 827
876 955
619 365
15 108
243 388
54 925
141 894
272 634
0 989
600 346
380 277
350 113
326 613
975 946
660 98
34 538
220 864
9 585
185 860
458 424
509 14
22 275
109 872
153 233
76 834
972 736
...

output:

3
0
1
2
998
203
335
316
714
920
63
630
933
216
527
21
685
236
715
631
880
29
75
921
151
385
114
748
560
574
141
18
948
364
634
258
946
620
816
537
257
439
719
796
282
191
499
961
860
542
555
939
783
255
112
277
127
427
149
207
295
773
534
154
194
376
655
453
693
349
129
626
809
559
810
187
176
956
8...

input:

1
59797
2 3 2
1
3
227 133 2
226
228
1 0 1
0
84 51 2
83
85
273 920 2
272
274
1 0 2
0
2
1 3 2
0
2
321 617 2
320
322
944 542 2
943
945
421 271 2
420
422
0 1 1
1
256 248 2
255
257
362 365 2
361
363
250 444 2
249
251
1 0 2
0
2
667 65 2
666
668
515 917 2
514
516
25 39 2
24
26
8 9 2
7
9
175 645 2
174
176
9...

output:

3
226
0
83
274
0
2
322
943
420
1
255
363
251
0
666
516
26
9
176
941
0
1
561
14
905
832
948
652
1
0
214
766
1
742
31
109
987
68
0
1
1
741
721
0
112
695
133
543
8
1
956
220
0
5
755
314
1
980
1
2
473
4
3
600
379
1
107
255
9
3
675
198
354
175
848
2
922
979
608
1
71
1
1
7
626
454
407
1
1
114
1
8
560
2
1
...

result:

ok 

Test #55:

score: 61
Accepted
time: 32ms
memory: 4084kb

input:

0
10
997 1000000000
210 799
337 790
66 160
541 810
854 650
948 726
189 923
593 566
649 647
907 215
598 271
78 173
820 920
364 470
435 553
634 846
276 104
203 761
874 954
20 983
946 834
365 933
37 641
811 497
970 551
42 389
59 52
747 45
35 291
534 616
284 677
215 83
741 600
549 680
58 500
495 489
664...

output:

997
265
19
20
327
857
406
918
323
207
354
972
153
23
824
562
596
259
400
756
876
688
204
79
683
655
813
906
332
926
358
527
605
856
339
567
754
953
872
366
159
878
388
479
716
137
160
931
443
859
487
411
113
467
456
976
12
671
881
648
468
156
728
297
353
829
448
107
284
713
831
882
864
198
682
271
3...

input:

1
50045
648 197 2
647
649
120 84 2
119
121
429 70 2
428
430
535 259 2
534
536
776 348 2
775
777
375 158 2
374
376
279 72 2
278
280
423 507 2
422
424
752 266 2
751
753
651 126 2
650
652
297 217 2
296
298
410 404 2
409
411
835 297 2
834
836
266 99 2
265
267
757 846 2
756
758
221 961 2
220
222
123 675 ...

output:

647
119
428
534
775
374
278
424
751
650
296
409
834
265
758
222
124
376
551
965
193
721
796
7
847
38
202
514
468
414
64
721
13
919
496
145
964
495
876
800
505
265
241
750
802
169
811
262
431
226
669
632
297
912
190
739
380
617
671
675
919
586
878
665
710
590
838
189
102
272
962
937
83
716
424
594
25...

result:

ok 

Test #56:

score: 61
Accepted
time: 48ms
memory: 4100kb

input:

0
10
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
1 0

output:

2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1

input:

1
100000
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
0 1 1
1
1 0 1
0
0 1...

output:

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

result:

ok 

Test #57:

score: 61
Accepted
time: 40ms
memory: 4088kb

input:

0
10
3 1000000000
0 2
1 0
3 1000000000
1 0
2 1
3 1000000000
2 1
0 1
3 1000000000
2 0
0 1
3 1000000000
0 1
2 1
3 1000000000
1 2
0 2
3 1000000000
0 2
2 1
3 1000000000
1 0
2 1
3 1000000000
0 2
0 1
3 1000000000
2 0
1 0

output:

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

input:

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

output:

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

result:

ok 

Test #58:

score: 61
Accepted
time: 36ms
memory: 3828kb

input:

0
10
4 1000000000
1 2
0 2
1 3
4 1000000000
3 0
1 2
0 1
4 1000000000
2 3
3 0
0 1
4 1000000000
2 3
1 2
0 3
4 1000000000
1 3
0 3
2 0
4 1000000000
3 0
3 2
1 0
4 1000000000
3 1
0 1
2 3
4 1000000000
1 0
3 0
1 2
4 1000000000
3 1
2 3
1 0
4 1000000000
0 1
3 0
1 2

output:

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

input:

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

output:

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

result:

ok 

Test #59:

score: 61
Accepted
time: 32ms
memory: 3752kb

input:

0
10
1000 1000000000
313 401
316 54
721 11
679 942
681 467
84 472
977 306
285 19
891 45
654 702
294 627
927 124
583 515
700 300
401 460
521 643
911 738
818 7
895 746
370 781
405 64
904 359
22 187
609 408
363 713
768 965
345 943
512 10
149 608
438 998
642 108
680 783
648 653
592 351
79 477
759 16
430...

output:

1000
503
719
115
683
553
509
889
55
381
117
954
634
447
39
358
813
505
682
959
92
678
24
994
232
533
209
231
896
626
838
125
399
921
932
271
603
137
513
32
707
546
296
280
496
560
347
410
475
759
844
848
372
741
329
120
957
167
783
9
964
773
946
653
500
243
670
738
57
651
593
108
154
86
149
233
0
80...

input:

1
50038
618 631 2
617
619
678 709 2
677
679
870 437 2
869
871
918 799 2
917
919
619 977 2
618
620
234 167 2
233
235
952 690 2
951
953
529 242 2
528
530
391 345 2
390
392
610 443 2
609
611
539 91 2
538
540
611 219 2
610
612
967 704 2
966
968
313 899 2
312
314
224 798 2
223
225
652 932 2
651
653
682 7...

output:

619
679
869
917
620
233
951
528
390
609
538
610
966
314
225
653
683
927
828
685
668
517
23
199
342
848
160
622
46
919
271
715
868
313
27
409
189
190
283
659
566
51
940
812
369
511
833
655
710
620
305
781
585
76
95
920
972
242
766
899
86
277
897
676
125
419
234
870
892
676
596
172
950
431
753
701
169...

result:

ok 

Test #60:

score: 61
Accepted
time: 32ms
memory: 3796kb

input:

0
1
1000 1000000000
165 608
217 371
579 924
67 365
865 568
258 7
999 657
669 881
268 354
140 308
76 139
428 750
616 661
178 737
179 1
705 411
437 759
119 472
353 50
549 581
327 276
319 864
662 404
619 776
651 890
153 938
580 396
501 193
560 607
786 871
291 760
898 722
511 542
743 74
742 918
431 774
...

output:

1000
442
495
601
500
18
818
840
459
118
419
12
695
685
792
642
401
250
350
509
859
651
141
692
547
894
603
223
812
164
772
756
452
28
732
935
76
708
758
704
98
317
969
892
169
573
457
253
889
499
691
300
1
347
212
570
825
456
650
263
430
769
313
241
188
737
593
215
904
520
256
356
587
850
869
962
80...

input:

1
50048
457 512 2
456
458
219 949 2
218
220
777 403 2
776
778
839 467 2
838
840
434 918 2
433
435
865 927 2
864
866
260 501 2
259
261
482 147 2
481
483
446 985 2
445
447
332 158 2
331
333
627 7 2
626
628
841 360 2
840
842
290 689 2
289
291
643 34 2
642
644
969 914 2
968
970
810 684 2
809
811
604 733...

output:

458
220
776
838
435
866
261
481
447
331
626
840
291
642
968
809
605
838
313
119
886
670
73
314
444
934
518
855
22
955
882
311
289
557
140
990
665
633
44
237
43
383
138
180
783
973
96
274
268
263
813
567
638
79
775
358
950
694
185
492
670
200
612
550
238
256
415
702
200
142
591
934
775
478
930
326
19...

result:

ok 

Test #61:

score: 61
Accepted
time: 0ms
memory: 4036kb

input:

0
10
4 1000000000
0 1
1 2
2 3
4 1000000000
0 1
1 3
3 2
4 1000000000
0 2
2 1
1 3
4 1000000000
0 2
2 3
3 1
4 1000000000
0 3
3 1
1 2
4 1000000000
0 3
3 2
2 1
4 1000000000
1 0
0 2
2 3
4 1000000000
1 0
0 3
3 2
4 1000000000
1 2
2 0
0 3
4 1000000000
1 3
3 0
0 2

output:

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

input:

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

output:

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

result:

ok 

Test #62:

score: 61
Accepted
time: 0ms
memory: 4056kb

input:

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

output:

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

input:

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

output:

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

result:

ok 

Test #63:

score: 61
Accepted
time: 0ms
memory: 4084kb

input:

0
3
3 1000000000
0 1
1 2
3 1000000000
0 2
2 1
3 1000000000
1 0
0 2

output:

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

input:

1
18
1 0 2
0
2
0 1 1
1
1 2 2
0
2
0 1 1
1
2 0 1
1
0 1 1
1
1 0 2
0
2
1 0 2
0
2
2 1 1
1
2 1 1
1
1 2 2
0
2
0 2 1
1
0 2 1
1
0 2 1
1
2 1 1
1
1 2 2
0
2
2 0 1
1
2 0 1
1

output:

0
1
2
1
1
1
0
0
1
1
2
1
1
1
1
2
1
1

result:

ok 

Test #64:

score: 0
Wrong Answer
time: 26ms
memory: 3756kb

input:

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

output:

997
8
9
7
10
265
520
6
11
138
266
393
521
648
775
5
12
75
139
202
267
330
394
457
522
585
649
712
776
839
902
4
13
44
76
107
140
171
203
234
268
299
331
362
395
426
458
489
523
554
586
617
650
681
713
744
777
808
840
871
903
934
3
965
14
29
45
60
77
92
108
123
141
156
172
187
204
219
235
250
269
284...

input:

1
49888
714 402 3
713
715
722
191 383 1
189
781 215 1
780
758 404 1
757
483 700 3
482
484
485
458 806 3
457
459
474
232 827 1
231
2 571 3
1
3
987
954 294 1
952
551 940 3
547
552
553
502 154 3
498
503
504
592 96 3
588
593
594
900 406 1
899
839 344 3
775
840
871
655 249 1
653
870 36 1
868
494 559 1
49...

output:

713
189
780
757
484
459
231
3
952
552
498
588
899
775
653
868
492
15
462
31
514
397
970
947
324
757
712
919
579
902
173
1
282
46
962
245
461
895
522
248
471
793
195
691
188
524
778
79
188
181
678
589
255
884
379
301
440
579
692
602
582
182
426
4
375
656
862
350
786
821
30
712
424
592
805
221
118
332...

result:

wrong answer Diff at 5-th number: read 484 but expected 482