QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113960#1139. Stationswlxhkk100 ✓68ms3804kbC++141.3kb2023-06-20 11:18:242023-06-20 11:18:26

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

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
0
6
1
5
2
7
8
4
3
9
3
2
0
1
998
0
777
971
894
145
299
706
704
822
831
724
624
848
495
195
855
665
26
231
629
457
599
108
545
92
534
250
372
300
51
992
469
488
538
379
719
118
942
314
435
761
885
735
900
48
407
11
941
702
130
595
958
434
177
183
437
886
820
756
125
789
330
949
767
809
868
850
970
...

input:

1
59784
0 1 1
1
156 200 2
424
425
0 1 1
1
848 310 2
151
152
1 2 1
2
1 0 1
0
0 1 1
1
324 733 2
256
257
2 3 2
0
1
3 0 1
0
474 416 2
525
526
8 1 2
0
1
803 470 2
775
776
934 400 2
65
66
264 947 2
883
884
285 437 2
714
715
0 1 1
1
30 47 2
22
23
0 1 2
1
2
0 1 1
1
429 842 2
350
351
1 0 1
0
962 137 2
428
42...

output:

1
424
1
152
2
0
1
256
0
0
526
1
775
66
884
714
1
22
1
1
350
0
428
1
0
692
2
0
2
130
75
861
2
8
6
0
985
72
7
0
8
828
420
1
81
549
104
521
919
19
0
956
150
2
0
0
2
196
0
1
2
0
270
802
467
93
822
3
0
931
549
16
865
0
780
727
0
2
5
1
2
529
0
912
0
88
81
152
8
8
8
0
98
1
2
829
779
526
0
616
394
312
0
193...

result:

ok

Test #2:

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

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
0
569
420
272
546
773
647
227
759
52
399
118
626
765
347
130
488
879
240
123
936
153
1
156
571
545
388
930
758
779
990
322
729
829
861
695
737
720
815
261
979
507
788
997
619
271
321
652
534
303
473
912
859
570
242
289
133
674
483
165
602
864
931
337
890
893
531
601
273
346
523
377
519
275
525
4...

input:

1
50048
691 60 2
364
365
640 356 2
516
517
606 280 2
848
849
478 659 2
577
578
53 627 2
402
403
234 703 2
399
400
348 672 2
285
286
607 53 2
847
848
594 382 2
397
398
412 925 2
221
222
917 90 2
796
797
701 684 2
753
754
114 15 2
877
878
803 36 2
353
354
957 13 2
199
200
62 914 2
104
105
950 18 2
105...

output:

364
516
849
578
403
400
285
848
397
221
796
754
878
353
199
105
105
572
335
870
49
813
401
115
943
215
578
502
833
136
213
876
779
369
829
724
509
105
201
220
59
926
932
885
775
789
337
112
407
540
979
865
207
6
19
58
571
168
283
527
221
128
429
816
350
116
796
126
908
898
188
767
529
287
482
65
63
...

result:

ok

Test #3:

score: 5
Accepted
time: 68ms
memory: 3704kb

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
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0

input:

1
100000
0 1 1
1
1 0 1
0
0 1 1
1
1 0 1
0
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
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
0 1 1
1
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
1 0 1
0
1 0 1
0
1 0 1
0
0 1...

output:

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

result:

ok

Test #4:

score: 5
Accepted
time: 56ms
memory: 3772kb

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
2
1
3
2
0
1
3
0
2
1
3
2
1
0
3
0
1
2
3
2
0
1
3
0
2
1
3
2
0
1
3
0
2
1
3
2
0
1

input:

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

output:

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

result:

ok

Test #5:

score: 5
Accepted
time: 52ms
memory: 3768kb

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
0
1
3
2
4
3
2
1
0
4
0
1
3
2
4
3
1
2
0
4
0
3
1
2
4
3
1
0
2
4
0
3
2
1
4
3
0
1
2
4
0
3
2
1
4
3
0
2
1

input:

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

output:

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

result:

ok

Test #6:

score: 5
Accepted
time: 34ms
memory: 3684kb

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
0
479
917
860
37
418
923
695
881
327
604
387
975
772
29
727
375
673
279
8
416
93
102
362
10
672
372
809
773
302
610
280
491
193
912
647
544
715
669
489
690
77
910
61
621
504
254
380
4
718
303
468
457
127
602
931
287
637
605
421
536
873
644
566
653
315
64
436
537
401
936
191
968
192
675
933
207
...

input:

1
50055
703 872 2
578
579
471 417 2
414
415
712 401 2
434
435
658 423 2
616
617
623 58 2
261
262
14 203 2
569
570
725 690 2
598
599
229 609 2
259
260
242 400 2
246
247
638 427 2
685
686
373 801 2
773
774
354 447 2
134
135
581 602 2
742
743
908 851 2
273
274
344 997 2
930
931
994 3 2
493
494
872 363 ...

output:

578
415
434
616
261
569
599
260
247
686
774
134
742
274
931
493
310
309
818
126
71
514
606
753
516
291
594
497
153
791
256
305
661
728
4
284
536
839
212
310
852
608
248
46
718
168
951
989
776
378
572
921
395
746
731
941
360
992
673
8
253
573
414
101
742
214
102
735
531
228
649
70
690
925
182
160
109...

result:

ok

Test #7:

score: 5
Accepted
time: 28ms
memory: 3676kb

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
0
569
423
285
325
235
890
458
11
914
307
551
399
763
302
65
353
634
152
301
111
595
55
755
27
451
149
103
140
826
876
252
952
579
968
287
487
191
745
79
844
548
753
508
133
554
881
621
995
311
631
286
495
861
38
922
78
723
729
345
352
533
427
369
607
900
538
754
658
318
326
503
691
686
342
904
...

input:

1
50046
484 655 2
264
265
808 133 2
939
940
399 624 2
349
350
806 783 2
941
942
988 587 2
759
760
682 1 2
66
67
72 245 2
676
677
813 378 2
934
935
60 772 2
688
689
783 830 2
964
965
870 429 2
877
878
910 895 2
837
838
749 892 2
998
999
623 630 2
125
126
357 89 2
391
392
902 990 2
845
846
363 802 2
3...

output:

264
940
349
942
759
66
676
935
689
964
878
838
998
125
392
845
386
838
525
62
959
699
348
188
426
645
419
856
158
608
387
179
182
38
860
492
703
437
765
38
125
540
45
394
42
212
208
481
637
492
826
134
288
907
747
159
7
416
974
316
87
591
133
821
836
532
381
525
153
126
791
355
219
309
987
540
705
3...

result:

ok

Test #8:

score: 5
Accepted
time: 2ms
memory: 3700kb

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
3
1
2
4
3
0
1
2
4
0
1
3
2
4
3
1
0
2
4
0
1
2
3
4
3
1
2
0
4
0
3
2
1
4
3
2
1
0
4
0
2
3
1
4
3
2
0
1

input:

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

output:

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

result:

ok

Test #9:

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

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
5
1
4
2
3
6
5
0
4
1
2
3
6
0
5
1
2
4
3
6
5
0
4
2
1
3
6
0
5
1
2
3
4
6
5
0
4
2
3
1
6
0
5
4
1
2
3
6
5
0
1
4
2
3
6
0
5
2
1
4
3
6
5
0
2
4
1
3

input:

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

output:

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

result:

ok

Test #10:

score: 5
Accepted
time: 2ms
memory: 3680kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Subtask #2:

score: 8
Accepted

Test #11:

score: 8
Accepted
time: 46ms
memory: 3680kb

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
0
995
484
740
485
229
1
994
867
739
612
483
356
228
101
931
868
804
741
676
613
549
486
420
357
293
230
165
102
38
2
993
962
930
899
866
835
803
772
738
707
675
644
611
580
548
517
482
451
419
388
355
324
292
261
227
196
164
133
100
69
37
17
978
963
947
932
915
900
884
869
851
836
820
805
788
77...

input:

1
50252
269 617 1
271
146 853 1
144
7 470 1
6
587 611 1
588
138 779 1
137
578 75 1
579
288 282 1
287
559 215 1
561
279 238 3
273
277
278
134 520 3
120
128
131
7 984 1
6
399 855 3
400
401
405
216 482 1
218
596 77 1
598
705 0 1
703
920 844 1
921
128 61 3
129
130
131
680 689 3
695
710
742
632 344 1
633...

output:

271
144
6
588
137
579
287
561
273
120
6
405
218
598
703
921
131
695
633
33
58
135
283
831
618
84
790
241
307
102
96
111
219
636
707
486
383
230
693
534
150
588
3
93
579
956
833
294
150
865
823
625
76
942
160
17
656
55
369
768
311
88
812
553
127
349
486
897
725
786
241
296
388
902
103
102
167
439
980...

result:

ok

Test #12:

score: 8
Accepted
time: 44ms
memory: 3680kb

input:

0
10
31 1000
0 1
0 2
3 1
4 1
2 5
6 2
7 3
3 8
4 9
4 10
11 5
5 12
13 6
6 14
15 7
16 7
17 8
18 8
9 19
20 9
10 21
22 10
11 23
11 24
12 25
26 12
13 27
28 13
14 29
14 30
128 1000
0 1
2 0
3 1
4 1
5 2
6 2
3 7
8 3
9 4
10 4
11 5
12 5
6 13
6 14
7 15
16 7
17 8
18 8
19 9
20 9
10 21
22 10
11 23
11 24
12 25
26 12
...

output:

31
0
30
15
23
16
8
1
29
26
22
19
14
11
7
4
28
27
25
24
21
20
18
17
13
12
10
9
6
5
3
2
128
127
63
0
126
94
62
31
110
95
79
64
47
32
16
1
125
117
109
102
93
86
78
71
61
54
46
39
30
23
15
8
121
118
114
111
106
103
99
96
90
87
83
80
75
72
68
65
58
55
51
48
43
40
36
33
27
24
20
17
12
9
5
2
124
122
120
11...

input:

1
59568
22 1 3
16
20
21
562 725 3
563
564
568
479 175 3
482
485
493
168 113 3
171
174
175
43 56 3
44
45
46
2 0 2
0
1
101 112 1
99
206 65 3
200
204
205
276 186 3
273
274
275
3 1 2
0
1
292 252 3
289
290
291
0 1 1
3
120 144 1
122
0 2 1
3
0 1 1
1
30 78 3
16
24
27
104 75 1
103
11 117 1
9
815 246 1
813
35...

output:

16
568
493
175
46
0
99
200
273
1
289
3
122
3
1
16
103
9
813
366
0
16
352
199
93
54
99
1
413
8
1
388
0
0
0
2
164
26
72
31
1
0
362
215
0
0
295
784
2
0
169
110
334
2
0
124
0
19
1
257
2
2
514
43
3
151
158
23
61
415
1
1
19
246
1
0
20
79
365
6
3
15
138
47
2
14
502
0
20
160
22
2
441
11
16
0
37
102
40
32
23...

result:

ok

Test #13:

score: 8
Accepted
time: 68ms
memory: 3720kb

input:

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

output:

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

input:

1
100000
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
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
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
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
1 0 1
0
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...

output:

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

result:

ok

Test #14:

score: 8
Accepted
time: 40ms
memory: 3680kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #15:

score: 8
Accepted
time: 52ms
memory: 3676kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #16:

score: 8
Accepted
time: 46ms
memory: 3676kb

input:

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

output:

1000
0
999
488
744
489
233
1
998
871
743
616
487
360
232
105
935
872
808
745
680
617
553
490
424
361
297
234
169
106
42
2
997
966
934
903
870
839
807
776
742
711
679
648
615
584
552
521
486
455
423
392
359
328
296
265
231
200
168
137
104
73
41
17
982
967
951
936
919
904
888
873
855
840
824
809
792
7...

input:

1
50108
711 905 3
680
681
696
998 205 3
744
872
935
649 798 3
656
663
679
791 756 3
777
785
788
276 497 1
274
714 319 1
713
485 783 3
471
479
482
94 671 1
93
818 133 1
817
9 379 3
3
7
8
716 386 3
717
718
719
530 115 3
531
532
536
528 250 1
526
618 967 3
625
632
648
825 158 3
826
827
831
724 116 1
72...

output:

680
744
679
777
274
713
471
93
817
3
719
536
526
648
831
723
289
352
618
490
838
608
589
376
791
57
281
377
905
193
111
489
873
841
236
904
78
776
254
370
927
919
235
918
713
369
604
707
96
250
178
788
447
576
178
955
105
10
366
788
781
146
799
400
854
314
361
491
974
663
202
16
313
215
327
681
665
...

result:

ok

Subtask #3:

score: 16
Accepted

Test #17:

score: 16
Accepted
time: 52ms
memory: 3728kb

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
996
258
346
707
168
846
395
278
806
978
462
939
11
681
754
768
36
8
155
91
213
375
905
351
910
53
661
602
686
332
119
985
170
826
435
320
798
883
955
643
43
211
694
250
202
702
536
517
385
918
860
940
847
631
845
629
41
597
437
490
703
712
690
564
139
100
308
73
596
450
995
710
975
565
991...

input:

1
59859
9 7 2
0
5
1 0 1
0
1 0 1
0
15 42 2
983
984
99 150 2
804
805
862 563 2
129
130
0 1 1
1
1 0 2
3
4
938 835 2
60
61
0 1 1
1
0 1 1
1
1 0 1
0
0 1 2
1
2
116 909 2
16
17
185 106 2
813
814
255 251 2
743
744
8 4 2
5
6
1 0 1
0
279 384 2
849
850
8 83 2
76
77
717 704 2
274
275
759 334 2
144
145
77 88 2
55...

output:

5
0
0
983
804
130
1
4
61
1
1
0
1
16
814
744
5
0
849
77
275
145
55
76
1
642
375
460
0
2
433
0
724
0
0
2
311
836
599
1
809
462
51
678
6
0
492
360
463
1
66
0
181
289
52
973
1
9
2
0
0
9
9
22
858
584
12
0
839
1
865
726
26
0
212
2
519
622
1
206
0
529
259
1
1
917
1
764
1
346
62
1
0
0
86
8
0
1
754
1
547
0
8...

result:

ok

Test #18:

score: 16
Accepted
time: 46ms
memory: 3724kb

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
0
105
684
637
471
311
828
900
624
3
791
10
76
825
40
301
840
874
1
638
503
326
566
614
461
502
469
654
385
456
109
978
51
570
453
768
123
856
745
667
594
744
225
281
820
911
763
121
892
78
286
623
206
585
554
715
92
56
881
447
975
883
603
176
466
992
217
80
165
947
49
497
229
124
132
663
42
727
...

input:

1
50048
916 710 2
134
135
824 495 2
422
423
34 56 2
217
218
696 906 2
354
355
436 134 2
760
761
336 707 2
860
861
42 899 2
18
19
558 663 2
492
493
720 138 2
526
527
37 248 2
990
991
463 906 2
733
734
4 850 2
774
775
189 416 2
198
199
570 763 2
457
458
502 516 2
744
745
737 234 2
642
643
758 2 2
488
...

output:

135
423
217
354
761
860
18
492
526
990
734
775
199
457
744
642
488
690
24
786
341
896
32
48
874
492
877
933
868
437
437
40
544
859
111
650
225
815
901
525
964
665
435
289
596
887
277
558
905
281
675
454
392
125
628
499
626
29
666
97
882
33
994
777
149
343
187
403
118
45
975
357
287
618
404
868
369
4...

result:

ok

Test #19:

score: 16
Accepted
time: 66ms
memory: 3744kb

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
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0

input:

1
100000
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
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
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
1 0 1
0
1 0 1
0
1 0 1
0
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
0 1 1
1
0 1 1
1
0 1 1
1
1 0...

output:

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

result:

ok

Test #20:

score: 16
Accepted
time: 58ms
memory: 3688kb

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
0
2
1
3
2
0
1
3
0
1
2
3
2
1
0
3
0
2
1
3
2
0
1
3
0
1
2
3
2
0
1
3
0
2
1
3
2
1
0

input:

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

output:

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

result:

ok

Test #21:

score: 16
Accepted
time: 52ms
memory: 3608kb

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
0
3
2
1
4
3
2
0
1
4
0
1
2
3
4
3
2
0
1
4
0
1
2
3
4
3
1
2
0
4
0
1
2
3
4
3
1
0
2
4
0
1
3
2
4
3
2
1
0

input:

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

output:

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

result:

ok

Test #22:

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

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
0
454
826
944
631
862
619
251
318
102
334
538
386
892
121
194
943
803
419
228
979
876
461
949
665
597
90
184
235
167
50
201
135
321
262
936
176
344
872
495
924
644
290
468
508
310
183
799
460
562
299
969
664
95
123
269
718
776
864
941
111
952
119
127
896
477
900
255
948
347
207
356
552
916
887
...

input:

1
50050
961 862 2
744
745
945 944 2
713
714
50 783 2
226
227
526 868 2
435
436
340 985 2
337
338
698 92 2
60
61
220 486 2
56
57
728 860 2
40
41
188 648 2
570
571
770 136 2
505
506
585 242 2
278
279
506 707 2
355
356
247 735 2
511
512
244 299 2
415
416
529 454 2
130
131
58 544 2
601
602
595 865 2
268...

output:

745
714
227
435
337
61
56
40
571
505
278
355
512
415
131
601
268
824
268
794
753
782
430
513
215
934
336
519
90
600
867
468
871
298
329
136
178
128
798
9
646
157
457
690
722
438
963
821
380
789
955
336
729
606
700
287
14
641
147
867
973
912
678
147
916
926
876
924
707
11
331
677
923
17
914
147
240
4...

result:

ok

Test #23:

score: 16
Accepted
time: 46ms
memory: 3704kb

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
0
361
68
834
798
165
420
295
767
944
503
994
480
445
349
381
860
211
627
955
811
281
758
333
488
616
689
46
968
244
39
200
853
996
462
324
239
393
753
857
859
980
312
716
530
220
821
858
710
688
246
424
691
65
558
705
541
224
621
908
568
579
539
738
965
808
843
754
13
649
416
134
64
682
79
332
...

input:

1
50053
660 56 2
105
106
573 289 2
192
193
791 898 2
973
974
444 144 2
321
322
167 549 2
598
599
331 275 2
434
435
902 299 2
862
863
128 621 2
637
638
536 77 2
229
230
88 595 2
677
678
892 900 2
872
873
280 509 2
485
486
303 778 2
462
463
977 492 2
787
788
262 274 2
503
504
945 343 2
819
820
996 965...

output:

105
193
973
321
598
435
862
637
229
677
872
486
463
787
503
819
769
341
343
663
686
206
507
191
189
142
832
548
925
29
13
483
362
233
440
681
256
641
262
906
528
970
305
390
579
230
784
659
1
72
542
137
613
224
58
418
989
186
216
316
726
663
869
940
20
786
592
211
309
894
760
100
300
493
517
495
488...

result:

ok

Test #24:

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

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
3
1
2
4
3
0
1
2
4
0
1
3
2
4
3
1
0
2
4
0
1
2
3
4
3
1
2
0
4
0
3
2
1
4
3
2
1
0
4
0
2
3
1
4
3
2
0
1

input:

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

output:

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

result:

ok

Test #25:

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

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
5
1
4
2
3
6
5
0
4
1
2
3
6
0
5
1
2
4
3
6
5
0
4
2
1
3
6
0
5
1
2
3
4
6
5
0
4
2
3
1
6
0
5
4
1
2
3
6
5
0
1
4
2
3
6
0
5
2
1
4
3
6
5
0
2
4
1
3

input:

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

output:

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

result:

ok

Test #26:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #27:

score: 16
Accepted
time: 52ms
memory: 3720kb

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
3
1
2
4
3
0
2
1
4
0
3
2
1
4
3
1
0
2
4
0
1
2
3
4
3
0
1
2
4
0
3
1
2
4
3
1
0
2
4
0
1
3
2
4
3
0
1
2

input:

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

output:

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

result:

ok

Test #28:

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

input:

0
10
1000 1000000
802 637
810 172
802 781
109 293
802 724
488 524
73 802
802 312
108 985
802 594
305 802
802 620
382 747
841 535
802 690
987 387
269 559
201 219
982 319
228 802
802 977
291 962
657 597
69 757
321 555
825 299
802 694
363 827
802 265
475 796
600 891
802 16
802 116
487 167
150 335
175 5...

output:

1000
0
752
577
441
93
210
411
696
114
72
976
358
709
558
637
353
943
218
351
894
531
406
839
644
327
534
613
555
914
641
203
684
403
646
742
104
776
729
774
122
881
7
382
457
101
389
523
174
516
930
937
527
328
924
5
502
794
701
739
456
901
12
11
341
80
566
294
244
295
192
1
112
601
953
668
611
423
...

input:

1
51340
396 19 2
850
851
856 963 2
121
122
484 607 2
867
868
687 66 2
721
722
540 740 2
437
438
448 769 2
467
468
346 996 2
363
364
867 92 2
874
875
414 306 1
415
300 320 1
1
317 359 2
929
930
616 402 2
630
631
333 903 2
319
320
324 86 1
29
35 89 2
40
41
348 413 2
344
345
736 261 2
671
672
402 716 1...

output:

851
121
867
722
437
468
364
875
415
1
929
631
319
29
41
344
671
29
1
199
336
224
625
540
254
29
67
696
661
100
78
868
849
779
756
69
486
781
772
162
195
49
998
1
496
9
532
1
70
371
354
998
509
711
402
29
79
378
587
588
145
0
59
804
29
8
597
363
727
843
646
938
576
958
798
8
742
757
460
899
462
29
63...

result:

ok

Test #29:

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

input:

0
10
1000 1000000
1 433
265 863
766 305
237 422
591 33
588 87
33 868
33 328
110 458
718 791
891 33
22 576
773 795
489 357
104 33
33 829
308 726
592 865
651 179
591 508
264 792
274 367
219 33
67 600
419 406
583 183
716 211
4 709
983 33
672 928
648 689
679 497
321 874
711 585
758 518
223 702
440 618
7...

output:

1000
0
400
492
573
717
534
623
288
952
607
142
409
833
284
128
424
222
36
608
162
743
404
130
682
35
416
485
33
339
890
509
200
569
998
233
478
784
302
160
150
561
379
648
133
326
243
125
905
920
631
497
104
822
516
865
330
90
51
703
340
270
177
869
245
756
241
940
464
846
761
930
951
692
615
969
56...

input:

1
51513
288 439 2
520
521
642 997 2
681
682
584 382 1
0
514 255 1
0
279 494 2
273
274
515 848 2
518
519
693 456 2
993
994
775 509 2
694
695
413 910 2
394
395
509 613 1
0
110 693 2
985
986
100 687 2
104
105
431 335 2
7
416
437 115 2
424
425
167 24 2
431
432
158 646 2
990
991
954 825 1
998
555 107 2
2...

output:

520
682
0
0
273
519
994
694
394
0
985
105
7
424
432
990
998
276
369
743
892
185
7
552
190
7
0
88
938
794
978
221
762
339
232
181
499
752
894
0
711
720
9
413
651
0
973
0
325
868
0
0
351
34
0
216
0
406
901
211
570
884
288
86
865
191
647
613
95
678
591
893
725
18
122
495
43
104
476
695
826
910
221
749
...

result:

ok

Test #30:

score: 16
Accepted
time: 30ms
memory: 3684kb

input:

0
1
1000 1000000
394 768
598 218
369 360
414 385
909 666
948 524
272 868
110 348
723 672
225 409
312 213
865 469
207 711
779 480
303 958
946 880
22 137
265 787
595 9
193 865
661 869
680 238
708 770
389 82
828 35
881 49
138 749
220 975
452 201
641 269
734 497
155 159
324 778
105 650
882 621
519 319
4...

output:

1000
0
702
95
813
947
663
149
32
810
696
974
389
982
886
899
660
634
450
822
791
8
462
744
869
826
727
497
72
405
764
985
897
219
728
339
486
336
283
960
385
204
178
908
207
866
78
807
711
584
927
723
905
56
124
518
367
984
862
992
494
31
753
644
632
783
781
799
637
202
717
170
278
607
730
365
529
3...

input:

1
49931
18 266 2
15
16
685 279 2
655
656
999 586 30
0
34
78
112
152
197
226
264
297
327
360
392
433
460
500
536
562
590
624
649
692
728
755
787
824
849
878
898
927
967
728 267 2
754
999
571 79 2
580
581
418 413 2
406
407
293 505 2
267
268
57 527 2
54
55
723 167 2
696
697
155 825 2
193
194
922 147 2
...

output:

15
655
562
999
581
407
267
54
696
194
902
525
974
687
999
951
596
26
150
680
438
867
197
528
250
864
481
515
69
598
999
33
259
283
429
0
219
319
478
778
949
704
8
492
198
362
458
261
540
279
367
209
457
728
617
432
404
610
987
358
864
910
290
560
738
384
178
979
157
801
60
999
501
562
919
649
305
35...

result:

ok

Test #31:

score: 16
Accepted
time: 16ms
memory: 3688kb

input:

0
10
96 1000000
0 36
27 0
95 0
7 0
0 70
59 0
72 0
83 0
22 0
25 0
18 0
92 0
0 88
87 0
0 75
0 68
39 0
0 84
0 43
0 24
28 0
19 0
5 0
0 80
37 0
0 33
77 0
15 0
0 38
3 0
0 60
11 0
74 0
89 0
52 0
79 0
0 73
81 0
44 0
76 0
41 0
21 0
57 0
0 85
40 0
49 0
0 45
0 46
16 0
14 0
0 66
29 0
20 0
32 0
0 1
0 51
0 47
0 3...

output:

96
0
41
10
66
4
73
13
92
20
32
19
64
2
5
46
68
47
24
85
74
43
54
87
22
76
86
25
94
75
44
34
38
42
70
31
36
95
71
67
79
51
55
21
77
57
49
48
39
6
50
37
40
61
9
17
3
30
53
28
90
65
33
14
27
1
23
45
18
80
11
91
15
89
59
63
81
56
69
8
60
72
58
35
88
78
52
7
82
83
62
29
26
84
16
12
93
96
95
55
67
48
33
7...

input:

1
4026
30 2 1
0
79 18 1
0
62 12 1
0
46 52 1
0
25 18 1
95
95 78 95
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
8...

output:

0
0
0
0
95
78
95
0
95
0
0
95
95
0
72
95
95
0
14
95
0
95
95
95
29
95
0
35
0
0
95
0
69
0
0
95
95
95
0
95
0
0
0
95
70
95
0
0
0
95
21
50
77
0
75
0
0
0
0
0
95
95
0
0
95
85
0
0
50
95
87
0
95
95
95
95
0
40
95
0
95
0
0
0
0
1
0
0
0
0
0
0
71
11
0
86
42
56
2
0
95
0
0
0
95
95
78
95
0
0
12
0
0
0
0
20
95
95
34
8
...

result:

ok

Test #32:

score: 16
Accepted
time: 18ms
memory: 3748kb

input:

0
10
541 1000000
540 23
540 21
40 540
150 540
540 291
540 34
3 540
540 416
428 540
347 540
60 540
140 540
540 216
411 540
57 540
540 214
271 540
439 540
400 540
379 540
195 540
540 167
152 540
540 254
251 540
399 540
540 185
420 540
540 154
534 540
540 160
540 194
247 540
540 11
342 540
540 257
454 ...

output:

541
0
482
393
533
283
499
285
490
155
159
286
506
38
213
14
27
99
311
378
267
333
538
314
539
79
154
450
457
6
37
25
418
72
334
534
486
219
195
438
403
537
497
479
290
475
170
282
329
294
325
221
142
426
302
192
187
212
525
71
18
529
492
415
330
384
428
35
214
301
338
16
321
460
413
440
141
193
29
3...

input:

1
5675
305 372 1
540
339 164 1
540
349 73 1
0
334 482 1
0
0 138 540
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
8...

output:

540
540
0
0
138
0
0
0
0
0
0
0
0
0
540
0
0
0
0
0
0
540
0
0
540
0
0
0
0
0
0
0
0
0
0
540
0
0
540
0
0
0
0
0
0
540
0
0
0
540
0
0
0
0
0
0
0
0
0
0
0
0
540
540
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
380
0
0
540
0
0
0
0
0
0
0
0
0
0
0
0
0
540
540
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
540
0
540
0
0
0
0
0
540
0
0
540
0
0
0
0
...

result:

ok

Test #33:

score: 16
Accepted
time: 14ms
memory: 3692kb

input:

0
10
1000 1000000
989 0
0 294
783 0
474 0
831 0
397 0
0 538
626 0
554 0
837 0
954 0
0 694
343 0
883 0
0 957
0 24
0 688
0 17
406 0
472 0
929 0
22 0
0 412
0 195
150 0
0 518
0 255
35 0
381 0
751 0
0 928
0 555
0 241
0 590
454 0
373 0
0 72
389 0
455 0
327 0
0 917
572 0
0 164
335 0
0 59
0 809
0 182
0 123
...

output:

1000
0
509
122
479
94
532
548
560
900
390
577
840
653
657
395
902
156
982
756
789
27
311
978
403
984
299
229
942
129
426
432
680
540
771
946
972
795
570
576
740
428
285
568
860
399
774
250
673
765
366
583
44
149
739
189
608
292
410
792
955
790
786
828
188
538
173
28
503
842
430
764
477
963
930
47
23...

input:

1
10180
928 612 1
0
953 665 1
0
943 660 1
999
877 85 1
0
804 282 1
0
29 232 1
0
263 410 1
0
597 392 1
0
386 744 1
999
895 681 1
0
724 194 1
999
225 810 1
0
972 333 1
0
762 673 1
0
892 827 1
999
924 762 1
999
718 435 1
999
818 289 1
0
808 17 1
999
607 169 1
0
486 393 1
999
880 890 1
0
925 871 1
0
923...

output:

0
0
999
0
0
0
0
0
999
0
999
0
0
0
999
999
999
0
999
0
999
0
0
0
160
0
0
999
0
999
0
999
999
0
0
0
999
999
999
0
999
999
0
0
0
0
999
0
0
0
999
0
999
759
0
0
999
999
999
999
0
0
0
999
0
0
999
0
0
0
0
0
0
999
0
0
0
999
0
999
0
999
0
0
0
0
999
0
0
0
999
0
999
999
0
999
0
0
0
0
0
999
999
0
0
999
0
0
0
0
...

result:

ok

Subtask #4:

score: 10
Accepted

Test #34:

score: 10
Accepted
time: 58ms
memory: 3728kb

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
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0

input:

1
100000
0 1 1
1
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
0 1 1
1
1 0 1
0
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
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
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
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...

output:

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

result:

ok

Test #35:

score: 10
Accepted
time: 56ms
memory: 3692kb

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
1
2
3
2
1
0
3
0
1
2
3
2
1
0
3
0
2
1
3
2
0
1
3
0
1
2
3
2
0
1
3
0
1
2
3
2
1
0

input:

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

output:

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

result:

ok

Test #36:

score: 10
Accepted
time: 52ms
memory: 3728kb

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
0
2
3
1
4
3
2
1
0
4
0
2
3
1
4
3
0
2
1
4
0
3
2
1
4
3
2
1
0
4
0
2
3
1
4
3
1
0
2
4
0
2
1
3
4
3
0
2
1

input:

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

output:

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

result:

ok

Test #37:

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

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
3
1
2
4
3
0
1
2
4
0
1
3
2
4
3
1
0
2
4
0
1
2
3
4
3
1
2
0
4
0
3
2
1
4
3
2
1
0
4
0
2
3
1
4
3
2
0
1

input:

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

output:

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

result:

ok

Test #38:

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

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
5
1
4
2
3
6
5
0
4
1
2
3
6
0
5
1
2
4
3
6
5
0
4
2
1
3
6
0
5
1
2
3
4
6
5
0
4
2
3
1
6
0
5
4
1
2
3
6
5
0
1
4
2
3
6
0
5
2
1
4
3
6
5
0
2
4
1
3

input:

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

output:

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

result:

ok

Test #39:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #40:

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

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
3
1
2
4
3
1
2
0
4
0
2
3
1
4
3
0
2
1
4
0
2
3
1
4
3
2
0
1
4
0
1
3
2
4
3
1
0
2
4
0
2
3
1
4
3
0
2
1

input:

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

output:

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

result:

ok

Test #41:

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

input:

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

output:

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

input:

1
100000
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
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 1
1
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
0 1 1
1
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
0 1 1
1
1 0 1
0
0 1 1
1
0 1 1
1
0 1 1
1
1 0...

output:

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

result:

ok

Test #42:

score: 10
Accepted
time: 50ms
memory: 3696kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #43:

score: 10
Accepted
time: 52ms
memory: 3728kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #44:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #45:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #46:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #47:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #48:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #49:

score: 10
Accepted
time: 46ms
memory: 3664kb

input:

0
10
8 1000000000
5 6
4 7
5 1
7 2
0 3
2 1
6 0
8 1000000000
7 6
4 7
7 2
3 7
7 5
1 3
7 0
8 1000000000
0 1
2 0
1 3
4 1
5 2
6 2
7 3
8 1000000000
4 2
6 0
0 1
4 7
1 4
4 3
4 5
8 1000000000
6 0
6 2
6 5
7 6
6 3
6 4
6 1
8 1000000000
7 2
5 7
7 6
1 7
4 7
7 3
7 0
8 1000000000
6 5
7 3
1 2
2 7
0 1
5 3
4 5
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #50:

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

input:

0
10
8 1000000000
1 3
4 1
0 1
6 1
1 2
1 7
5 1
8 1000000000
4 0
2 0
5 4
3 5
7 2
1 6
0 1
8 1000000000
0 5
6 2
0 6
3 6
4 5
1 4
4 7
8 1000000000
5 1
5 7
3 0
2 3
3 1
7 4
3 6
8 1000000000
2 4
0 1
5 3
1 2
7 0
4 3
5 6
8 1000000000
6 5
1 2
0 3
6 1
2 4
3 4
7 0
8 1000000000
3 6
5 0
4 0
0 6
7 0
1 3
2 0
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #51:

score: 10
Accepted
time: 46ms
memory: 3676kb

input:

0
10
8 1000000000
2 7
4 2
5 3
1 6
0 1
1 4
3 7
8 1000000000
4 2
0 4
4 5
4 1
4 6
4 7
4 3
8 1000000000
0 7
5 3
5 1
2 3
1 4
0 6
6 4
8 1000000000
6 4
5 4
4 0
4 1
2 0
7 4
4 3
8 1000000000
0 6
4 0
1 7
5 7
7 2
6 3
4 2
8 1000000000
3 1
3 6
5 0
4 7
2 4
2 5
1 0
8 1000000000
4 7
6 5
7 5
5 3
0 7
1 5
2 7
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #52:

score: 10
Accepted
time: 46ms
memory: 3684kb

input:

0
10
8 1000000000
2 7
4 2
5 3
1 6
0 1
1 4
3 7
8 1000000000
4 2
0 4
4 5
4 1
4 6
4 7
4 3
8 1000000000
0 7
5 3
5 1
2 3
1 4
0 6
6 4
8 1000000000
6 4
5 4
4 0
4 1
2 0
7 4
4 3
8 1000000000
0 6
4 0
1 7
5 7
7 2
6 3
4 2
8 1000000000
3 1
3 6
5 0
4 7
2 4
2 5
1 0
8 1000000000
4 7
6 5
7 5
5 3
0 7
1 5
2 7
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #53:

score: 10
Accepted
time: 32ms
memory: 3688kb

input:

0
10
8 1000000000
2 7
4 2
5 3
1 6
0 1
1 4
3 7
8 1000000000
4 2
0 4
4 5
4 1
4 6
4 7
4 3
8 1000000000
0 7
5 3
5 1
2 3
1 4
0 6
6 4
8 1000000000
6 4
5 4
4 0
4 1
2 0
7 4
4 3
8 1000000000
0 6
4 0
1 7
5 7
7 2
6 3
4 2
8 1000000000
3 1
3 6
5 0
4 7
2 4
2 5
1 0
8 1000000000
4 7
6 5
7 5
5 3
0 7
1 5
2 7
8 100000...

output:

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

input:

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

output:

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

result:

ok

Subtask #5:

score: 61
Accepted

Test #54:

score: 61
Accepted
time: 50ms
memory: 3664kb

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
2
1
998
997
728
56
255
358
927
213
429
6
632
906
553
16
538
580
338
910
933
435
971
703
838
272
178
185
966
886
372
80
215
27
371
208
306
627
767
676
536
296
39
991
646
415
328
169
618
426
504
768
839
757
959
682
970
792
748
509
165
818
798
86
568
669
549
721
960
211
491
616
303
989
807
376
340
...

input:

1
59797
2 1 2
0
1
733 686 2
505
506
0 1 1
1
51 19 2
35
36
891 216 2
617
618
0 3 2
2
3
0 1 2
2
3
735 587 2
58
59
228 27 2
282
283
636 561 2
214
215
1 0 1
0
491 495 2
747
748
438 802 2
800
801
23 120 2
770
771
2 0 2
0
1
759 458 2
91
92
742 541 2
257
258
6 13 2
80
81
3 4 2
4
5
912 677 2
87
88
471 53 2
...

output:

1
506
1
35
617
3
2
59
283
215
0
747
801
770
0
92
258
80
4
88
529
1
0
474
888
547
172
94
224
0
0
107
42
2
248
9
950
126
59
1
2
0
384
786
1
563
652
686
483
3
0
903
509
0
6
622
462
0
110
0
1
659
1
7
300
944
0
479
882
88
91
763
99
577
912
322
1
461
406
315
2
931
2
0
5
306
392
692
0
0
838
2
3
280
1
0
5
9...

result:

ok

Test #55:

score: 61
Accepted
time: 38ms
memory: 3732kb

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
0
854
874
31
296
661
405
29
760
687
378
787
852
452
583
566
734
664
486
426
520
966
824
209
195
274
411
698
401
685
131
170
436
37
151
487
344
428
681
784
425
670
107
506
795
944
333
89
297
111
73
807
101
636
376
870
203
308
540
630
942
500
16
44
282
640
810
722
224
283
423
432
963
523
3
697
626...

input:

1
50045
430 205 2
772
773
555 573 2
675
676
654 404 2
224
225
152 14 2
608
609
476 690 2
255
256
803 536 2
427
428
755 579 2
475
476
194 152 2
617
618
579 70 2
825
826
864 132 2
520
521
588 548 2
290
291
410 413 2
820
821
302 33 2
458
459
539 356 2
272
273
263 453 2
497
498
314 721 2
92
93
265 864 2...

output:

773
675
225
609
255
428
476
618
826
520
291
820
459
273
497
92
141
251
130
614
536
800
109
199
291
895
514
363
381
613
674
45
857
748
462
791
921
942
633
614
959
0
324
64
596
191
802
537
831
90
774
299
257
562
108
820
686
881
872
222
156
399
437
772
569
569
633
290
457
78
676
238
822
572
2
567
344
8...

result:

ok

Test #56:

score: 61
Accepted
time: 42ms
memory: 3680kb

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
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0
2
0
1
2
1
0

input:

1
100000
1 0 1
0
1 0 1
0
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
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
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
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...

output:

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

result:

ok

Test #57:

score: 61
Accepted
time: 42ms
memory: 3728kb

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
0
1
2
3
2
0
1
3
0
2
1
3
2
0
1
3
0
2
1
3
2
1
0
3
0
1
2
3
2
0
1
3
0
1
2
3
2
0
1

input:

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

output:

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

result:

ok

Test #58:

score: 61
Accepted
time: 42ms
memory: 3684kb

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
1
3
2
4
3
0
1
2
4
0
1
2
3
4
3
1
2
0
4
0
2
1
3
4
3
0
2
1
4
0
3
2
1
4
3
1
2
0
4
0
3
2
1
4
3
1
2
0

input:

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

output:

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

result:

ok

Test #59:

score: 61
Accepted
time: 46ms
memory: 3680kb

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
0
108
690
90
25
3
193
720
557
689
271
431
524
728
927
155
1
407
228
794
409
760
251
864
15
643
632
300
435
329
685
548
209
282
612
50
679
5
764
102
475
896
888
996
468
574
953
510
128
326
324
934
119
583
808
227
664
140
743
266
135
275
75
998
626
413
379
719
74
45
802
825
791
673
631
748
346
46...

input:

1
50038
598 223 2
216
217
213 519 2
534
535
87 741 2
957
958
540 399 2
458
459
832 34 2
212
213
405 606 2
639
640
275 144 2
322
323
218 832 2
688
689
149 126 2
757
758
443 526 2
53
54
18 702 2
478
479
213 17 2
601
602
294 458 2
326
327
156 449 2
842
843
761 273 2
985
986
988 848 2
640
641
181 164 2
...

output:

217
534
957
458
212
639
323
689
758
53
479
602
327
842
986
641
864
417
213
250
476
258
798
648
351
890
919
626
976
414
612
106
880
156
301
204
220
410
95
544
157
824
269
280
138
209
939
850
167
625
951
201
581
941
1
62
513
436
616
449
755
92
350
472
685
538
927
518
245
565
172
913
839
583
497
161
60...

result:

ok

Test #60:

score: 61
Accepted
time: 46ms
memory: 3676kb

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
0
973
920
471
212
630
641
991
162
431
215
873
878
617
542
422
96
46
966
791
895
292
567
947
668
919
333
627
139
607
599
447
207
587
753
183
575
600
573
172
380
736
667
306
934
992
348
776
971
875
71
222
395
115
506
808
449
546
353
6
836
378
342
127
852
924
329
673
481
93
43
927
646
786
702
817
...

input:

1
50048
992 477 2
449
450
331 746 2
111
112
832 423 2
609
610
801 987 2
640
641
4 680 2
438
439
788 757 2
653
654
91 970 2
351
352
462 295 2
979
980
444 728 2
997
998
55 142 2
387
388
907 225 2
534
535
800 41 2
641
642
76 876 2
366
367
899 204 2
542
543
736 678 2
705
706
626 563 2
815
816
523 854 2
...

output:

450
111
609
640
439
654
352
980
997
387
534
641
367
542
705
816
918
640
378
281
664
556
258
64
443
688
480
793
210
743
662
377
366
942
151
716
888
904
199
340
243
413
152
131
829
734
173
84
87
353
814
937
540
261
833
42
696
568
314
467
556
121
527
496
102
93
429
572
121
150
925
688
833
460
686
58
12...

result:

ok

Test #61:

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

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
3
1
2
4
3
0
1
2
4
0
1
3
2
4
3
1
0
2
4
0
1
2
3
4
3
1
2
0
4
0
3
2
1
4
3
2
1
0
4
0
2
3
1
4
3
2
0
1

input:

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

output:

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

result:

ok

Test #62:

score: 61
Accepted
time: 2ms
memory: 3680kb

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
5
1
4
2
3
6
5
0
4
1
2
3
6
0
5
1
2
4
3
6
5
0
4
2
1
3
6
0
5
1
2
3
4
6
5
0
4
2
3
1
6
0
5
4
1
2
3
6
5
0
1
4
2
3
6
0
5
2
1
4
3
6
5
0
2
4
1
3

input:

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

output:

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

result:

ok

Test #63:

score: 61
Accepted
time: 2ms
memory: 3676kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #64:

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

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
0
996
485
741
486
230
1
995
868
740
613
484
357
229
102
932
869
805
742
677
614
550
487
421
358
294
231
166
103
39
2
994
963
931
900
867
836
804
773
739
708
676
645
612
581
549
518
483
452
420
389
356
325
293
262
228
197
165
134
101
70
38
17
979
964
948
933
916
901
885
870
852
837
821
806
789
77...

input:

1
49888
279 608 3
286
293
294
813 621 1
815
226 794 1
224
250 604 1
248
524 309 3
525
526
527
549 201 3
487
519
534
778 181 1
779
25 436 3
30
37
38
53 716 1
55
454 63 3
451
452
453
499 850 3
500
501
505
408 908 3
409
410
414
100 596 1
101
167 666 3
104
105
136
350 757 1
352
132 968 1
131
512 446 1
5...

output:

294
815
224
248
527
487
779
38
55
451
505
414
101
104
352
131
511
989
537
978
488
613
10
54
679
249
292
87
422
36
830
25
731
926
45
756
542
100
478
765
531
193
808
312
823
479
226
928
804
823
328
416
747
123
629
702
573
425
309
390
424
825
552
25
626
353
138
661
212
184
994
295
592
414
196
786
887
6...

result:

ok

Test #65:

score: 61
Accepted
time: 50ms
memory: 3676kb

input:

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

output:

512
0
511
255
383
256
128
1
510
446
382
319
254
191
127
64
478
447
415
384
351
320
288
257
223
192
160
129
96
65
33
2
509
493
477
462
445
430
414
399
381
366
350
335
318
303
287
272
253
238
222
207
190
175
159
144
126
111
95
80
63
48
32
17
501
494
486
479
470
463
455
448
438
431
423
416
407
400
392
...

input:

1
59652
24 8 1
23
267 97 1
268
2 1 1
3
1 0 1
0
37 109 1
36
3 2 2
0
2
1 0 1
0
0 1 1
1
1 0 1
0
17 286 3
24
31
32
214 42 3
208
212
213
126 50 3
63
95
110
1 0 1
0
392 499 3
361
362
377
421 426 1
422
25 5 1
26
1 0 1
0
92 1 1
90
31 39 3
0
1
16
876 529 1
874
412 460 1
410
0 3 2
1
3
1 0 1
0
125 8 3
119
123
...

output:

23
268
3
0
36
2
0
1
0
32
208
63
0
361
422
26
0
90
0
874
410
3
0
119
23
808
14
4
16
0
221
0
0
2
257
0
0
22
862
0
385
65
11
343
104
3
0
448
2
1
3
55
22
0
482
2
0
30
2
0
273
0
0
0
1
0
14
116
103
109
66
0
27
398
335
8
0
9
0
58
3
3
3
19
68
30
0
16
25
355
23
6
1
419
23
0
491
19
0
0
15
16
46
0
0
1
454
0
18...

result:

ok

Test #66:

score: 61
Accepted
time: 68ms
memory: 3680kb

input:

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

output:

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

input:

1
100000
0 1 1
1
0 1 1
1
1 0 1
0
1 0 1
0
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
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
1 0 1
0
1 0 1
0
0 1 1
1
0 1 1
1
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
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
1 0...

output:

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

result:

ok

Test #67:

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

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #68:

score: 61
Accepted
time: 52ms
memory: 3688kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #69:

score: 61
Accepted
time: 18ms
memory: 3684kb

input:

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

output:

1000
0
999
488
744
489
233
1
998
871
743
616
487
360
232
105
935
872
808
745
680
617
553
490
424
361
297
234
169
106
42
2
997
966
934
903
870
839
807
776
742
711
679
648
615
584
552
521
486
455
423
392
359
328
296
265
231
200
168
137
104
73
41
17
982
967
951
936
919
904
888
873
855
840
824
809
792
7...

input:

1
50098
266 573 3
273
280
296
459 165 1
457
248 724 1
246
812 240 1
810
833 263 1
832
27 291 3
28
29
33
434 92 1
433
198 643 1
196
928 736 1
927
935 399 3
966
997
998
428 635 1
426
574 544 1
573
758 492 1
757
487 249 3
233
361
424
152 351 3
138
146
149
867 446 1
866
551 42 3
537
545
548
940 261 3
94...

output:

296
457
246
810
832
33
433
196
927
998
426
573
757
233
138
866
537
943
498
978
757
526
153
892
270
258
6
54
384
447
285
668
233
266
362
965
799
712
565
742
855
358
728
361
105
930
607
246
3
703
133
337
96
185
617
152
9
267
840
884
441
573
361
663
126
856
488
340
384
936
785
373
904
115
569
344
305
1...

result:

ok

Test #70:

score: 61
Accepted
time: 52ms
memory: 3724kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #71:

score: 61
Accepted
time: 46ms
memory: 3668kb

input:

0
10
1000 1000000000
496 136
370 247
359 252
743 278
85 499
522 547
6 780
330 416
815 429
942 361
275 290
113 753
471 15
720 896
514 482
631 513
981 760
525 601
600 637
263 572
292 229
556 489
46 504
199 953
354 801
91 181
742 119
495 647
940 396
272 230
291 130
763 639
467 709
945 171
96 610
726 96...

output:

1000
0
48
559
909
107
67
615
828
675
608
128
948
878
68
459
711
508
619
575
564
990
284
841
431
771
316
23
276
420
926
809
334
590
110
78
45
628
622
355
456
250
254
418
424
212
925
733
911
302
674
146
713
814
286
493
928
913
542
801
113
601
203
895
392
569
215
541
345
417
920
271
172
411
5
138
247
8...

input:

1
50431
251 785 2
420
421
664 536 2
643
644
66 441 1
16
935 321 2
735
736
399 126 1
949
344 360 2
229
230
193 251 2
203
204
574 246 2
998
999
398 830 2
390
391
64 814 2
74
75
618 175 2
975
976
280 122 2
293
294
429 489 2
242
243
88 213 2
506
507
259 980 1
949
409 766 1
949
416 108 2
412
413
305 209 ...

output:

421
643
16
735
949
229
204
999
390
75
976
294
242
506
949
949
412
290
257
654
866
949
732
949
427
702
702
254
610
71
163
596
589
286
369
519
0
640
531
349
377
409
44
932
314
628
299
141
810
625
38
561
319
343
834
366
798
871
404
144
0
684
16
520
416
414
583
476
610
406
539
16
105
224
699
663
534
529...

result:

ok

Test #72:

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

input:

0
10
1000 1000000000
812 935
596 175
369 401
625 709
470 249
715 901
665 497
296 591
732 817
698 374
352 216
787 19
831 844
896 420
700 895
533 363
872 36
58 930
48 897
321 154
391 351
993 950
392 990
585 323
565 739
818 926
103 89
912 432
706 259
359 608
218 33
146 201
16 769
230 885
945 377
41 131...

output:

1000
0
47
828
656
720
594
979
815
476
618
104
898
484
235
581
173
924
32
470
323
60
866
442
63
749
77
116
58
508
557
171
338
310
437
292
612
740
189
917
607
679
718
678
545
637
838
698
31
627
560
246
655
324
829
250
970
691
422
298
674
689
886
685
311
52
968
641
498
899
816
178
573
481
501
91
364
31...

input:

1
51725
182 558 2
113
114
762 988 2
165
166
623 599 2
612
613
188 640 1
187
985 704 1
999
802 936 2
492
493
701 122 2
698
699
514 523 2
641
642
404 708 2
420
421
252 979 2
231
232
988 208 1
999
410 622 2
517
518
706 385 2
588
589
19 511 1
999
336 491 2
591
592
204 86 2
252
253
803 619 2
491
492
6 44...

output:

113
165
612
187
999
492
698
641
421
231
999
518
588
999
591
253
492
5
491
291
447
27
997
999
999
279
655
668
999
523
966
441
236
152
643
652
871
527
399
189
675
579
184
39
881
999
587
154
110
999
5
983
243
713
915
711
2
628
876
794
856
351
501
201
34
483
173
670
0
939
2
2
994
999
465
792
435
517
659...

result:

ok

Test #73:

score: 61
Accepted
time: 46ms
memory: 3684kb

input:

0
1
1000 1000000000
584 325
759 912
536 411
310 503
386 643
125 683
587 211
331 908
866 671
790 38
346 846
813 567
297 574
42 196
443 23
467 767
797 820
134 746
465 907
815 88
161 453
467 788
793 875
656 320
847 290
725 194
372 594
909 185
120 5
845 895
292 421
56 804
634 565
41 22
144 402
616 552
1...

output:

1000
0
840
371
651
648
723
801
677
506
519
727
794
668
645
880
149
84
909
281
899
323
53
348
975
501
475
482
993
639
604
868
765
301
491
721
147
680
605
589
672
253
324
671
582
918
24
6
767
732
616
148
717
13
809
876
627
463
413
27
547
792
330
958
315
667
186
753
354
712
423
514
23
365
820
359
462
9...

input:

1
49651
118 355 2
112
113
146 584 1
145
753 589 2
741
742
574 342 1
575
209 700 1
208
369 440 2
367
368
579 93 2
569
570
758 48 2
736
737
904 710 2
917
918
544 946 2
534
535
627 652 2
593
594
980 966 2
977
978
467 83 2
486
487
695 499 2
725
726
875 848 2
872
873
373 995 2
363
364
38 735 2
33
34
186 ...

output:

112
145
741
575
208
367
569
736
918
534
593
977
487
726
872
363
33
162
291
22
128
344
886
502
22
94
110
755
671
537
825
663
840
956
720
594
187
61
321
355
192
22
617
596
873
892
179
173
644
22
341
143
98
862
89
139
900
453
15
302
237
811
964
329
423
210
261
137
455
49
216
167
229
568
852
64
594
515
...

result:

ok

Test #74:

score: 61
Accepted
time: 12ms
memory: 3684kb

input:

0
10
96 1000000000
95 4
95 32
13 95
49 95
76 95
95 73
95 10
95 42
63 95
17 95
95 52
95 84
95 11
95 2
95 14
95 85
91 95
57 95
24 95
46 95
95 23
77 95
54 95
95 40
33 95
34 95
95 26
95 51
95 89
59 95
82 95
95 28
95 25
95 81
3 95
95 45
95 29
71 95
95 94
95 21
95 22
8 95
92 95
15 95
95 55
56 95
6 95
95 7...

output:

96
0
20
81
60
94
4
48
17
53
28
88
82
34
92
80
51
6
85
13
29
24
55
54
74
76
62
68
19
63
58
3
33
93
70
69
46
14
43
40
25
71
10
87
7
30
59
75
1
21
91
38
67
84
36
72
50
49
77
16
65
37
32
41
86
39
12
2
44
8
18
5
57
27
89
47
11
90
73
23
31
15
61
64
35
83
79
45
42
26
66
22
78
52
9
56
95
96
95
31
49
81
86
8...

input:

1
4308
92 42 1
95
48 6 1
0
95 47 95
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
9...

output:

95
0
47
0
0
58
0
95
95
0
95
0
95
0
95
67
95
95
95
0
95
95
0
0
0
0
95
0
0
95
95
0
0
0
95
95
0
0
95
0
6
95
0
95
46
0
0
95
95
95
13
0
58
13
43
95
27
45
0
0
95
95
95
0
95
95
95
95
0
95
0
53
44
78
35
95
95
0
38
95
95
95
0
95
0
95
0
0
95
95
95
0
31
9
0
0
95
0
0
21
95
95
69
14
92
75
0
0
89
0
89
95
0
95
53
...

result:

ok

Test #75:

score: 61
Accepted
time: 18ms
memory: 3696kb

input:

0
10
541 1000000000
0 527
0 72
0 176
0 246
0 323
190 0
74 0
0 110
518 0
259 0
0 293
0 51
0 59
149 0
0 232
327 0
0 136
0 503
0 142
0 248
64 0
0 398
379 0
0 156
0 265
406 0
84 0
0 49
522 0
0 413
0 513
429 0
170 0
163 0
319 0
233 0
490 0
0 187
0 270
273 0
0 17
471 0
437 0
0 154
276 0
63 0
378 0
0 38
42...

output:

541
0
51
291
487
479
229
220
172
478
484
304
154
290
42
119
175
160
500
75
269
443
57
458
399
338
466
65
372
417
32
292
5
380
212
106
306
156
329
493
359
180
463
256
358
371
186
103
115
255
513
363
529
324
93
118
394
274
197
395
528
491
428
92
495
520
147
16
309
52
66
231
205
539
367
534
141
198
445...

input:

1
6214
55 69 1
540
106 323 1
0
482 37 1
540
232 208 1
0
54 238 1
540
230 58 1
0
495 475 1
540
186 447 1
540
380 510 1
540
119 400 1
540
429 329 1
0
368 140 1
0
156 187 1
540
180 286 1
540
139 303 1
0
101 241 1
540
378 114 1
0
274 226 1
540
303 409 1
0
174 319 1
0
40 540 1
540
105 506 1
0
277 441 1
0...

output:

540
0
540
0
540
0
540
540
540
540
0
0
540
540
0
540
0
540
0
0
540
0
0
0
540
0
0
186
540
540
0
540
540
0
540
0
0
0
540
540
0
0
0
0
0
0
0
540
540
0
0
0
0
0
0
540
0
0
540
0
0
540
540
0
0
0
386
0
0
0
540
0
0
540
0
0
0
540
0
0
0
540
540
0
0
0
0
540
540
540
0
0
540
0
540
0
540
540
0
0
0
540
540
0
540
540
...

result:

ok

Test #76:

score: 61
Accepted
time: 20ms
memory: 3712kb

input:

0
10
1000 1000000000
999 444
999 412
999 312
999 906
999 990
999 616
999 554
718 999
999 228
494 999
999 726
999 728
55 999
370 999
190 999
999 230
999 64
944 999
358 999
999 189
65 999
500 999
457 999
480 999
414 999
999 820
999 29
331 999
999 693
239 999
132 999
999 918
527 999
999 534
145 999
999...

output:

1000
0
184
843
610
934
557
317
43
103
902
561
885
456
906
42
768
641
187
356
950
636
508
303
230
368
532
65
794
591
972
124
519
875
681
829
330
337
748
55
94
955
733
526
854
278
724
503
461
56
428
903
602
483
235
581
986
12
864
735
45
328
155
10
867
982
978
196
426
663
251
416
341
651
21
408
550
312...

input:

1
10180
981 198 1
999
995 574 1
999
382 979 1
0
796 713 1
0
529 138 1
0
467 216 1
999
866 91 1
999
786 390 1
999
32 129 1
0
448 427 1
0
21 252 1
0
140 644 1
0
331 310 1
999
217 603 1
0
849 677 1
0
322 487 1
0
712 86 1
0
712 209 1
999
950 899 1
0
602 973 1
999
710 124 1
0
236 603 1
999
828 231 1
999
...

output:

999
999
0
0
0
999
999
999
0
0
0
0
999
0
0
0
0
999
0
999
0
999
999
999
0
999
0
999
999
0
999
0
0
999
999
0
999
0
999
0
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
999
0
999
999
0
0
999
999
999
999
999
0
999
999
0
999
999
999
0
999
999
0
999
0
999
999
0
0
999
999
0
999
999
0
999
0
999
...

result:

ok

Test #77:

score: 61
Accepted
time: 2ms
memory: 3608kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #78:

score: 61
Accepted
time: 2ms
memory: 3680kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #79:

score: 61
Accepted
time: 2ms
memory: 3708kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #80:

score: 61
Accepted
time: 2ms
memory: 3684kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #81:

score: 61
Accepted
time: 2ms
memory: 3688kb

input:

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

output:

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

input:

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

output:

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

result:

ok

Test #82:

score: 61
Accepted
time: 46ms
memory: 3684kb

input:

0
10
8 1000000000
2 1
4 7
6 0
7 3
1 5
6 5
4 0
8 1000000000
3 2
3 4
4 5
7 6
5 6
0 1
2 1
8 1000000000
0 6
4 7
3 6
3 1
2 5
5 1
4 0
8 1000000000
0 1
2 0
1 3
1 4
2 5
2 6
3 7
8 1000000000
5 1
5 0
6 5
5 7
3 5
5 2
4 5
8 1000000000
0 6
0 3
0 4
7 0
2 0
1 0
5 0
8 1000000000
7 0
1 2
1 5
6 0
4 3
6 3
5 7
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #83:

score: 61
Accepted
time: 46ms
memory: 3608kb

input:

0
10
8 1000000000
4 0
3 4
4 6
6 2
1 4
4 5
7 4
8 1000000000
1 3
3 5
3 7
2 3
0 3
3 6
4 2
8 1000000000
0 4
3 2
2 5
7 2
0 2
2 6
3 1
8 1000000000
0 6
6 1
3 1
7 3
7 4
4 2
0 5
8 1000000000
0 4
3 4
6 5
0 2
7 0
5 1
6 2
8 1000000000
2 4
5 2
4 0
6 1
7 6
5 3
0 1
8 1000000000
5 3
0 1
0 5
2 0
7 6
6 5
4 2
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #84:

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

input:

0
10
8 1000000000
3 7
0 3
3 6
3 2
4 3
3 5
3 1
8 1000000000
2 1
6 3
3 0
0 2
1 4
5 7
3 5
8 1000000000
6 2
6 7
1 6
0 7
0 4
5 6
1 3
8 1000000000
5 3
6 1
0 2
0 4
7 3
6 4
2 5
8 1000000000
2 0
4 0
4 7
3 6
3 5
1 6
3 2
8 1000000000
3 2
2 6
3 5
1 3
3 4
1 0
7 3
8 1000000000
4 1
2 1
0 6
7 4
3 7
6 3
2 5
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #85:

score: 61
Accepted
time: 46ms
memory: 3684kb

input:

0
10
8 1000000000
3 7
0 3
3 6
3 2
4 3
3 5
3 1
8 1000000000
2 1
6 3
3 0
0 2
1 4
5 7
3 5
8 1000000000
6 2
6 7
1 6
0 7
0 4
5 6
1 3
8 1000000000
5 3
6 1
0 2
0 4
7 3
6 4
2 5
8 1000000000
2 0
4 0
4 7
3 6
3 5
1 6
3 2
8 1000000000
3 2
2 6
3 5
1 3
3 4
1 0
7 3
8 1000000000
4 1
2 1
0 6
7 4
3 7
6 3
2 5
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #86:

score: 61
Accepted
time: 34ms
memory: 3692kb

input:

0
10
8 1000000000
3 7
0 3
3 6
3 2
4 3
3 5
3 1
8 1000000000
2 1
6 3
3 0
0 2
1 4
5 7
3 5
8 1000000000
6 2
6 7
1 6
0 7
0 4
5 6
1 3
8 1000000000
5 3
6 1
0 2
0 4
7 3
6 4
2 5
8 1000000000
2 0
4 0
4 7
3 6
3 5
1 6
3 2
8 1000000000
3 2
2 6
3 5
1 3
3 4
1 0
7 3
8 1000000000
4 1
2 1
0 6
7 4
3 7
6 3
2 5
8 100000...

output:

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

input:

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

output:

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

result:

ok

Test #87:

score: 61
Accepted
time: 26ms
memory: 3692kb

input:

0
10
978 1000000000
201 44
44 320
320 907
907 278
278 477
477 755
755 461
461 235
235 83
83 919
919 38
38 443
443 629
629 42
42 13
13 208
208 898
898 205
205 924
924 887
887 170
170 326
326 255
255 684
684 301
301 909
909 161
161 621
621 130
130 587
587 530
530 334
334 700
700 771
771 722
722 712
71...

output:

978
0
502
541
471
905
494
931
643
785
318
802
270
861
237
914
627
730
335
435
963
648
634
217
707
334
446
892
676
913
162
948
623
140
792
690
941
82
370
235
798
414
63
111
368
230
223
907
501
689
143
169
506
958
358
691
598
737
580
694
812
203
206
513
467
155
961
256
714
786
377
626
932
343
899
269
...

input:

1
35090
826 877 2
609
610
86 554 2
261
262
202 334 2
198
199
64 6 2
785
786
826 685 2
947
948
275 245 2
478
479
937 737 2
821
822
607 708 2
577
578
676 693 2
571
572
505 224 2
248
249
151 83 2
196
197
508 800 2
710
711
67 449 2
569
570
23 740 2
778
779
629 15 2
806
807
272 950 2
950
951
493 728 2
41...

output:

609
262
198
786
948
479
821
577
571
248
197
711
569
778
807
950
418
633
803
562
207
505
257
180
902
170
789
590
543
326
721
719
662
213
54
805
612
948
384
327
414
811
115
759
102
492
67
778
561
39
51
778
524
244
877
774
205
237
316
521
462
192
336
715
806
590
403
589
678
144
993
476
404
342
249
345
...

result:

ok

Test #88:

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

input:

0
10
1000 1000000000
897 448
897 517
583 297
897 748
84 650
402 690
131 583
583 601
464 897
336 674
189 897
897 246
843 421
432 742
529 877
812 209
103 109
842 931
795 84
289 103
103 579
84 603
926 897
70 897
183 901
448 647
111 513
646 689
84 949
191 485
745 12
124 578
133 689
423 755
767 124
897 8...

output:

1000
0
158
124
458
445
137
174
595
960
299
605
836
918
387
392
527
105
102
659
182
666
816
201
854
169
329
936
649
521
753
284
100
594
462
761
3
503
346
206
728
905
463
86
964
363
130
362
895
824
734
321
246
301
614
862
781
969
808
260
101
801
405
68
404
113
74
513
307
813
976
979
558
295
587
214
21...

input:

1
47617
229 356 2
227
228
184 736 3
170
178
181
303 80 1
302
955 727 3
956
957
958
991 163 1
72
601 591 1
602
411 857 2
21
22
471 660 2
472
473
790 595 2
952
953
384 222 6
385
390
392
393
394
395
492 508 1
457
496 219 2
935
936
642 625 1
0
368 168 2
370
371
930 195 3
931
932
933
0 727 1
999
995 547 ...

output:

227
170
302
958
72
602
21
473
953
395
457
936
0
371
933
999
747
821
0
198
446
97
0
11
587
50
806
813
997
472
651
584
81
283
178
16
318
938
819
874
3
130
999
630
376
76
148
148
205
151
11
209
835
0
202
935
349
530
157
683
1
0
0
297
536
988
569
590
517
923
842
910
734
707
945
601
436
62
277
928
162
41...

result:

ok

Test #89:

score: 61
Accepted
time: 46ms
memory: 3740kb

input:

0
10
991 1000000000
454 800
702 960
660 644
108 499
445 776
921 520
184 252
730 588
97 163
465 448
361 58
227 250
577 112
191 405
394 157
830 296
589 428
814 830
531 947
161 797
490 127
145 911
858 49
935 552
600 543
138 501
850 916
602 242
114 606
516 650
573 988
121 41
617 723
680 173
619 709
620 ...

output:

991
0
92
429
447
712
410
546
60
943
955
554
698
872
725
620
942
947
635
853
228
392
453
130
911
921
102
550
819
967
541
904
268
131
531
954
766
810
45
152
126
298
856
66
259
746
85
910
309
310
711
676
721
494
898
964
816
322
146
547
689
88
117
679
316
916
763
452
352
615
885
815
907
248
830
926
127
...

input:

1
49922
285 540 2
283
284
294 968 1
306
511 729 2
501
502
36 808 2
292
293
601 144 2
411
412
399 284 2
363
364
756 78 2
55
56
637 77 3
639
640
643
617 95 2
700
701
243 945 2
255
256
298 497 2
305
306
909 487 2
884
885
29 589 2
782
783
339 97 1
338
942 482 1
968
370 390 2
780
781
734 835 2
583
584
15...

output:

283
306
501
293
411
363
56
643
701
256
306
884
782
338
968
780
583
6
457
19
288
544
750
237
870
876
671
989
185
669
645
848
282
708
818
536
253
474
750
464
708
696
358
690
776
352
23
200
167
250
519
135
874
602
754
461
707
387
741
163
264
523
581
852
458
629
476
371
506
702
708
754
802
375
753
564
1...

result:

ok

Test #90:

score: 61
Accepted
time: 38ms
memory: 3712kb

input:

0
10
993 1000000000
659 162
695 292
133 492
301 424
380 243
646 631
297 394
653 704
220 522
825 939
861 883
602 802
939 903
875 50
576 279
343 778
734 393
665 687
340 125
189 579
672 873
201 476
715 325
846 119
682 482
362 218
694 968
463 785
402 585
985 957
207 215
887 618
859 317
871 214
655 459
3...

output:

993
0
477
910
761
754
359
16
200
361
209
461
876
134
640
740
48
348
715
449
915
267
464
176
58
372
672
321
522
647
606
896
266
506
404
42
260
364
686
3
102
719
800
886
297
728
467
553
503
332
845
154
440
174
384
642
251
234
938
458
25
738
572
526
655
700
380
940
34
74
929
953
23
905
950
529
734
912
...

input:

1
50698
589 577 3
591
592
594
974 210 1
972
41 934 1
999
99 924 3
347
354
355
784 941 2
786
788
232 865 1
231
379 386 1
380
436 641 1
873
749 558 3
750
776
777
963 520 2
637
638
82 283 1
999
292 889 2
293
296
379 518 1
380
835 439 2
832
833
5 116 2
2
4
244 392 1
241
309 150 1
310
291 26 2
288
290
23...

output:

594
972
999
355
788
231
380
873
777
637
999
296
380
832
2
241
310
288
220
965
906
118
20
731
761
67
198
572
838
837
915
580
729
624
496
169
118
176
65
757
941
94
383
118
18
837
548
118
480
631
876
541
218
717
118
155
697
98
363
390
979
706
150
782
775
35
442
646
899
9
727
554
568
214
170
195
116
706...

result:

ok

Test #91:

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

input:

0
10
993 1000000000
659 162
695 292
133 492
301 424
380 243
646 631
297 394
653 704
220 522
825 939
861 883
602 802
939 903
875 50
576 279
343 778
734 393
665 687
340 125
189 579
672 873
201 476
715 325
846 119
682 482
362 218
694 968
463 785
402 585
985 957
207 215
887 618
859 317
871 214
655 459
3...

output:

993
0
477
910
761
754
359
16
200
361
209
461
876
134
640
740
48
348
715
449
915
267
464
176
58
372
672
321
522
647
606
896
266
506
404
42
260
364
686
3
102
719
800
886
297
728
467
553
503
332
845
154
440
174
384
642
251
234
938
458
25
738
572
526
655
700
380
940
34
74
929
953
23
905
950
529
734
912
...

input:

1
50698
589 577 3
591
592
594
974 210 1
972
41 934 1
999
99 924 3
347
354
355
784 941 2
786
788
232 865 1
231
379 386 1
380
436 641 1
873
749 558 3
750
776
777
963 520 2
637
638
82 283 1
999
292 889 2
293
296
379 518 1
380
835 439 2
832
833
5 116 2
2
4
244 392 1
241
309 150 1
310
291 26 2
288
290
23...

output:

594
972
999
355
788
231
380
873
777
637
999
296
380
832
2
241
310
288
220
965
906
118
20
731
761
67
198
572
838
837
915
580
729
624
496
169
118
176
65
757
941
94
383
118
18
837
548
118
480
631
876
541
218
717
118
155
697
98
363
390
979
706
150
782
775
35
442
646
899
9
727
554
568
214
170
195
116
706...

result:

ok

Test #92:

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

input:

0
10
992 1000000000
274 302
761 266
243 116
753 556
69 885
191 771
127 476
904 335
735 660
798 382
116 771
973 331
753 437
318 813
250 127
64 904
929 494
127 885
318 538
135 116
822 415
894 258
187 322
874 759
574 890
379 812
988 653
332 331
572 244
215 346
825 401
510 519
517 777
958 897
911 176
40...

output:

992
0
988
975
231
4
289
570
274
266
888
423
330
116
255
601
838
370
128
217
43
415
309
428
541
42
651
659
809
817
325
708
934
634
931
238
607
5
921
281
968
844
490
405
698
468
613
560
789
419
675
614
883
224
615
771
935
632
260
830
943
456
335
295
441
609
777
517
803
627
133
261
680
957
449
447
605
...

input:

1
49569
217 351 1
218
460 750 2
461
464
852 679 1
853
943 992 2
944
945
773 803 3
416
417
418
22 641 1
58
86 730 4
87
88
89
122
141 712 1
142
471 982 3
409
411
412
894 971 1
896
67 500 1
66
697 298 1
696
498 17 1
497
554 274 1
639
958 856 1
979
781 55 2
782
784
110 996 4
94
97
100
109
536 354 1
940
...

output:

218
464
853
945
416
58
122
142
409
896
66
696
497
639
979
784
94
940
69
551
83
106
102
669
365
616
0
829
987
609
144
680
310
764
622
736
844
221
819
952
316
591
314
658
353
93
224
743
886
81
639
486
485
0
219
390
547
789
979
639
789
869
365
0
927
219
618
989
288
0
391
0
164
741
0
158
841
154
24
257
...

result:

ok

Test #93:

score: 61
Accepted
time: 46ms
memory: 3748kb

input:

0
10
992 1000000000
274 302
761 266
243 116
753 556
69 885
191 771
127 476
904 335
735 660
798 382
116 771
973 331
753 437
318 813
250 127
64 904
929 494
127 885
318 538
135 116
822 415
894 258
187 322
874 759
574 890
379 812
988 653
332 331
572 244
215 346
825 401
510 519
517 777
958 897
911 176
40...

output:

992
0
988
975
231
4
289
570
274
266
888
423
330
116
255
601
838
370
128
217
43
415
309
428
541
42
651
659
809
817
325
708
934
634
931
238
607
5
921
281
968
844
490
405
698
468
613
560
789
419
675
614
883
224
615
771
935
632
260
830
943
456
335
295
441
609
777
517
803
627
133
261
680
957
449
447
605
...

input:

1
49569
217 351 1
218
460 750 2
461
464
852 679 1
853
943 992 2
944
945
773 803 3
416
417
418
22 641 1
58
86 730 4
87
88
89
122
141 712 1
142
471 982 3
409
411
412
894 971 1
896
67 500 1
66
697 298 1
696
498 17 1
497
554 274 1
639
958 856 1
979
781 55 2
782
784
110 996 4
94
97
100
109
536 354 1
940
...

output:

218
464
853
945
416
58
122
142
409
896
66
696
497
639
979
784
94
940
69
551
83
106
102
669
365
616
0
829
987
609
144
680
310
764
622
736
844
221
819
952
316
591
314
658
353
93
224
743
886
81
639
486
485
0
219
390
547
789
979
639
789
869
365
0
927
219
618
989
288
0
391
0
164
741
0
158
841
154
24
257
...

result:

ok

Test #94:

score: 61
Accepted
time: 46ms
memory: 3688kb

input:

0
10
1000 1000000000
880 197
507 738
947 24
750 375
785 686
514 578
885 51
988 286
813 807
384 826
436 909
304 273
322 772
368 921
802 592
951 168
937 494
937 450
667 703
62 981
618 350
800 460
668 12
126 532
723 262
525 741
950 567
220 587
477 326
212 582
160 788
772 225
754 196
553 741
471 31
332 ...

output:

1000
0
760
550
869
238
278
747
289
154
166
258
49
749
348
685
22
243
167
424
459
731
596
185
325
374
221
738
363
464
519
394
465
111
317
118
47
898
787
804
699
796
953
190
900
954
904
26
536
14
650
581
918
858
73
746
227
332
778
312
574
714
987
145
343
228
177
646
303
218
716
368
121
9
94
199
311
34...

input:

1
50684
593 34 1
592
839 124 1
840
998 225 2
52
984
398 925 1
401
316 779 1
317
461 941 1
454
245 642 1
246
94 132 3
81
91
93
783 64 2
784
796
313 449 1
351
603 671 2
604
606
945 737 10
737
930
931
937
939
940
941
942
943
944
566 932 2
564
565
107 693 3
109
125
834
142 848 1
150
17 797 1
0
415 277 1...

output:

592
840
52
401
317
454
246
81
796
351
606
737
564
834
150
0
0
861
729
570
830
551
970
359
397
360
592
869
123
248
12
967
435
716
805
362
0
692
654
545
49
981
75
975
307
247
68
11
882
490
49
572
440
691
54
178
264
210
11
678
256
698
226
63
923
11
12
890
636
24
218
52
338
706
36
56
505
264
918
117
915...

result:

ok

Test #95:

score: 61
Accepted
time: 16ms
memory: 3740kb

input:

0
10
731 1000000000
730 284
530 730
304 730
730 104
730 252
48 730
615 730
472 730
730 414
730 441
64 730
150 730
351 730
86 730
730 542
730 207
416 730
730 145
45 730
730 159
409 730
603 730
730 353
690 730
71 730
730 579
730 684
730 93
730 88
38 730
730 419
22 730
595 730
730 675
730 633
730 183
4...

output:

731
0
207
516
38
636
690
311
367
276
128
264
400
550
654
637
28
523
594
206
355
113
608
698
173
32
108
152
619
684
410
357
520
146
543
490
438
57
42
700
455
41
588
499
335
13
711
139
507
724
486
251
567
174
682
402
186
689
223
653
669
54
177
515
230
719
458
29
661
133
364
422
705
327
297
660
135
599...

input:

1
5230
520 530 1
0
481 390 1
0
461 193 1
0
471 127 1
730
682 122 1
0
172 496 1
0
58 127 1
0
484 722 1
0
152 115 1
0
432 42 1
730
154 76 1
0
636 325 1
0
154 351 1
730
108 300 1
730
404 196 1
0
637 457 1
0
203 281 1
0
4 39 1
0
246 557 1
730
235 286 1
0
628 128 1
730
221 370 1
0
505 131 1
0
199 53 1
0
...

output:

0
0
0
730
0
0
0
0
0
730
0
0
730
730
0
0
0
0
730
0
730
0
0
0
730
0
730
0
0
0
666
0
730
0
0
730
0
0
0
0
0
0
12
730
730
0
0
0
730
730
0
0
730
0
730
0
730
730
0
0
730
730
730
0
730
0
0
0
0
730
0
0
0
0
730
730
0
0
0
730
0
0
730
0
0
0
0
730
0
0
0
730
0
730
730
222
0
730
730
0
0
0
0
730
0
0
0
730
0
0
0
0
7...

result:

ok

Test #96:

score: 61
Accepted
time: 20ms
memory: 3704kb

input:

0
10
1000 1000000000
999 515
999 808
389 999
137 999
936 999
887 999
287 999
999 299
999 704
14 999
999 937
387 999
841 999
78 999
894 999
757 999
691 999
71 999
779 999
999 676
838 999
999 524
999 359
999 19
29 999
405 999
192 999
17 999
136 999
31 999
999 952
999 735
696 999
942 999
999 223
530 99...

output:

1000
0
206
737
831
722
546
412
112
570
663
2
508
388
277
989
349
481
971
332
975
551
280
716
94
939
60
909
687
826
974
413
969
35
809
115
471
940
87
850
616
516
204
445
44
697
406
110
446
502
572
538
688
409
531
813
334
83
495
714
160
510
917
750
468
796
248
839
736
718
611
552
981
752
57
543
631
81...

input:

1
10180
300 611 1
0
999 722 1
0
283 822 1
0
280 864 1
999
875 757 1
0
366 879 1
999
359 741 1
0
408 656 1
999
354 708 1
999
239 174 1
999
434 970 1
999
575 746 1
999
264 922 1
999
74 682 1
0
42 335 1
999
729 217 1
999
104 667 1
0
862 900 1
999
338 911 1
999
534 510 1
0
875 488 1
999
902 243 1
0
393 ...

output:

0
0
0
999
0
999
0
999
999
999
999
999
999
0
999
999
0
999
999
0
999
0
0
999
999
0
0
999
999
0
999
999
0
0
999
999
999
999
0
999
999
436
999
999
999
999
0
999
999
999
0
999
999
999
0
0
0
999
999
0
0
999
0
999
0
999
999
999
999
999
999
999
0
0
999
999
0
999
0
0
999
0
999
999
999
0
999
999
999
999
999
...

result:

ok

Test #97:

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

input:

0
10
892 1000000000
606 640
172 727
509 98
109 640
296 474
23 332
782 57
427 887
57 179
720 206
766 218
884 395
110 412
188 813
801 345
131 824
359 689
686 789
274 346
167 842
429 845
249 550
273 798
588 61
631 364
120 266
296 213
819 110
10 420
401 438
286 261
813 61
454 67
824 59
174 859
252 271
3...

output:

892
0
99
518
108
344
627
391
431
90
680
493
352
736
708
853
279
607
264
430
719
618
329
228
161
647
497
439
310
668
72
246
531
20
705
700
725
328
747
48
699
152
614
730
248
476
783
840
515
229
134
50
488
802
129
216
652
23
261
843
872
374
461
21
569
625
888
298
797
603
332
495
686
819
123
737
296
48...

input:

1
13208
18 528 8
2
11
12
13
14
15
16
17
332 840 11
333
334
335
336
337
338
339
340
341
342
398
19 583 10
9
10
11
12
13
14
15
16
17
18
800 668 10
801
802
803
804
805
806
807
808
809
880
46 731 10
6
37
38
39
40
41
42
43
44
45
809 795 10
810
811
812
813
814
815
816
817
818
889
671 289 2
667
670
481 128...

output:

2
398
9
880
6
889
667
821
752
864
368
75
760
222
331
195
165
336
165
803
171
693
300
171
455
720
5
864
80
171
786
87
100
272
100
535
208
432
890
479
314
720
570
272
473
752
525
622
1
108
679
822
54
756
834
2
525
262
716
509
541
565
736
165
679
822
222
786
246
353
398
434
432
66
109
688
605
171
735
1...

result:

ok

Test #98:

score: 61
Accepted
time: 12ms
memory: 3756kb

input:

0
10
1000 1000000000
180 624
132 59
664 556
950 732
810 7
7 911
627 313
332 648
703 375
220 710
922 375
812 676
664 387
725 759
223 711
329 138
536 671
316 235
182 116
65 893
948 116
521 965
728 495
502 950
521 460
103 682
574 331
89 865
490 979
530 125
980 65
176 190
308 702
308 597
309 107
523 566...

output:

1000
0
910
858
659
598
135
29
897
666
191
680
957
691
935
814
553
30
986
126
560
423
893
97
669
527
150
493
731
835
689
908
938
500
842
800
862
790
446
47
909
470
941
693
347
34
345
352
333
291
709
750
137
54
183
237
594
294
127
734
542
269
116
914
481
711
436
13
849
210
783
66
767
23
919
361
350
35...

input:

1
16365
588 63 9
570
580
581
582
583
584
585
586
587
771 202 8
772
773
774
775
776
777
778
811
69 881 8
77
85
93
101
109
117
125
954
18 377 9
91
164
603
676
725
798
871
944
999
465 293 3
462
463
464
540 127 8
541
542
543
544
545
546
547
572
202 824 6
109
172
178
184
190
196
484 472 9
457
476
477
478...

output:

570
811
954
603
462
572
109
457
997
417
115
844
533
420
501
798
509
657
2
604
77
740
583
530
952
982
868
214
702
836
515
285
85
191
811
241
871
25
587
213
869
325
716
145
869
537
435
215
725
886
544
535
298
173
556
890
2
183
324
829
324
733
350
717
452
578
603
131
108
332
126
630
828
871
702
328
727...

result:

ok

Test #99:

score: 61
Accepted
time: 24ms
memory: 3680kb

input:

0
10
712 1000000000
165 500
293 270
484 552
3 324
308 190
621 104
561 389
581 286
154 188
251 457
223 99
633 660
446 540
160 610
150 323
93 265
273 380
268 297
38 376
670 568
653 209
253 291
384 187
434 193
422 131
96 418
625 325
72 325
299 590
645 552
486 384
28 153
37 246
309 566
91 686
468 464
57...

output:

712
0
18
631
44
613
102
207
253
129
332
153
325
155
569
209
264
486
252
456
151
337
37
445
194
662
51
441
559
701
287
169
67
191
523
38
183
375
10
219
525
636
76
149
315
306
580
23
451
443
600
359
621
162
229
311
199
538
671
230
308
388
195
646
243
679
258
190
629
673
371
533
474
89
599
245
596
422
...

input:

1
33400
96 213 3
462
463
464
402 245 3
600
601
603
160 710 3
161
587
588
678 217 3
601
603
677
163 199 3
164
664
666
179 321 3
180
366
367
320 334 3
321
679
681
365 399 3
366
636
637
205 530 3
206
372
373
333 331 3
481
482
483
293 45 3
271
272
292
184 345 3
185
271
273
203 260 3
204
472
473
650 236 ...

output:

462
603
588
601
664
366
679
636
373
483
271
273
472
530
223
198
563
363
336
252
626
119
643
437
639
285
329
270
112
538
505
396
59
529
238
447
659
178
244
411
203
401
27
402
646
536
530
410
96
509
369
612
628
452
153
117
538
203
511
553
230
6
612
268
647
266
335
442
622
253
169
180
706
579
707
654
2...

result:

ok

Test #100:

score: 61
Accepted
time: 38ms
memory: 3696kb

input:

0
10
1000 1000000000
339 519
436 552
9 671
650 693
652 769
640 509
384 65
726 126
261 226
444 449
419 177
123 140
813 825
4 483
859 484
506 423
273 852
939 263
891 108
985 3
299 95
490 816
846 130
963 551
714 667
771 311
856 316
515 601
647 905
2 877
612 372
163 540
642 602
717 169
699 632
854 124
5...

output:

1000
0
611
926
271
44
871
351
484
861
291
157
279
124
472
49
751
566
830
631
421
734
72
668
866
359
85
512
691
904
323
171
335
865
416
710
826
583
805
969
598
312
700
648
196
672
450
410
772
217
944
363
778
492
821
531
580
961
208
596
349
931
248
502
499
210
445
934
309
873
280
55
489
785
361
723
71...

input:

1
33377
492 859 3
167
169
170
274 794 3
782
783
785
677 977 3
409
410
676
802 308 3
258
259
260
198 13 3
948
949
950
863 497 3
584
586
862
154 701 3
738
739
740
102 453 3
103
547
548
483 961 3
484
966
968
328 793 3
329
451
453
960 70 3
840
841
842
949 156 3
120
122
948
751 634 3
404
406
750
547 779 ...

output:

167
785
409
260
950
584
738
547
966
453
840
122
406
513
1
707
152
518
777
62
758
304
395
527
869
225
234
804
858
508
414
607
235
285
861
835
896
629
764
164
324
780
921
540
966
923
400
84
898
493
292
993
185
302
198
85
995
597
849
721
720
607
901
146
732
532
855
353
611
155
251
536
246
197
704
923
7...

result:

ok

Test #101:

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

input:

0
10
905 1000000000
149 541
744 692
648 655
441 692
692 263
648 156
754 161
20 648
538 541
285 648
843 541
720 541
692 791
648 167
357 648
533 648
196 541
626 754
692 511
754 485
56 754
893 541
796 541
19 692
541 110
471 541
833 541
754 508
541 593
406 692
355 754
541 777
618 648
648 760
754 121
294...

output:

905
0
169
401
633
413
288
378
279
224
512
857
50
79
575
196
779
744
886
164
898
468
502
73
276
709
615
37
253
799
596
755
97
217
533
90
65
371
121
13
197
306
824
587
60
598
734
539
388
695
793
694
389
803
363
501
205
874
548
493
280
760
153
862
658
171
421
129
546
194
231
595
365
814
433
804
676
64
...

input:

1
4502
531 10 42
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
589
211 406 1
35
243 545 1
239
100 569 69
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
1...

output:

589
35
239
771
480
684
494
640
214
479
904
222
531
471
895
35
904
288
904
551
890
735
100
674
831
815
494
771
904
676
855
531
510
280
904
355
794
887
494
109
26
35
904
49
49
793
239
49
534
229
73
904
171
771
100
904
672
601
196
100
432
735
527
0
873
214
696
299
904
676
214
895
904
771
555
479
0
815
...

result:

ok

Test #102:

score: 61
Accepted
time: 14ms
memory: 3764kb

input:

0
10
1000 1000000000
864 948
95 883
976 573
252 601
415 95
95 514
601 388
573 857
666 136
535 95
751 666
605 541
666 971
289 541
69 501
601 321
370 573
438 601
681 515
541 795
948 668
948 827
515 14
515 94
478 601
319 95
69 342
461 186
573 704
69 706
573 301
573 16
772 601
788 666
948 537
666 530
51...

output:

1000
0
334
130
421
600
448
332
995
573
429
604
492
68
950
784
786
223
384
681
45
255
749
111
39
576
583
148
153
412
270
935
27
566
637
469
293
967
548
96
129
327
791
394
121
667
352
691
90
706
443
644
923
99
951
136
450
515
91
554
971
635
812
231
887
292
516
660
170
194
803
584
391
164
930
162
365
6...

input:

1
4293
758 770 1
458
454 575 1
489
223 206 1
259
640 997 1
900
759 835 44
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
902
198 133 1
143
830 754 1
840
154 726 1
38
648 613 1...

output:

458
489
259
900
902
143
840
38
739
871
988
228
143
188
228
84
0
999
871
167
999
489
988
131
84
228
778
23
556
560
988
739
584
988
333
982
601
188
552
111
711
939
489
900
627
999
0
300
871
848
988
371
206
803
229
588
0
375
23
206
848
999
332
489
778
84
900
104
495
272
264
0
552
489
706
454
951
488
87...

result:

ok

Extra Test:

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

Server Time: 2024-11-29 16:49:46 | OpenSource Project