12 12 5 3 5
2 11 3 3 9 5
1 9 6 9 1 7 4 4 7 1 7 4
10 9 10 12 11 4 12 4
9 7 8 1 3
4 3
2 2 6 6 6 2 2 6 8 2 8 2
6 7 50 1 3
3 4
2 2 2 6 3 6 5 4 5 4 3 2
12 12 5 3 0
2 11 3 3 9 5
10 10 40 1 3
1 1
3 1 3 9 5 2 5 10 7 1 7 9
10 10 50 1 5
10 1
1 1 9 9
2 5 7 10
5 2 10 7
1 7 3 9
7 1 9 3
20 20 10 10 40
2 18 13 9 4 17 17 3 15 6 4 2 11 4 19 20
12 14 11 1
9 6 9 2 12 18 6 18 2 20 2 20 8 7 4 3
20 5 20 5 20 11 18 13 11 15 11 7 13 12 7 18
11 12 7 12 17 18 11 18 7 1 5 3 6 16 6 8
3 12 3 10 18 7 4 7 2 13 2 3 9 3 5 3
5 10 5 6 7 18 7 2 7 20 7 18 18 5 12 11
3 13 1 11 18 7 14 7 19 9 13 3 20 4 20 4
4 4 2 6 9 5 1 13 10 15 10 11 15 19 1 19
18 1 18 1 15 17 15 11 14 5 2 5 10 15 4 9
20 4 16 4 19 14 17 12 14 5 14 3 20 5 20 5
11 10 7 10 17 11 15 11 12 1 12 1 19 13 3 13
20 20 8 10 20
5 15 9 20 7 7 4 7 10 2 15 5 19 20 8 16
13 17 19 6
1 7 1 7 19 1 19 1 7 1 7 1 11 12 3 20
11 20 11 18 20 9 20 9 7 20 7 20 1 3 1 3
3 5 1 5 1 7 1 7 11 9 3 1 9 13 1 13
2 20 2 6 1 17 1 17 10 20 10 10 20 3 20 3
20 16 10 6 20 2 20 2 20 1 18 3 6 1 6 1
20 20 5 36 10
8 3 7 8 15 5 9 3 14 2 15 13 13 13 5 1
20 8 11 13 20 2 12 6 17 1 20 4
10 2 6 20 10 18 10 5 13 15 12 3 1 12
16 5 3 5 10 11 10 9 20 1 9 15 1 2 2 11
11 18 1 11 10 6 1 1 7 9 5 3 12 11
19 5 13 11 17 4 9 4 7 11 1 17 19 9 15 9
6 9 6 3 8 1 8 1 2 5 2 1 6 6 4 6
12 17 12 15 3 17 1 17
100 100 115 10 60
4 44 81 48 26 65 47 95 14 81 5 63 86 49 44 93
82 6 59 82
80 41 50 41 77 38 77 24 100 5 96 1 42 76 28 90
25 93 25 91 91 30 73 48 74 1 64 1 76 22 68 14
97 53 95 51 83 28 73 18 75 7 73 5 18 15 6 3
87 82 77 72 99 74 73 100 21 21 3 39 81 1 49 33
63 38 47 38 38 68 2 68 33 86 7 86 89 71 85 75
37 10 31 16 40 95 28 83 47 4 37 14 48 5 36 17
98 52 84 66 98 98 96 98 60 99 60 49 60 41 42 41
47 36 47 10 63 100 63 100 89 88 77 100 63 80 1 80
63 74 63 70 45 41 39 35 79 46 79 40 9 45 7 43
29 92 5 92 95 70 81 56 54 7 4 57 76 85 70 91
34 16 24 6 41 52 35 46 24 49 12 49 51 92 49 94
41 15 41 13 80 62 76 62 30 52 30 4 74 56 48 56
100 2 18 2 98 15 62 51 49 97 17 97 100 43 98 43
78 24 12 24 16 74 4 74 35 80 25 90 81 89 75 89
76 12 72 16 20 2 16 6 19 88 1 70 86 100 86 96
1000 1000 185000 1 100
1000 1
1 1 999 999
2 5 997 1000
5 2 1000 997
1 7 993 999
7 1 999 993
2 11 991 1000
11 2 1000 991
1 13 987 999
13 1 999 987
2 17 985 1000
17 2 1000 985
1 19 981 999
19 1 999 981
2 23 979 1000
23 2 1000 979
1 25 975 999
25 1 999 975
2 29 973 1000
29 2 1000 973
1 31 969 999
31 1 999 969
2 35 967 1000
35 2 1000 967
1 37 963 999
37 1 999 963
2 41 961 1000
41 2 1000 961
1 43 957 999
43 1 999 957
2 47 955 1000
47 2 1000 955
1 49 951 999
49 1 999 951
2 53 949 1000
53 2 1000 949
1 55 945 999
55 1 999 945
2 59 943 1000
59 2 1000 943
1 61 939 999
61 1 999 939
2 65 937 1000
65 2 1000 937
1 67 933 999
67 1 999 933
2 71 931 1000
71 2 1000 931
1 73 927 999
73 1 999 927
2 77 925 1000
77 2 1000 925
1 79 921 999
79 1 999 921
2 83 919 1000
83 2 1000 919
1 85 915 999
85 1 999 915
2 89 913 1000
89 2 1000 913
1 91 909 999
91 1 999 909
2 95 907 1000
95 2 1000 907
1 97 903 999
97 1 999 903
2 101 901 1000
101 2 1000 901
1 103 897 999
103 1 999 897
2 107 895 1000
107 2 1000 895
1 109 891 999
109 1 999 891
2 113 889 1000
113 2 1000 889
1 115 885 999
115 1 999 885
2 119 883 1000
119 2 1000 883
1 121 879 999
121 1 999 879
2 125 877 1000
125 2 1000 877
1 127 873 999
127 1 999 873
2 131 871 1000
131 2 1000 871
1 133 867 999
133 1 999 867
2 137 865 1000
137 2 1000 865
1 139 861 999
139 1 999 861
2 143 859 1000
143 2 1000 859
1 145 855 999
145 1 999 855
2 149 853 1000
149 2 1000 853
1 151 849 999
1000 1000 101000 1 100
1 1
400 1 400 999
402 2 402 1000
404 1 404 999
406 2 406 1000
408 1 408 999
410 2 410 1000
412 1 412 999
414 2 414 1000
416 1 416 999
418 2 418 1000
420 1 420 999
422 2 422 1000
424 1 424 999
426 2 426 1000
428 1 428 999
430 2 430 1000
432 1 432 999
434 2 434 1000
436 1 436 999
438 2 438 1000
440 1 440 999
442 2 442 1000
444 1 444 999
446 2 446 1000
448 1 448 999
450 2 450 1000
452 1 452 999
454 2 454 1000
456 1 456 999
458 2 458 1000
460 1 460 999
462 2 462 1000
464 1 464 999
466 2 466 1000
468 1 468 999
470 2 470 1000
472 1 472 999
474 2 474 1000
476 1 476 999
478 2 478 1000
480 1 480 999
482 2 482 1000
484 1 484 999
486 2 486 1000
488 1 488 999
490 2 490 1000
492 1 492 999
494 2 494 1000
496 1 496 999
498 2 498 1000
500 1 500 999
502 2 502 1000
504 1 504 999
506 2 506 1000
508 1 508 999
510 2 510 1000
512 1 512 999
514 2 514 1000
516 1 516 999
518 2 518 1000
520 1 520 999
522 2 522 1000
524 1 524 999
526 2 526 1000
528 1 528 999
530 2 530 1000
532 1 532 999
534 2 534 1000
536 1 536 999
538 2 538 1000
540 1 540 999
542 2 542 1000
544 1 544 999
546 2 546 1000
548 1 548 999
550 2 550 1000
552 1 552 999
554 2 554 1000
556 1 556 999
558 2 558 1000
560 1 560 999
562 2 562 1000
564 1 564 999
566 2 566 1000
568 1 568 999
570 2 570 1000
572 1 572 999
574 2 574 1000
576 1 576 999
578 2 578 1000
580 1 580 999
582 2 582 1000
584 1 584 999
586 2 586 1000
588 1 588 999
590 2 590 1000
592 1 592 999
594 2 594 1000
596 1 596 999
598 2 598 1000
1000 1000 100000 1 0
500 500
1000 1000 20 100 100
60 776
190 912
872 506
912 378
980 814
662 774
850 468
2 820
804 596
966 478
260 858
514 440
958 100
200 348
828 864
472 34
836 994
116 416
388 830
710 870
130 696
714 846
150 262
586 188
316 592
412 710
448 952
486 864
918 628
394 26
356 150
636 730
532 910
922 862
614 178
912 990
8 98
138 156
480 378
40 992
508 574
484 64
104 962
352 448
286 202
148 510
736 720
690 984
246 352
274 506
908 254
848 124
82 234
642 726
82 606
598 924
302 714
26 550
974 116
200 286
480 82
418 918
694 762
710 896
722 612
802 106
172 552
548 312
640 30
818 22
874 862
316 450
500 580
584 218
724 158
738 124
134 728
422 226
268 728
772 526
116 518
622 212
228 12
544 54
362 272
594 152
780 778
414 748
254 280
758 112
782 622
182 204
654 830
748 414
738 642
914 572
96 572
146 756
202 11
674 22
676 272 676 272
432 814 432 814
380 82 380 82
790 494 790 494
346 2 346 2
342 948 342 948
76 746 76 746
604 616 604 616
132 948 132 948
462 448 462 448
852 286 852 286
372 336 372 336
800 480 800 480
904 762 904 762
720 30 720 30
158 216 158 216
190 616 190 616
162 50 162 50
84 678 84 678
906 234 906 234
640 722 640 722
578 958 578 958
534 748 534 748
48 660 48 660
382 192 382 192
172 890 172 890
354 216 354 216
738 920 738 920
924 488 924 488
640 82 640 82
154 26 154 26
702 760 702 760
714 898 714 898
742 108 742 108
294 254 294 254
612 900 612 900
752 58 752 58
38 2 38 2
660 518 660 518
946 8 946 8
208 450 208 450
640 804 640 804
712 346 712 346
758 930 758 930
72 568 72 568
282 376 282 376
652 148 652 148
506 186 506 186
372 426 372 426
556 826 556 826
194 422 194 422
360 150 360 150
520 786 520 786
644 170 644 170
248 812 248 812
592 978 592 978
582 60 582 60
220 28 220 28
692 900 692 900
412 550 412 550
408 112 408 112
712 926 712 926
990 310 990 310
256 10 256 10
926 36 926 36
952 566 952 566
804 910 804 910
828 96 828 96
20 568 20 568
234 428 234 428
450 104 450 104
448 134 448 134
386 54 386 54
804 326 804 326
704 304 704 304
324 376 324 376
764 726 764 726
816 654 816 654
262 892 262 892
630 954 630 954
494 618 494 618
310 452 310 452
674 374 674 374
978 946 978 946
186 220 186 220
252 864 252 864
99 614 99 614
670 702 670 702
30 388 30 388
692 474 692 474
852 736 852 736
462 18 462 18
672 618 672 618
512 278 512 278
232 936 232 936
554 142 554 142
596 728 596 728
104 866 104 866
49 49 49 49
108 1 108 1
1000 1000 200000 1 100
3 3
5 2 1000 2
7 3 1000 3
9 4 1000 4
11 5 1000 5
13 6 1000 6
15 7 1000 7
17 8 1000 8
19 9 1000 9
21 10 1000 10
23 11 1000 11
25 12 1000 12
27 13 1000 13
29 14 1000 14
31 15 1000 15
33 16 1000 16
35 17 1000 17
37 18 1000 18
39 19 1000 19
41 20 1000 20
43 21 1000 21
45 22 1000 22
47 23 1000 23
49 24 1000 24
51 25 1000 25
53 26 1000 26
55 27 1000 27
57 28 1000 28
59 29 1000 29
61 30 1000 30
63 31 1000 31
65 32 1000 32
67 33 1000 33
69 34 1000 34
71 35 1000 35
73 36 1000 36
75 37 1000 37
77 38 1000 38
79 39 1000 39
81 40 1000 40
83 41 1000 41
85 42 1000 42
87 43 1000 43
89 44 1000 44
91 45 1000 45
93 46 1000 46
95 47 1000 47
97 48 1000 48
99 49 1000 49
101 50 1000 50
103 51 1000 51
105 52 1000 52
107 53 1000 53
109 54 1000 54
111 55 1000 55
113 56 1000 56
115 57 1000 57
117 58 1000 58
119 59 1000 59
121 60 1000 60
123 61 1000 61
125 62 1000 62
127 63 1000 63
129 64 1000 64
131 65 1000 65
133 66 1000 66
135 67 1000 67
137 68 1000 68
139 69 1000 69
141 70 1000 70
143 71 1000 71
145 72 1000 72
147 73 1000 73
149 74 1000 74
151 75 1000 75
153 76 1000 76
155 77 1000 77
157 78 1000 78
159 79 1000 79
161 80 1000 80
163 81 1000 81
165 82 1000 82
167 83 1000 83
169 84 1000 84
171 85 1000 85
173 86 1000 86
175 87 1000 87
177 88 1000 88
179 89 1000 89
181 90 1000 90
183 91 1000 91
185 92 1000 92
187 93 1000 93
189 94 1000 94
191 95 1000 95
193 96 1000 96
195 97 1000 97
197 98 1000 98
199 99 1000 99
201 100 1000 100
203 101 1000 101
1000 1000 200000 1 100
3 3
1 1 1 1000
2 5 2 1000
3 7 3 1000
4 9 4 1000
5 11 5 1000
6 13 6 1000
7 15 7 1000
8 17 8 1000
9 19 9 1000
10 21 10 1000
11 23 11 1000
12 25 12 1000
13 27 13 1000
14 29 14 1000
15 31 15 1000
16 33 16 1000
17 35 17 1000
18 37 18 1000
19 39 19 1000
20 41 20 1000
21 43 21 1000
22 45 22 1000
23 47 23 1000
24 49 24 1000
25 51 25 1000
26 53 26 1000
27 55 27 1000
28 57 28 1000
29 59 29 1000
30 61 30 1000
31 63 31 1000
32 65 32 1000
33 67 33 1000
34 69 34 1000
35 71 35 1000
36 73 36 1000
37 75 37 1000
38 77 38 1000
39 79 39 1000
40 81 40 1000
41 83 41 1000
42 85 42 1000
43 87 43 1000
44 89 44 1000
45 91 45 1000
46 93 46 1000
47 95 47 1000
48 97 48 1000
49 99 49 1000
50 101 50 1000
105 52 1000 52
107 53 1000 53
109 54 1000 54
111 55 1000 55
113 56 1000 56
115 57 1000 57
117 58 1000 58
119 59 1000 59
121 60 1000 60
123 61 1000 61
125 62 1000 62
127 63 1000 63
129 64 1000 64
131 65 1000 65
133 66 1000 66
135 67 1000 67
137 68 1000 68
139 69 1000 69
141 70 1000 70
143 71 1000 71
145 72 1000 72
147 73 1000 73
149 74 1000 74
151 75 1000 75
153 76 1000 76
155 77 1000 77
157 78 1000 78
159 79 1000 79
161 80 1000 80
163 81 1000 81
165 82 1000 82
167 83 1000 83
169 84 1000 84
171 85 1000 85
173 86 1000 86
175 87 1000 87
177 88 1000 88
179 89 1000 89
181 90 1000 90
183 91 1000 91
185 92 1000 92
187 93 1000 93
189 94 1000 94
191 95 1000 95
193 96 1000 96
195 97 1000 97
197 98 1000 98
199 99 1000 99
201 100 1000 100
203 101 1000 101
1000 1000 100 1 14
501 501
500 500 500 502
500 502 496 502
496 502 496 508
496 508 490 508
490 508 490 520
490 520 478 520
478 520 478 544
478 544 454 544
454 544 454 592
454 592 408 592
408 592 408 686
408 686 312 686
312 686 312 870
312 870 120 870
-1