TEST DATA FOR `ombro'
A Zip file of this data
is available.
Input for test 1
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
Output for test 1
110
Input for test 2
200 199
1000 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 1000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1000000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
19 20 1000000000
20 21 1000000000
21 22 1000000000
22 23 1000000000
23 24 1000000000
24 25 1000000000
25 26 1000000000
26 27 1000000000
27 28 1000000000
28 29 1000000000
29 30 1000000000
30 31 1000000000
31 32 1000000000
32 33 1000000000
33 34 1000000000
34 35 1000000000
35 36 1000000000
36 37 1000000000
37 38 1000000000
38 39 1000000000
39 40 1000000000
40 41 1000000000
41 42 1000000000
42 43 1000000000
43 44 1000000000
44 45 1000000000
45 46 1000000000
46 47 1000000000
47 48 1000000000
48 49 1000000000
49 50 1000000000
50 51 1000000000
51 52 1000000000
52 53 1000000000
53 54 1000000000
54 55 1000000000
55 56 1000000000
56 57 1000000000
57 58 1000000000
58 59 1000000000
59 60 1000000000
60 61 1000000000
61 62 1000000000
62 63 1000000000
63 64 1000000000
64 65 1000000000
65 66 1000000000
66 67 1000000000
67 68 1000000000
68 69 1000000000
69 70 1000000000
70 71 1000000000
71 72 1000000000
72 73 1000000000
73 74 1000000000
74 75 1000000000
75 76 1000000000
76 77 1000000000
77 78 1000000000
78 79 1000000000
79 80 1000000000
80 81 1000000000
81 82 1000000000
82 83 1000000000
83 84 1000000000
84 85 1000000000
85 86 1000000000
86 87 1000000000
87 88 1000000000
88 89 1000000000
89 90 1000000000
90 91 1000000000
91 92 1000000000
92 93 1000000000
93 94 1000000000
94 95 1000000000
95 96 1000000000
96 97 1000000000
97 98 1000000000
98 99 1000000000
99 100 1000000000
100 101 1000000000
101 102 1000000000
102 103 1000000000
103 104 1000000000
104 105 1000000000
105 106 1000000000
106 107 1000000000
107 108 1000000000
108 109 1000000000
109 110 1000000000
110 111 1000000000
111 112 1000000000
112 113 1000000000
113 114 1000000000
114 115 1000000000
115 116 1000000000
116 117 1000000000
117 118 1000000000
118 119 1000000000
119 120 1000000000
120 121 1000000000
121 122 1000000000
122 123 1000000000
123 124 1000000000
124 125 1000000000
125 126 1000000000
126 127 1000000000
127 128 1000000000
128 129 1000000000
129 130 1000000000
130 131 1000000000
131 132 1000000000
132 133 1000000000
133 134 1000000000
134 135 1000000000
135 136 1000000000
136 137 1000000000
137 138 1000000000
138 139 1000000000
139 140 1000000000
140 141 1000000000
141 142 1000000000
142 143 1000000000
143 144 1000000000
144 145 1000000000
145 146 1000000000
146 147 1000000000
147 148 1000000000
148 149 1000000000
149 150 1000000000
150 151 1000000000
151 152 1000000000
152 153 1000000000
153 154 1000000000
154 155 1000000000
155 156 1000000000
156 157 1000000000
157 158 1000000000
158 159 1000000000
159 160 1000000000
160 161 1000000000
161 162 1000000000
162 163 1000000000
163 164 1000000000
164 165 1000000000
165 166 1000000000
166 167 1000000000
167 168 1000000000
168 169 1000000000
169 170 1000000000
170 171 1000000000
171 172 1000000000
172 173 1000000000
173 174 1000000000
174 175 1000000000
175 176 1000000000
176 177 1000000000
177 178 1000000000
178 179 1000000000
179 180 1000000000
180 181 1000000000
181 182 1000000000
182 183 1000000000
183 184 1000000000
184 185 1000000000
185 186 1000000000
186 187 1000000000
187 188 1000000000
188 189 1000000000
189 190 1000000000
190 191 1000000000
191 192 1000000000
192 193 1000000000
193 194 1000000000
194 195 1000000000
195 196 1000000000
196 197 1000000000
197 198 1000000000
198 199 1000000000
199 200 1000000000
Output for test 2
199000000000
Input for test 3
13 22
58 8
14 7
23 69
18 4
17 75
6 10
34 6
46 7
9 5
26 63
27 55
10 16
60 23
11 5 198
12 13 76
1 8 623
6 10 405
7 13 842
2 10 331
5 6 112
5 12 922
8 4 39
13 5 176
11 2 955
6 2 657
9 2 326
5 8 899
5 3 398
11 4 560
3 8 20
12 2 990
8 9 776
6 10 638
2 9 844
7 2 551
Output for test 3
842
Input for test 4
39 156
0 2
2 3
1 0
6 9
1 14
0 2
0 15
3 5
3 14
0 1
0 0
1 0
1 0
8 13
4 3
2 0
0 12
3 0
0 5
5 0
0 1
8 0
19 9
2 1
13 9
2 0
3 8
10 12
23 1
1 3
3 0
11 3
10 6
2 7
1 1
13 3
11 5
0 7
2 0
14 29 984
23 28 848
39 28 578
8 1 361
3 28 303
1 5 894
34 36 633
22 26 160
30 39 684
15 13 447
15 26 296
3 37 865
21 36 539
12 5 77
8 35 679
4 35 691
22 29 681
33 39 211
2 30 420
19 33 516
16 8 862
30 11 296
33 20 995
12 20 227
31 27 934
39 20 468
39 2 544
36 23 710
8 24 350
18 31 504
2 35 632
1 26 714
8 8 301
39 19 968
25 11 72
5 38 619
20 37 499
13 33 990
5 1 307
16 19 777
9 9 846
9 9 861
20 5 982
39 33 449
27 18 689
31 22 25
15 30 850
29 3 842
26 36 563
24 12 76
14 9 600
39 17 994
38 36 198
17 24 262
3 1 705
27 31 811
10 7 749
29 24 710
3 10 751
6 22 869
15 36 917
33 35 524
10 22 754
30 38 256
4 29 997
23 5 397
13 14 720
33 32 167
17 34 725
35 28 50
4 4 917
30 25 872
23 34 422
2 13 898
4 16 100
34 27 360
5 1 758
11 33 435
11 38 288
38 23 877
8 26 626
2 5 134
30 17 392
29 18 298
27 10 761
4 32 833
24 36 676
7 7 35
22 7 969
31 5 228
6 1 29
24 2 639
27 20 227
2 9 601
29 36 310
22 39 52
2 23 221
10 18 887
39 39 213
17 19 923
17 25 768
3 9 14
22 24 178
17 14 383
19 4 525
29 25 52
4 26 970
31 24 738
25 12 788
15 29 111
8 6 227
30 37 113
2 19 252
5 24 33
5 3 752
1 32 518
24 24 514
19 4 765
3 28 303
15 3 742
35 39 12
11 18 139
13 19 758
37 12 798
25 5 505
27 33 892
3 17 7
32 35 69
6 27 18
20 30 8
22 25 17
8 25 809
2 37 44
3 23 601
17 9 862
22 24 699
19 16 811
28 36 867
1 31 604
29 11 806
21 21 933
29 29 211
15 19 101
9 11 205
14 27 201
1 37 543
32 16 746
30 4 320
12 32 83
9 21 632
35 31 58
19 20 723
16 24 114
38 32 634
5 34 431
7 34 359
Output for test 4
781
Input for test 5
54 317
12 1
2 2
27 4
1 22
7 0
30 15
27 0
9 2
0 6
3 3
0 43
33 0
1 2
0 5
1 18
0 0
30 13
5 2
41 8
0 13
27 0
8 1
2 0
0 3
2 8
21 7
0 1
7 29
5 21
1 0
2 0
7 0
0 8
4 0
1 2
23 37
7 5
0 18
37 17
10 50
0 0
0 11
3 56
31 11
10 2
0 0
0 5
68 15
0 1
9 9
2 5
5 38
1 21
20 2
53 6 776
8 50 971
40 9 98
25 33 580
33 16 753
6 48 589
16 13 660
4 44 926
29 32 654
14 54 792
24 14 364
42 22 155
15 23 574
40 47 264
3 25 228
25 30 872
16 7 305
7 11 534
40 39 327
36 14 720
19 37 73
45 24 895
28 1 254
19 2 274
4 20 459
5 44 975
16 5 503
39 27 333
13 29 835
18 26 781
23 44 635
3 50 169
20 39 705
5 19 337
37 38 642
40 43 372
50 20 463
50 20 926
7 32 682
17 49 384
3 17 173
10 35 410
18 16 247
42 21 311
13 19 511
20 4 73
17 15 569
18 11 302
23 17 155
3 49 804
39 52 262
11 23 305
47 2 471
14 43 717
14 17 665
14 37 419
2 53 305
25 32 821
13 16 299
32 34 923
46 19 472
38 29 577
26 21 405
30 50 714
16 26 486
5 39 360
29 41 410
51 11 96
46 24 693
2 1 881
39 8 392
19 7 750
37 49 658
2 24 417
25 40 334
27 6 567
26 34 538
24 46 812
30 37 392
36 1 79
38 39 378
3 4 547
13 40 538
5 4 522
46 44 565
5 32 330
2 4 233
1 43 280
26 18 938
21 54 206
16 53 654
50 1 103
21 29 478
2 33 829
7 25 924
28 45 542
39 8 743
6 8 288
19 33 918
15 53 676
10 30 791
6 26 5
5 8 361
6 26 572
25 32 402
18 5 480
5 5 74
48 27 719
42 45 576
53 21 35
9 47 523
49 52 769
19 19 316
34 40 699
28 10 142
7 44 207
15 48 222
45 3 768
29 44 124
23 42 929
15 12 33
53 6 441
40 41 605
19 36 999
38 9 450
51 32 231
14 46 586
51 52 903
23 42 468
39 10 899
37 41 871
12 1 170
54 41 504
22 21 230
45 20 917
23 16 318
45 45 909
21 4 114
16 26 649
17 26 441
5 8 872
20 19 112
3 34 279
26 17 37
31 23 731
6 46 204
28 52 662
41 34 26
51 50 359
11 12 134
35 32 629
44 51 875
16 54 661
28 25 591
22 17 307
20 38 962
49 11 135
14 51 58
53 10 983
46 20 728
27 16 189
15 6 234
21 37 383
39 27 488
4 48 128
7 13 867
17 23 722
8 53 897
48 51 205
46 4 294
54 30 250
40 44 997
38 27 590
35 27 713
18 46 695
2 52 968
2 30 383
50 53 949
18 47 43
50 38 373
9 53 719
37 54 58
33 37 968
27 33 106
47 51 60
6 14 488
48 15 699
5 26 827
29 44 277
50 1 383
36 25 870
35 23 277
2 1 482
11 43 571
47 35 27
20 41 329
44 34 693
6 54 837
21 29 361
43 40 114
49 21 388
31 17 486
50 35 698
14 45 317
27 37 51
19 2 298
41 8 318
24 29 195
32 49 525
45 54 51
20 48 144
35 40 168
2 35 234
2 11 956
45 37 141
14 17 845
23 4 907
27 27 22
31 20 70
41 26 975
36 45 468
13 25 769
7 42 152
50 44 96
46 34 522
25 47 806
21 31 923
40 3 914
33 50 318
37 52 141
2 34 846
14 46 170
11 14 596
43 10 819
46 1 858
48 41 761
50 23 823
17 8 711
10 3 914
22 1 9
21 3 692
10 16 457
1 43 117
17 31 958
1 38 583
33 31 482
4 42 496
20 4 883
1 13 12
47 50 952
37 16 675
5 41 645
35 41 628
25 20 774
1 36 528
32 14 762
50 33 278
52 15 998
7 31 183
51 24 502
41 22 739
49 42 443
50 23 779
24 9 342
5 9 299
24 41 506
36 52 425
35 49 526
53 17 868
30 13 714
3 15 423
23 25 36
29 21 656
54 6 100
44 10 324
15 34 908
16 15 332
11 11 89
4 9 763
43 39 12
14 3 488
21 25 865
54 15 431
33 15 165
20 20 190
32 35 384
7 12 801
18 22 421
54 41 887
53 45 83
11 20 805
53 41 493
27 2 939
6 51 920
5 16 422
30 9 797
18 16 493
52 49 988
26 48 453
41 9 105
23 19 656
24 33 581
10 5 211
11 26 255
42 47 457
39 22 490
31 2 261
35 53 746
37 41 88
26 43 695
5 11 929
19 50 627
36 6 651
16 16 78
30 4 125
37 42 981
53 18 27
Output for test 5
378
Input for test 6
79 639
0 10
1 0
0 0
8 0
36 4
7 0
0 0
0 0
5 26
5 0
20 3
18 0
6 0
0 3
0 16
0 0
0 0
2 1
0 5
0 23
9 0
1 18
0 18
0 2
0 0
2 12
8 2
7 2
0 0
2 3
0 14
0 0
11 0
0 0
15 0
19 0
12 5
16 2
17 0
12 6
6 0
0 0
34 24
0 3
0 1
0 1
0 36
0 4
0 6
3 0
2 16
0 0
1 0
3 6
1 8
2 1
2 0
0 5
2 0
0 0
1 0
0 0
0 15
1 2
3 9
0 1
1 0
9 17
5 5
6 0
15 0
4 25
0 16
1 0
1 0
1 0
0 1
1 0
33 0
52 16 502
33 2 167
75 31 961
7 55 280
43 8 505
67 20 398
39 32 258
40 46 821
32 1 789
27 22 361
64 74 994
52 2 422
2 76 590
35 57 25
18 20 788
51 7 158
14 45 486
7 60 920
17 12 708
55 14 24
8 52 624
4 24 514
2 79 252
5 10 48
62 27 150
76 52 465
55 40 709
16 46 872
47 37 306
53 13 344
56 74 444
53 77 753
1 53 85
25 57 452
26 14 133
46 10 278
23 40 338
20 55 216
75 76 83
38 24 428
14 55 907
71 3 215
18 4 124
72 28 868
57 53 175
42 73 828
79 71 984
50 11 477
67 6 225
42 44 285
3 32 678
38 23 82
70 15 304
50 8 944
62 64 752
63 1 171
73 79 719
72 25 751
46 12 488
70 28 586
13 31 33
11 68 974
65 33 513
43 57 378
48 40 372
1 23 977
26 70 469
18 37 534
44 3 739
51 47 812
76 34 233
54 19 556
54 4 993
68 46 721
65 14 254
20 68 115
1 15 834
11 32 392
44 50 263
64 76 21
33 47 948
6 21 719
22 74 767
69 38 743
69 77 590
29 17 55
65 72 660
12 3 120
49 21 888
63 6 449
19 13 35
34 72 380
42 68 806
28 33 473
60 22 755
2 51 726
11 36 712
9 23 828
13 46 957
66 5 188
12 23 681
4 56 315
16 72 995
77 21 65
71 1 242
62 56 129
70 66 487
69 49 203
71 61 313
68 23 133
70 34 330
59 37 201
65 27 813
35 25 284
37 70 1001
36 53 255
30 43 748
10 32 487
12 77 943
60 40 647
7 30 751
56 63 639
57 24 336
50 58 350
38 70 150
1 1 488
20 30 792
26 15 67
30 26 843
40 60 73
48 67 944
63 18 484
36 74 7
60 44 856
58 56 445
46 57 366
8 76 745
65 76 419
75 26 587
33 41 263
55 63 227
56 46 509
66 2 307
74 36 785
36 68 574
66 35 674
72 17 688
28 2 65
52 52 939
22 5 600
27 59 398
19 10 729
4 51 934
8 45 993
30 1 311
4 42 681
34 9 294
61 11 587
5 62 329
28 58 7
13 60 44
34 78 733
22 56 907
66 63 219
41 68 874
29 71 17
2 1 13
69 61 956
59 65 910
75 67 163
41 54 624
15 9 572
78 5 809
7 45 993
6 6 904
35 10 819
79 65 57
53 54 654
36 34 673
56 29 402
29 45 790
61 34 882
41 7 107
23 14 396
43 73 741
50 3 152
24 3 957
52 30 151
7 65 319
55 16 138
12 19 612
22 54 135
15 16 437
66 38 125
58 55 713
56 26 776
62 24 31
29 76 786
49 57 698
23 33 675
54 44 876
51 40 924
56 29 738
67 69 478
67 48 782
60 24 902
55 60 8
53 63 802
54 32 638
41 29 834
19 4 494
69 29 53
14 5 390
54 71 313
27 33 512
54 13 76
57 68 507
29 16 759
26 69 982
79 6 842
7 78 180
6 67 900
45 1 839
32 29 783
9 55 502
8 5 60
5 61 580
62 64 92
23 10 83
69 63 545
65 44 205
39 50 233
66 15 254
72 46 3
20 30 957
25 37 893
42 17 416
23 78 179
18 75 981
57 64 161
22 25 903
64 63 345
43 25 891
23 71 632
31 11 527
68 35 84
31 52 80
3 49 20
39 66 12
4 19 683
7 40 225
29 79 518
45 42 755
51 39 477
77 69 464
28 58 566
69 63 138
73 65 812
49 78 326
21 3 112
31 63 713
40 12 683
57 32 899
74 57 316
3 29 584
21 56 7
49 45 477
49 13 407
18 37 678
28 32 267
30 37 686
72 76 835
9 53 55
67 22 236
59 24 711
40 20 300
54 68 788
25 38 253
36 30 711
71 32 525
57 62 727
27 29 187
38 38 772
79 79 587
19 58 457
65 18 493
63 46 313
1 71 348
5 27 112
46 72 576
38 25 200
42 51 48
41 63 448
14 63 647
38 2 311
6 41 373
72 24 485
47 78 123
35 58 394
27 24 973
50 36 126
31 77 591
65 39 496
32 27 247
77 64 428
21 69 748
11 61 856
72 4 539
74 13 45
24 14 84
20 63 882
40 14 164
6 53 113
35 59 500
22 56 965
35 51 609
64 62 924
12 29 922
12 24 950
16 22 765
71 41 644
58 55 137
43 60 288
65 70 544
64 66 251
48 76 71
75 60 372
58 46 286
45 57 989
18 47 519
5 39 847
29 17 800
66 59 614
52 20 134
43 58 605
39 26 452
6 75 771
10 29 768
42 48 979
47 40 798
19 44 660
6 47 795
22 34 364
18 60 479
59 23 988
61 36 853
5 42 34
62 26 802
60 67 78
60 9 161
3 27 166
63 7 85
36 28 54
17 45 709
17 78 591
74 59 302
28 38 908
57 74 132
34 54 257
34 10 621
19 12 740
76 50 458
47 6 276
1 76 101
40 13 417
51 61 529
43 10 536
27 41 204
60 49 4
31 3 558
34 75 663
39 72 328
49 14 696
8 69 129
65 4 455
16 54 955
26 71 535
49 18 875
66 53 774
32 4 12
62 12 394
24 25 85
35 49 870
26 31 800
13 16 934
66 6 508
21 32 173
40 1 539
73 41 382
76 47 958
57 4 589
8 27 13
5 61 684
15 7 581
69 19 98
21 59 353
52 1 873
24 40 542
13 33 562
55 5 934
49 61 917
55 43 821
61 47 321
10 36 816
15 25 78
9 46 265
63 72 327
69 70 150
50 3 902
46 32 411
10 2 685
31 31 764
24 66 82
28 76 858
64 11 241
68 73 164
51 32 131
35 21 665
32 46 302
37 12 421
46 75 331
11 26 969
72 25 345
21 52 142
31 11 289
15 53 234
19 25 327
15 34 791
55 40 813
18 77 951
13 18 840
9 4 396
11 75 83
53 17 277
12 22 439
60 11 643
51 29 857
49 18 756
67 72 488
51 10 952
75 23 909
16 6 393
37 70 164
2 43 653
48 54 716
51 9 591
2 35 143
31 4 500
14 70 676
36 16 322
56 11 505
68 2 608
4 38 245
14 14 464
16 62 698
13 8 939
21 9 768
56 39 863
30 52 12
74 8 377
24 38 554
50 26 85
3 4 10
25 72 762
10 8 319
49 74 414
72 15 391
49 71 456
30 21 10
79 69 242
40 14 750
11 38 791
62 40 757
46 64 159
43 74 1001
23 18 996
63 64 733
33 9 55
15 13 461
24 12 976
40 26 920
43 36 498
72 72 315
26 38 319
50 2 265
32 78 554
8 61 122
77 68 85
34 58 305
64 2 495
59 16 30
42 58 460
63 51 221
44 51 966
63 75 160
77 27 414
58 34 196
23 7 190
51 40 907
11 78 1001
62 33 416
35 74 547
18 32 886
72 75 836
6 59 553
74 31 388
61 9 685
5 6 176
16 31 912
59 42 704
78 78 525
33 8 293
45 25 207
4 72 578
66 77 76
45 72 610
51 28 788
65 32 377
60 22 459
15 55 42
22 53 969
37 6 915
21 26 395
36 4 273
47 69 866
12 35 683
7 60 782
64 20 412
23 79 58
12 68 326
42 10 568
45 21 195
56 41 457
67 77 884
69 19 662
44 31 693
65 12 363
35 76 354
11 73 543
33 5 487
6 46 887
32 11 266
38 67 969
15 29 498
49 18 483
72 37 645
26 22 944
13 31 517
74 41 737
54 49 61
23 29 880
55 60 512
28 18 869
17 7 992
3 55 207
8 23 322
17 23 72
63 35 532
55 29 169
65 58 332
54 55 402
63 30 592
4 32 797
64 49 473
74 26 499
76 33 240
35 50 385
69 8 943
55 63 617
57 23 653
2 52 534
1 35 793
10 38 397
36 77 960
43 71 682
1 67 691
60 76 628
62 65 140
74 41 389
10 72 460
3 73 115
50 49 880
22 58 968
79 68 540
27 31 995
79 7 481
59 66 373
10 24 388
47 18 408
42 27 950
59 29 696
24 53 693
23 74 235
34 48 468
43 74 510
42 48 562
58 28 860
15 37 138
12 58 985
49 74 719
53 53 990
26 51 329
46 73 526
45 28 327
6 45 690
77 7 645
50 39 530
10 54 321
46 65 508
75 10 125
50 37 333
29 62 244
34 29 737
9 48 127
56 53 953
47 51 207
32 75 720
44 59 861
67 1 369
43 75 649
13 20 647
11 23 760
59 57 976
21 40 582
65 70 44
48 37 517
38 69 265
42 33 145
19 75 995
36 13 447
37 26 569
50 36 53
45 15 520
68 10 199
34 49 414
27 18 556
71 30 564
6 71 316
78 11 482
Output for test 6
314
Input for test 7
95 919
0 0
0 1
0 0
1 2
1 0
0 0
0 0
0 5
0 0
0 2
0 5
0 3
1 4
4 0
7 0
0 0
11 9
0 2
0 1
0 0
0 0
0 3
0 0
1 0
3 0
0 0
0 0
1 0
2 0
1 1
0 3
0 0
0 0
12 0
0 0
0 6
4 0
0 0
0 0
5 0
0 0
2 0
0 0
1 7
0 0
0 0
0 0
1 3
0 0
7 0
9 16
0 0
0 0
0 3
1 10
0 0
0 0
0 0
0 0
0 0
4 0
1 0
5 0
0 0
0 2
0 0
0 6
0 0
1 0
0 0
1 7
5 4
1 4
0 0
0 2
0 0
0 2
0 0
7 1
0 0
0 0
3 0
6 0
8 1
2 2
3 1
7 0
0 12
0 0
0 0
0 2
1 0
5 2
0 1
0 0
82 17 212
83 60 565
73 3 703
66 56 153
82 37 379
57 19 434
82 72 264
25 93 702
54 21 125
62 20 46
21 3 708
40 85 831
8 60 777
88 30 639
81 14 834
85 67 956
51 53 839
30 75 380
45 33 419
73 95 380
90 17 376
25 54 828
20 61 700
16 50 816
65 33 167
58 22 275
66 69 76
50 1 711
31 42 235
33 16 474
48 11 775
69 35 699
73 51 807
41 67 504
32 33 940
40 90 492
15 60 295
40 11 611
47 41 786
81 71 647
18 23 237
64 88 614
65 62 606
31 4 986
41 36 744
82 72 711
50 86 840
80 31 671
18 74 933
89 59 339
83 74 321
82 39 548
20 6 903
8 33 729
57 73 193
45 60 810
25 11 501
60 90 43
11 9 145
2 2 391
57 81 899
42 67 499
14 83 535
51 88 810
88 49 177
62 93 927
15 19 196
47 79 333
15 89 594
53 87 114
51 48 185
25 86 97
37 5 111
51 52 828
2 41 937
26 7 475
11 21 855
3 64 913
84 78 23
75 32 763
64 83 821
36 9 515
74 42 743
1 92 52
16 93 225
78 21 100
37 31 836
15 34 283
70 19 481
18 91 926
51 59 652
31 94 261
1 69 249
70 70 500
89 82 173
56 61 443
26 3 233
16 17 88
66 83 43
4 5 337
66 53 432
19 83 862
73 83 723
72 54 121
68 47 235
58 4 351
65 29 942
10 41 211
78 8 69
69 12 536
55 74 78
4 89 160
44 63 999
55 40 631
39 9 161
13 66 459
44 35 622
74 41 187
25 20 82
58 88 841
90 47 684
79 48 612
55 91 236
15 47 153
28 86 214
84 95 237
45 40 14
34 18 775
60 42 606
94 1 250
40 88 395
57 71 116
67 31 978
44 42 701
61 70 402
82 55 667
74 2 548
1 32 632
61 89 479
46 87 507
23 28 250
43 81 782
19 52 612
82 1 89
93 58 841
95 44 377
95 22 153
40 20 141
93 77 173
93 27 31
87 46 554
76 89 423
37 9 249
26 87 615
59 84 377
60 83 394
17 80 605
71 24 668
61 18 357
41 15 979
12 3 132
7 78 210
83 17 973
18 42 101
44 2 292
33 58 297
65 74 782
20 46 291
87 11 806
40 48 803
16 59 140
38 63 62
53 47 702
73 61 668
84 10 399
81 42 437
65 8 804
33 24 1002
18 12 523
23 51 535
40 67 420
57 6 375
56 56 822
71 33 711
29 19 301
80 4 672
1 68 215
87 2 884
29 19 993
74 38 599
71 75 32
28 36 420
45 91 970
13 63 5
38 88 975
70 72 168
47 69 583
29 57 647
31 86 1000
47 64 93
16 36 782
48 63 501
83 9 661
80 21 313
12 56 770
54 30 484
4 73 537
18 3 730
30 33 767
57 77 519
27 89 167
67 42 184
48 29 886
23 10 150
58 22 682
84 72 134
84 76 175
53 90 370
82 25 247
3 78 150
79 6 26
95 73 904
76 25 202
65 44 887
71 6 314
38 90 750
27 75 768
89 32 893
59 19 473
58 18 504
38 94 76
14 93 674
26 70 91
62 39 42
13 15 485
77 49 893
23 75 42
40 69 171
55 29 359
91 86 19
12 28 667
33 38 170
28 60 709
44 24 169
8 36 399
73 15 728
34 34 343
69 73 713
41 33 908
27 25 821
28 33 303
30 62 377
24 86 944
87 31 261
93 39 859
16 13 401
81 47 635
28 20 678
43 57 773
83 84 37
18 16 971
69 43 706
63 63 559
21 54 620
2 48 630
12 60 425
40 46 543
2 70 726
37 18 790
6 2 149
92 17 762
17 85 997
3 52 726
72 69 303
77 67 246
21 79 656
76 20 905
76 18 687
1 55 712
77 57 236
46 50 429
27 63 240
51 63 747
41 39 890
82 17 929
72 38 70
29 15 713
29 91 194
95 91 837
83 72 763
69 22 654
69 45 536
58 95 110
95 38 582
8 21 273
86 92 809
48 22 318
30 47 340
29 46 245
79 30 525
87 1 678
47 69 111
70 28 170
59 24 932
81 32 344
25 22 706
2 66 967
89 95 85
76 25 42
55 8 897
10 92 589
75 43 839
93 14 589
12 73 231
60 55 356
33 79 187
94 81 495
81 74 991
20 52 217
2 11 657
13 18 69
21 92 162
2 86 765
7 94 688
35 58 512
92 87 859
74 82 182
24 65 854
69 81 860
43 82 793
21 91 823
91 16 682
10 17 774
40 20 321
42 55 550
3 51 152
39 26 536
61 50 664
55 20 268
5 62 739
57 79 322
32 71 253
95 80 70
53 22 657
10 63 296
22 65 342
22 5 979
8 62 700
59 21 196
92 22 330
16 79 108
31 12 596
59 11 307
5 60 1001
65 67 717
82 85 316
53 11 302
47 15 207
90 73 233
57 66 591
82 82 717
88 14 137
72 72 178
37 73 315
24 40 867
69 26 28
84 75 4
5 27 624
85 21 605
88 78 158
15 61 73
19 53 671
35 26 850
54 60 28
38 80 213
85 53 697
26 38 524
69 42 318
32 29 129
64 18 502
66 32 411
55 48 961
57 79 451
29 37 183
74 75 509
60 61 143
71 87 103
62 60 687
75 91 749
14 56 222
24 27 46
3 81 233
28 39 620
75 64 735
87 43 186
79 7 542
29 78 828
14 41 44
37 17 515
88 28 493
61 51 483
63 50 909
17 77 791
49 57 976
23 45 490
64 28 542
74 54 530
72 64 624
35 5 491
82 89 258
92 54 127
31 22 802
49 35 947
8 84 360
30 8 223
91 71 42
60 50 662
12 23 830
95 54 583
2 40 19
31 37 357
16 67 992
47 17 803
59 21 463
30 47 703
41 42 355
80 4 310
74 15 746
39 11 704
2 13 47
56 40 619
63 52 195
93 3 738
60 59 36
12 85 712
69 30 603
4 12 602
82 85 235
85 26 476
47 27 461
48 80 150
82 47 315
84 41 458
7 3 821
46 14 816
37 80 960
63 83 644
95 66 232
43 56 847
93 4 772
61 51 375
65 34 659
25 22 317
80 28 150
3 71 617
10 9 122
44 71 666
88 67 260
27 14 296
83 8 178
71 68 951
39 34 583
54 59 266
8 43 87
62 43 431
28 52 656
77 95 66
11 85 556
14 16 62
69 1 57
32 71 1000
42 14 389
82 64 538
48 71 253
39 34 352
4 62 649
73 40 101
21 50 52
33 61 381
57 34 284
89 63 529
88 6 841
28 88 524
20 37 950
54 75 560
36 79 26
66 56 762
92 73 488
13 10 109
44 64 919
72 54 445
75 46 282
88 70 714
70 89 653
25 48 535
13 80 139
59 50 824
46 46 949
82 55 124
84 95 703
18 71 446
14 47 350
15 40 152
6 11 37
33 35 605
36 44 207
23 4 193
61 49 957
77 36 605
5 21 514
90 38 319
39 51 896
34 65 733
3 67 54
57 1 454
64 37 196
54 59 949
91 21 178
78 3 366
21 4 973
59 93 563
70 37 282
35 70 409
33 69 656
44 30 672
87 93 343
76 52 156
71 47 581
16 26 916
92 43 635
89 4 438
26 73 121
9 9 734
57 41 723
74 84 826
91 73 997
49 53 90
62 25 998
92 40 676
27 33 78
62 24 715
92 46 608
63 54 1002
5 13 275
15 86 830
55 81 471
89 31 38
76 89 182
14 82 726
69 13 385
68 75 835
71 68 635
50 33 65
38 34 883
62 49 95
72 5 722
59 90 104
3 70 394
66 80 874
71 50 106
10 19 73
67 89 564
74 44 49
36 78 906
11 41 559
67 18 184
14 76 423
82 79 67
49 46 463
94 18 284
56 27 253
93 90 787
4 65 490
39 6 715
15 13 382
34 79 23
59 89 457
76 73 367
66 23 637
35 21 990
55 76 807
91 70 626
29 73 725
3 13 520
58 25 242
55 58 336
69 21 521
60 93 900
35 61 567
49 95 394
80 54 836
43 47 611
93 72 986
17 74 5
38 33 573
71 87 597
84 57 259
91 22 331
72 53 879
75 3 66
3 82 470
7 27 45
77 24 576
29 37 902
86 74 736
75 49 160
23 34 844
84 27 240
47 3 418
70 78 12
89 80 9
66 83 918
87 64 9
86 90 709
61 80 535
69 60 430
65 79 23
19 67 888
87 18 219
16 84 932
40 77 121
47 48 267
83 39 980
41 26 945
35 84 814
7 54 509
24 20 975
74 38 468
56 29 670
40 42 159
95 78 648
39 29 954
63 13 473
56 53 778
42 87 769
10 93 234
37 21 627
48 91 141
27 51 365
20 87 716
2 86 554
64 30 886
71 92 979
22 49 543
90 91 580
51 5 678
65 39 560
95 83 302
67 11 437
62 30 535
3 32 171
21 92 817
64 67 88
24 88 609
33 79 28
33 34 155
27 95 496
38 94 376
45 63 908
7 29 463
55 32 198
94 49 461
64 18 852
28 38 545
40 71 613
44 5 876
49 32 567
93 69 956
28 18 887
69 24 369
41 76 819
44 74 85
40 40 106
7 64 153
59 8 822
95 48 339
69 1 379
39 93 850
8 26 403
39 91 178
93 36 353
82 79 98
25 20 579
77 26 528
72 85 608
38 81 140
9 54 332
8 92 29
76 2 902
66 37 207
73 34 757
64 21 99
27 45 339
29 27 678
94 95 658
68 34 594
89 43 359
15 50 869
34 30 78
75 92 869
16 70 960
87 35 521
40 61 281
15 86 47
13 84 970
91 56 869
60 46 433
78 60 37
93 91 528
11 67 660
61 83 606
49 71 422
54 16 203
8 27 525
78 39 265
54 32 28
61 91 655
12 73 475
13 71 867
37 78 377
57 43 913
52 88 582
74 46 128
62 51 590
39 33 291
2 83 592
19 46 83
79 54 473
8 63 332
24 4 384
14 61 847
84 14 381
31 87 154
88 50 146
76 89 403
5 87 892
57 10 832
12 85 652
37 92 90
33 20 673
9 31 408
28 19 548
36 46 568
89 38 317
95 15 316
31 17 181
50 73 937
16 82 589
36 20 608
23 49 212
13 58 773
61 85 203
23 22 433
72 15 588
76 11 607
66 42 427
51 88 988
42 9 722
19 44 748
88 66 99
76 75 453
93 40 5
34 63 486
16 36 47
36 13 183
67 79 296
19 31 922
43 69 946
51 87 314
77 77 169
57 57 181
91 54 756
16 84 142
60 2 906
18 34 362
81 5 526
87 23 874
85 62 44
89 14 622
40 91 566
51 49 732
44 45 595
70 60 355
64 22 796
90 39 502
33 21 430
52 12 4
8 1 913
30 89 876
43 31 640
34 81 300
78 26 10
77 95 421
65 60 368
54 54 894
73 84 884
1 40 279
43 44 350
52 70 392
74 14 718
88 47 493
55 26 600
64 8 792
34 72 856
22 28 753
48 2 488
91 3 586
50 45 622
9 93 286
54 71 252
31 63 381
85 23 104
69 86 15
50 21 817
90 42 655
82 89 677
66 81 366
82 35 18
47 43 599
82 94 632
35 29 752
31 16 962
50 84 916
76 38 33
79 29 678
10 16 94
38 78 514
68 61 214
42 13 893
16 91 940
57 27 775
63 54 184
91 9 171
11 84 469
46 67 989
24 74 479
90 16 426
46 81 765
33 27 116
63 39 465
90 92 710
48 60 581
21 52 179
75 63 869
71 10 113
89 34 266
28 25 4
40 68 42
15 5 42
2 64 305
79 59 460
84 8 256
51 29 357
19 5 324
71 75 538
92 65 674
93 92 472
9 34 499
8 48 261
27 50 1000
84 30 359
40 19 109
54 66 431
22 81 846
49 57 820
86 53 691
57 47 936
53 56 329
21 60 634
86 87 612
27 72 428
20 16 789
23 70 922
49 88 59
81 42 715
90 32 351
68 88 935
36 46 116
38 63 286
87 53 188
84 76 419
15 95 492
57 20 958
65 68 874
62 53 561
17 44 259
24 16 287
75 52 115
88 86 942
63 74 26
26 62 14
58 73 964
13 34 336
34 1 557
44 59 119
1 76 543
80 1 167
54 75 274
70 65 192
54 29 552
87 52 315
5 14 258
18 26 816
44 56 611
45 4 701
93 1 150
89 81 657
5 36 154
62 8 756
16 61 745
41 49 10
31 53 616
91 68 404
90 16 681
88 58 966
47 55 522
81 48 252
15 49 794
23 15 612
Output for test 7
317
Input for test 8
111 1246
18 179
5 27
8 37
18 4
0 425
8 0
26 0
2 12
75 1
84 0
0 0
0 24
3 0
125 2
1 85
30 46
0 104
806 0
0 401
264 203
0 0
0 0
6 0
3 0
0 4
37 0
11 406
81 0
6 201
47 343
10 406
0 442
35 0
0 1
11 0
748 236
7 36
0 906
851 0
33 0
2 28
523 16
222 45
1 281
0 109
1000 82
1 8
15 0
0 47
0 2
0 494
0 184
5 0
34 0
0 14
28 272
0 613
420 280
664 5
81 25
114 11
35 0
166 231
0 42
0 0
0 0
9 0
196 24
1 0
1 0
12 0
929 0
0 0
176 193
0 663
0 48
4 60
398 0
233 0
10 4
11 0
0 27
0 105
43 0
29 48
1000 706
0 0
10 3
0 0
72 0
57 3
0 37
9 104
2 0
0 0
0 2
2 186
260 219
0 67
16 996
638 3
11 295
0 0
368 6
76 42
0 9
0 0
209 21
64 9
0 266
21 71
2 43 417
90 101 107
99 103 277
98 21 29
35 2 156
68 49 716
38 93 183
73 88 908
29 92 956
23 85 224
6 86 720
85 5 481
19 103 306
109 30 565
42 65 358
77 73 97
93 51 919
9 12 664
9 40 360
45 3 259
83 8 265
104 92 259
4 52 791
58 49 514
73 90 786
90 108 483
44 89 318
83 39 289
40 99 718
88 32 147
50 56 865
97 48 581
37 103 457
21 101 414
35 63 831
53 41 213
33 26 274
3 108 842
44 88 525
64 64 277
87 54 671
59 39 425
11 76 369
14 37 509
6 71 57
28 65 719
47 38 589
95 40 288
70 24 125
91 88 808
25 4 947
74 62 802
111 13 631
80 78 573
98 83 139
67 52 466
18 39 33
104 22 508
17 91 529
70 11 461
75 35 151
22 49 109
60 100 619
62 69 781
42 55 360
92 63 182
36 21 515
17 65 926
37 23 606
22 92 781
94 55 373
59 17 403
26 77 996
5 27 168
62 9 776
32 100 226
104 76 235
52 92 741
72 70 678
72 91 519
81 74 422
66 21 979
100 98 989
63 43 785
94 46 233
9 18 876
98 10 123
36 2 410
91 74 540
57 34 742
3 55 826
107 62 237
65 102 785
39 53 86
92 87 567
43 95 936
34 22 725
100 110 798
88 89 728
34 87 469
71 30 152
10 26 147
81 90 855
78 69 973
59 50 962
85 33 3
76 7 616
18 47 736
13 24 103
29 109 744
71 68 174
56 78 516
44 99 43
21 6 93
103 6 153
48 90 100
29 107 808
91 65 453
91 77 738
10 46 905
15 5 693
50 1 924
109 44 538
88 6 317
76 49 345
2 96 185
12 66 122
28 97 231
90 17 307
58 27 75
82 93 353
3 83 642
2 22 735
91 109 187
75 73 618
5 15 691
84 26 407
46 53 378
14 83 42
57 29 147
94 110 787
75 2 189
109 55 161
76 86 97
99 102 439
8 106 337
5 78 888
67 65 249
3 78 222
66 75 543
97 57 761
109 73 272
33 11 996
90 86 821
32 74 61
40 22 411
9 26 405
56 33 457
95 35 853
106 100 545
87 26 958
66 23 793
98 108 691
66 86 384
8 58 55
111 38 25
90 47 630
94 43 978
104 78 444
72 73 419
63 48 344
52 54 410
53 92 749
6 46 926
45 53 684
45 104 459
8 82 291
47 6 64
8 50 377
2 10 449
37 73 173
98 65 955
11 58 768
31 64 605
77 108 284
10 93 568
40 100 512
109 36 872
109 43 453
17 96 458
107 22 725
23 8 914
43 18 463
44 100 413
89 65 496
76 74 765
108 55 242
110 104 908
6 102 441
62 59 283
16 54 850
95 17 188
67 1 1000
45 44 88
79 21 23
109 38 838
10 34 990
62 32 118
90 37 283
101 98 212
44 54 351
2 37 223
25 104 427
59 89 786
80 109 198
55 106 1001
96 56 407
80 6 630
56 36 187
75 25 584
92 10 924
52 11 929
81 87 864
109 34 836
11 55 311
44 50 431
55 34 310
99 2 834
63 109 614
56 13 86
35 105 236
67 45 558
77 66 590
20 64 681
104 74 270
21 6 376
96 1 539
57 99 42
23 102 704
76 46 805
43 80 204
71 87 600
57 105 565
71 65 525
59 57 614
101 19 28
81 55 765
94 111 581
101 74 103
105 91 867
11 74 454
73 34 137
10 31 842
12 101 79
18 100 737
97 89 419
11 58 611
36 92 916
48 22 868
102 16 80
38 78 634
46 40 115
29 101 431
58 1 817
40 18 654
78 55 211
76 65 563
69 100 896
61 88 247
68 78 375
106 56 25
107 101 454
29 70 908
34 16 301
29 107 859
64 74 193
76 90 328
87 99 26
20 48 217
85 57 649
106 51 538
93 98 39
61 16 934
17 49 63
78 18 205
44 81 744
6 46 447
31 21 923
45 92 85
86 65 150
94 59 844
45 93 502
38 42 235
100 110 825
59 17 86
73 2 668
101 7 133
48 37 40
93 22 634
16 108 161
46 90 991
68 75 852
77 1 842
100 41 219
2 100 281
85 61 886
85 103 575
19 39 674
25 73 910
12 29 499
5 74 86
108 83 559
81 100 954
95 29 556
48 31 71
18 56 407
100 29 953
18 47 152
25 12 924
53 76 704
18 21 991
13 17 275
82 97 406
93 21 321
86 9 842
66 27 53
100 67 619
73 26 22
26 50 595
50 102 26
103 60 120
59 72 866
97 94 817
64 17 812
59 102 67
26 108 212
47 97 131
97 110 396
22 24 677
70 74 234
75 65 915
48 12 451
30 49 750
108 53 411
95 111 340
32 25 957
46 72 667
16 57 67
11 78 10
107 89 771
23 52 698
109 41 132
44 70 697
73 67 444
58 102 747
34 74 741
58 9 534
8 24 741
67 87 382
39 23 401
84 46 174
23 43 466
25 87 195
75 100 471
66 46 808
109 20 918
65 18 713
85 25 675
50 92 493
85 71 544
98 96 411
103 59 359
37 84 484
92 47 236
44 54 672
97 51 833
1 56 675
25 29 508
72 19 750
35 44 111
79 30 7
51 73 838
13 50 381
54 31 681
83 74 883
46 59 380
81 59 262
23 83 764
41 95 272
39 18 517
48 38 898
42 88 937
94 41 99
59 94 926
70 65 240
24 51 846
79 73 659
20 95 446
99 76 526
27 3 391
50 50 284
102 32 263
57 14 388
10 72 788
96 31 400
34 106 541
81 14 98
76 33 38
95 21 867
38 99 388
109 37 653
48 27 722
73 84 80
80 34 103
68 70 175
62 103 823
106 73 425
111 89 944
40 13 495
44 102 642
102 100 604
98 36 628
15 49 944
109 17 705
52 85 834
18 35 569
37 29 104
10 80 97
16 8 343
94 103 12
48 93 198
38 79 181
107 35 222
88 84 706
103 76 772
17 93 168
33 70 433
63 20 662
63 36 890
23 70 685
26 59 80
69 37 429
36 32 99
104 9 520
77 52 792
23 68 439
55 41 633
56 44 444
77 106 518
46 70 346
6 95 919
58 53 839
18 29 435
65 21 943
24 97 123
59 60 806
74 55 206
100 51 481
93 16 20
3 61 517
93 66 332
72 64 12
87 23 736
74 28 723
11 51 379
109 50 123
105 13 174
30 1 260
109 34 390
13 36 453
97 69 833
54 29 609
55 56 205
33 19 423
84 29 76
61 26 658
97 71 604
77 100 898
49 98 981
95 51 368
83 37 106
26 31 112
85 85 221
106 59 867
44 83 341
32 32 468
10 69 699
53 87 591
95 24 620
1 59 157
104 30 716
54 108 329
85 22 654
60 16 128
105 59 120
8 31 358
47 93 314
98 34 808
27 17 800
52 17 974
69 10 836
63 4 864
87 88 665
85 88 497
29 22 429
56 29 533
54 17 522
62 3 644
45 81 147
103 74 361
108 31 301
25 35 125
107 10 942
93 94 268
94 12 21
94 8 189
14 2 587
78 64 265
64 49 163
67 93 897
27 30 975
48 54 462
72 102 35
14 83 993
44 65 815
95 99 969
4 2 459
41 20 300
21 84 946
29 91 194
52 6 718
46 53 703
74 65 308
52 79 898
72 11 320
96 46 648
16 49 764
49 30 540
85 50 617
111 20 842
7 71 222
44 57 407
23 71 223
44 11 257
36 24 127
85 60 203
69 76 319
107 65 764
105 38 799
75 38 938
24 44 426
30 28 588
88 102 235
99 34 47
19 10 718
111 94 61
86 52 42
102 99 468
36 92 989
20 55 548
23 19 337
96 48 423
107 24 505
77 63 242
110 22 879
54 22 735
58 48 101
78 90 444
51 14 301
3 34 934
102 108 886
16 34 24
17 29 104
60 106 698
25 104 61
52 98 316
3 97 17
56 63 184
97 55 226
6 57 292
74 99 20
107 4 833
77 72 669
62 20 760
110 96 853
69 37 664
100 91 251
68 35 6
13 72 746
83 19 808
68 92 738
109 87 870
71 104 329
3 55 265
92 53 621
62 62 922
71 51 251
64 59 707
9 71 435
1 95 735
49 51 185
26 100 373
57 1 616
49 3 73
59 36 734
54 97 361
78 56 269
81 61 471
8 10 149
110 11 526
67 59 596
108 25 24
72 82 639
22 19 461
26 18 599
83 13 902
31 90 383
81 60 292
19 8 983
27 6 551
19 13 802
2 9 823
25 21 832
49 43 157
16 68 412
18 91 216
5 62 839
41 83 881
85 101 47
80 17 769
84 87 483
88 29 371
6 53 803
56 42 745
66 57 266
34 74 449
14 20 654
83 60 849
94 86 800
111 54 355
23 78 687
50 55 445
86 1 946
24 56 531
4 62 657
103 95 274
12 49 983
94 73 166
88 55 760
71 54 800
12 17 483
38 67 960
34 93 756
82 5 348
60 60 243
36 51 497
27 63 29
36 97 673
46 14 661
30 84 389
8 36 272
5 15 493
55 48 774
47 70 563
94 18 306
91 106 914
65 21 186
88 56 772
71 102 519
109 20 280
89 80 351
26 25 826
30 79 794
66 14 199
48 48 569
88 28 910
68 33 494
103 9 653
71 21 551
45 18 648
51 47 37
85 72 255
22 42 907
110 49 99
104 96 175
56 13 377
3 22 550
21 13 72
43 25 615
107 69 188
21 60 530
65 33 558
23 106 466
111 104 27
101 37 800
80 34 793
27 88 269
7 108 60
99 40 287
48 87 817
66 48 927
71 2 319
88 24 166
36 23 909
84 64 446
5 85 345
102 111 160
108 58 735
68 45 720
111 33 16
1 39 268
2 50 509
35 27 345
4 62 384
18 35 722
9 91 884
92 22 595
92 71 50
88 27 376
13 27 831
76 79 954
16 21 918
69 107 336
33 111 966
13 69 536
108 77 844
65 109 32
73 89 13
80 65 198
21 18 223
98 34 197
50 50 101
45 7 899
14 91 458
38 103 333
95 40 319
73 104 462
14 66 567
83 34 70
9 106 689
13 92 436
36 83 282
79 16 28
7 82 721
96 8 94
32 102 220
36 5 978
38 18 314
16 41 274
52 102 231
106 3 71
82 91 39
107 58 108
27 64 259
89 49 454
84 21 579
8 108 827
35 34 228
68 102 440
75 42 363
77 36 216
1 6 545
58 1 449
20 79 176
63 109 532
54 22 497
88 29 739
14 4 718
69 71 349
105 87 405
20 104 868
100 45 226
108 103 56
3 63 85
13 67 33
72 9 342
91 96 229
48 110 23
39 8 737
19 53 588
41 72 211
40 1 970
96 108 607
93 51 578
58 64 787
72 76 38
49 107 259
54 44 273
62 82 307
82 100 798
77 82 162
6 62 260
90 46 987
54 79 140
21 26 894
55 38 481
38 27 396
5 80 23
23 31 782
99 53 667
6 19 785
35 76 648
65 54 184
85 107 94
44 68 812
7 63 369
45 100 808
19 105 1002
37 68 677
76 55 862
45 1 550
95 36 246
95 41 269
81 66 575
35 109 91
65 4 602
22 100 198
58 8 433
62 96 280
37 1 692
64 46 168
51 29 517
1 65 347
57 34 642
107 68 541
55 74 637
66 36 58
6 93 899
50 95 534
102 20 742
38 25 188
34 75 357
58 16 894
12 72 981
83 68 709
40 63 238
53 17 936
55 22 960
63 12 660
49 54 360
94 92 621
66 14 640
66 13 660
20 76 652
7 47 483
54 27 947
64 21 995
109 75 117
24 78 801
86 15 322
57 49 371
51 55 464
61 10 467
86 29 725
12 87 581
58 81 869
55 33 280
9 82 868
37 106 178
77 21 797
111 77 114
73 69 664
41 70 803
22 96 421
77 48 849
9 46 793
78 41 840
49 50 925
42 27 355
105 44 141
72 43 640
29 56 821
92 38 323
1 59 803
42 24 262
110 32 885
88 50 263
99 98 742
81 80 787
49 74 196
97 34 994
104 3 195
67 94 262
100 35 362
57 17 218
62 67 760
54 44 504
34 83 429
4 104 754
52 42 300
33 27 215
109 19 962
70 27 849
68 15 382
13 12 625
92 15 130
33 68 389
83 42 537
1 97 200
57 37 729
76 11 616
10 60 794
5 70 136
35 26 612
41 38 374
63 70 34
40 103 121
61 15 600
105 15 858
30 71 31
108 87 664
42 37 397
105 42 126
25 17 758
10 109 356
7 60 135
18 100 853
89 101 714
90 35 793
24 64 193
99 60 563
72 42 117
105 88 812
36 1 848
104 10 604
90 17 701
94 86 620
30 5 98
32 94 318
107 7 181
24 46 765
27 6 333
66 110 26
88 87 331
67 20 209
95 109 680
20 92 478
37 62 721
43 94 7
83 30 543
76 53 708
10 79 516
44 86 9
107 62 16
110 69 291
12 52 540
41 13 895
38 49 559
38 33 243
21 4 736
62 20 228
37 29 985
18 14 415
49 61 385
107 59 36
73 71 969
36 52 587
91 30 506
89 68 821
69 88 200
78 39 173
81 75 205
104 33 924
41 81 408
40 17 986
47 89 512
47 14 720
59 45 85
61 22 324
94 31 147
72 108 742
70 19 869
37 63 689
69 103 210
50 31 795
89 19 86
81 65 266
13 13 285
26 73 347
107 107 396
105 68 813
30 78 176
22 3 114
47 71 744
94 9 800
46 38 965
86 7 556
81 71 509
60 97 680
61 92 183
32 26 920
111 107 412
97 17 510
86 64 839
8 98 452
71 32 36
93 58 748
16 79 11
56 28 553
4 29 401
111 60 347
4 60 482
33 97 24
5 13 12
99 20 300
90 90 737
60 71 406
88 27 218
75 82 809
48 27 874
104 78 455
23 82 714
99 55 177
81 1 603
67 99 788
39 19 826
42 19 383
103 106 12
72 10 219
68 109 387
33 102 695
57 65 412
30 52 596
40 22 810
62 88 185
103 16 522
4 57 559
86 100 689
24 1 272
44 68 915
83 100 311
89 98 158
5 16 287
87 107 72
58 57 817
69 100 875
97 44 629
33 18 186
14 41 760
5 26 159
105 108 604
24 26 549
8 31 56
43 6 652
40 5 937
13 73 48
2 110 808
40 31 597
66 97 424
34 101 209
70 35 985
35 59 148
97 7 754
4 49 750
69 88 943
79 100 218
18 42 391
52 22 722
51 88 899
83 62 190
89 20 859
32 106 864
52 32 63
51 87 93
107 44 319
56 63 611
18 80 489
89 72 581
80 11 772
108 94 821
15 12 884
8 95 913
111 35 104
109 85 860
44 21 832
59 76 952
62 93 971
48 71 636
56 91 951
39 88 279
25 102 884
31 50 748
31 49 664
3 46 736
10 30 62
2 29 584
56 90 867
19 27 301
54 82 604
41 61 728
61 86 157
93 57 451
48 87 823
38 30 981
2 40 719
38 93 353
38 89 491
72 107 972
6 102 21
31 83 464
83 84 119
67 6 868
99 54 621
69 91 831
76 33 356
2 11 376
66 49 193
50 61 423
1 8 403
85 38 730
60 61 736
8 16 951
65 4 471
37 13 311
39 88 204
80 30 560
43 37 962
35 86 625
23 28 495
52 53 230
53 1 499
78 61 865
56 14 71
29 102 643
85 30 559
62 50 536
50 93 923
27 68 562
6 90 422
102 31 520
66 24 21
90 101 395
70 97 154
106 66 621
42 39 976
7 101 221
2 91 433
84 7 801
30 64 745
3 106 667
81 60 997
100 90 469
68 101 679
101 95 151
13 77 843
66 25 602
109 78 691
22 50 717
2 80 653
13 23 344
106 44 665
111 84 818
46 40 311
78 29 270
5 94 983
22 48 7
81 45 578
8 7 265
52 8 275
41 73 732
83 67 153
15 67 907
89 1 388
40 19 449
79 75 710
83 97 143
111 66 967
46 73 316
82 65 636
28 105 21
107 17 136
111 84 327
88 61 59
105 41 712
91 8 84
59 90 365
15 30 508
67 16 201
73 98 510
79 14 85
106 61 971
88 1 831
77 89 127
66 82 872
15 61 333
98 60 140
47 74 351
62 81 543
89 42 624
11 9 572
88 55 116
71 31 758
26 48 403
34 55 787
83 69 709
80 107 172
55 43 372
53 45 921
15 22 484
66 84 46
20 61 625
85 20 356
92 98 913
24 20 354
89 102 739
44 70 501
110 66 4
27 7 752
76 73 944
55 28 439
95 99 321
78 13 909
84 105 383
86 69 516
83 47 881
90 31 103
92 30 25
77 108 698
106 73 958
97 16 484
2 51 492
26 69 448
63 42 755
33 68 166
16 40 169
49 70 765
92 50 475
89 67 373
33 61 25
102 98 615
87 41 834
111 66 306
89 69 734
59 43 382
98 58 249
13 106 774
11 27 456
37 56 648
1 89 747
37 20 46
30 107 981
14 47 871
66 24 974
49 24 669
40 10 823
70 23 666
Output for test 8
401
Input for test 9
130 1500
1 0
15 109
0 2
391 0
44 12
68 199
785 25
0 79
4 3
0 15
0 0
162 565
0 0
1 0
2 0
354 0
59 0
954 341
0 1
119 0
0 0
0 110
209 0
0 27
1 20
9 0
0 89
5 0
326 0
0 55
42 336
43 15
259 524
0 19
2 452
0 137
172 0
0 231
1000 49
3 6
0 60
15 73
6 0
0 216
0 900
0 7
165 691
0 0
0 338
0 0
42 0
599 126
64 7
0 3
97 65
6 0
309 8
81 0
224 408
0 52
342 309
0 2
1 4
0 370
6 23
514 16
0 3
14 124
75 21
102 0
17 85
32 0
5 323
0 0
100 43
2 5
970 791
0 13
23 0
173 6
30 149
131 0
489 8
0 0
17 373
0 58
0 0
628 0
4 2
212 26
3 0
38 0
0 48
1000 115
9 237
0 0
0 927
20 0
0 0
318 0
0 25
121 0
1 84
6 0
375 0
12 7
9 117
0 0
29 3
581 1
353 165
170 0
8 0
0 0
11 1000
47 226
0 422
49 364
0 0
8 664
0 10
2 0
1 7
107 11
0 0
7 0
0 2
13 245
1 3
42 54
83 44 965
11 60 371
66 21 135
2 66 517
41 97 902
87 18 775
118 109 223
18 1 207
52 42 654
30 111 455
82 63 966
52 73 699
84 10 361
71 12 443
80 54 728
34 12 136
56 130 45
41 19 253
34 72 944
8 102 297
31 55 497
99 107 739
97 60 453
117 130 24
74 81 965
127 115 418
70 40 342
122 82 413
45 115 541
11 122 364
87 22 475
95 121 540
45 89 278
7 76 117
111 21 629
9 18 359
48 89 785
88 82 127
18 127 588
19 9 173
122 96 684
21 60 438
26 107 130
92 115 118
30 95 843
49 103 734
51 22 923
95 109 453
91 128 574
71 17 932
44 10 821
39 32 438
26 59 167
102 22 515
124 52 799
37 100 334
97 20 238
119 117 500
91 77 880
62 19 918
42 62 326
117 103 225
124 128 208
106 101 846
73 97 957
6 3 168
41 102 539
100 90 501
10 52 177
45 114 153
100 27 303
34 14 604
129 9 196
22 114 206
68 58 748
36 63 664
102 106 389
60 75 490
6 84 121
26 130 503
68 101 268
40 4 234
115 2 189
60 25 297
108 95 423
119 130 10
7 103 95
126 35 560
75 40 606
77 68 112
64 5 343
75 46 624
104 33 879
8 92 611
28 69 717
108 60 153
120 66 732
109 62 47
44 8 243
65 84 494
86 17 303
79 93 970
75 66 447
75 76 929
102 105 971
92 82 21
82 73 742
48 51 520
50 97 841
91 31 880
74 118 785
61 66 821
95 13 275
32 87 983
62 58 238
32 20 812
62 103 66
29 22 738
59 71 91
96 33 727
90 106 107
98 36 277
72 3 504
112 36 666
97 99 75
59 130 92
102 63 573
87 93 247
125 21 510
1 118 602
38 77 15
62 46 400
23 120 78
127 101 492
61 70 217
52 128 925
63 101 986
49 59 141
59 56 553
8 56 766
120 93 655
80 26 4
77 49 629
76 47 508
110 107 621
114 28 850
119 92 709
57 13 261
90 71 889
13 78 34
55 68 772
46 19 854
85 95 612
112 40 490
112 21 208
51 6 134
117 124 413
27 53 265
124 14 637
17 26 389
96 82 416
10 130 435
81 86 843
68 69 67
105 51 596
116 101 348
28 90 893
32 116 919
46 111 563
4 130 376
38 97 473
10 108 154
1 58 125
85 127 660
81 101 969
98 88 21
119 116 311
7 17 602
77 65 800
32 68 142
12 105 661
75 117 478
8 117 795
25 73 575
113 25 951
123 123 482
104 113 1001
43 119 216
102 67 445
12 98 969
50 109 878
57 53 235
42 62 471
84 89 779
124 71 223
5 66 398
104 39 352
59 83 624
31 55 834
69 66 190
45 115 769
129 44 337
69 85 101
127 38 833
127 31 893
24 38 543
43 11 210
46 69 498
37 102 711
96 40 645
122 86 792
128 84 458
57 24 471
49 20 975
129 17 542
21 42 825
111 85 302
106 130 324
56 39 752
60 4 733
129 126 585
55 123 830
23 51 406
78 101 779
39 101 431
31 124 877
62 104 568
105 81 854
85 7 356
37 66 904
29 67 389
109 121 874
14 15 749
70 92 111
20 1 792
116 33 384
124 97 429
85 71 782
50 27 995
51 64 71
60 94 708
61 74 344
59 87 786
108 29 503
127 48 466
120 34 568
107 27 983
68 111 9
110 33 671
30 83 368
16 12 533
69 75 748
115 3 842
47 110 568
70 108 56
98 100 86
28 76 179
56 15 605
24 125 567
21 24 419
83 41 414
111 110 937
80 96 213
7 12 988
93 83 369
98 50 499
4 77 758
68 4 925
112 30 779
61 50 313
94 5 299
10 115 89
1 66 378
126 74 653
104 38 766
60 5 829
115 8 758
119 75 887
6 59 220
18 121 779
54 84 281
1 95 255
58 95 151
81 92 456
114 68 791
100 127 859
8 114 445
122 102 23
111 109 249
128 127 689
68 52 111
10 52 926
70 112 421
65 62 157
3 45 121
111 17 678
94 24 324
84 17 167
22 127 481
21 126 689
9 63 455
83 74 427
121 13 690
127 77 621
95 80 574
130 60 609
32 23 607
48 108 972
36 2 588
5 24 376
99 32 762
113 116 374
53 106 170
103 105 592
85 69 799
113 69 930
27 102 841
96 21 976
53 59 705
6 63 628
85 31 431
99 16 223
56 68 278
27 42 16
75 126 590
74 108 470
3 6 628
86 103 441
20 25 722
86 31 652
44 117 214
36 85 916
14 12 831
97 41 350
26 115 92
23 59 979
91 63 619
129 20 614
60 39 287
49 124 221
102 40 143
56 75 460
26 90 246
64 56 318
15 83 320
91 108 344
17 68 374
79 68 896
115 130 235
43 48 94
4 22 449
83 79 730
116 104 157
31 37 356
118 53 694
62 14 756
63 30 363
129 110 492
81 94 230
74 9 999
63 14 448
90 96 141
64 83 639
130 114 123
121 103 291
66 36 234
119 101 927
108 99 338
37 51 80
95 127 435
71 59 623
69 20 488
18 86 135
68 85 808
26 75 173
39 12 547
63 130 625
121 108 425
28 16 545
30 111 865
43 53 533
70 123 291
63 10 923
10 77 878
72 105 862
106 13 918
48 78 799
92 68 219
104 97 18
39 128 423
101 40 135
90 110 247
100 44 250
67 53 779
116 124 308
111 101 124
119 21 106
125 112 235
110 88 494
113 128 960
95 98 418
130 59 839
29 28 710
67 94 163
52 81 355
15 63 160
119 52 771
43 46 161
35 28 104
124 12 791
81 106 788
80 107 978
57 7 296
78 74 16
22 127 11
92 12 142
130 2 26
60 46 757
103 82 255
102 76 534
99 28 15
66 107 182
90 36 281
13 113 557
31 6 492
2 97 39
36 98 22
122 27 545
124 130 840
25 103 752
67 73 589
87 9 118
85 100 177
91 114 472
41 16 516
119 18 661
80 55 418
42 46 905
51 40 634
12 66 705
50 3 259
116 91 81
32 47 851
111 7 862
46 49 775
114 39 951
21 118 880
24 31 234
57 84 119
89 95 140
95 17 476
45 4 490
6 35 10
65 17 18
110 62 716
38 45 595
115 66 393
118 91 483
36 17 53
124 105 646
19 69 363
46 115 789
35 120 392
70 57 346
115 36 472
79 75 283
80 61 789
72 48 54
92 83 36
68 78 662
8 96 986
96 13 616
55 49 631
50 120 582
61 105 330
3 53 295
121 4 481
45 75 61
58 37 618
88 106 973
91 113 262
37 80 960
97 6 552
18 55 103
126 117 922
10 121 76
99 111 509
117 25 962
55 83 269
77 40 775
46 2 532
115 40 196
67 6 905
67 24 400
56 21 376
20 30 302
38 128 162
59 117 742
25 43 447
29 119 661
8 36 340
101 21 523
13 87 473
60 25 168
35 80 893
124 101 623
75 8 355
7 67 862
91 91 260
1 122 812
78 129 840
30 100 308
20 114 468
18 46 926
38 80 430
81 74 251
23 20 112
94 26 869
22 118 187
121 118 980
81 67 371
76 97 889
91 116 80
66 3 494
65 43 879
13 123 608
62 17 333
119 110 213
115 1 338
72 124 506
20 74 373
99 19 630
16 111 148
47 46 693
123 110 488
21 122 70
121 56 764
111 44 570
129 30 51
2 102 762
124 123 215
53 91 248
78 107 518
91 25 138
106 20 735
35 40 736
88 30 389
27 13 804
75 11 199
124 14 759
38 7 812
25 62 374
30 9 37
15 99 173
49 76 329
62 112 678
69 69 177
2 95 509
109 42 531
117 35 931
96 75 564
69 99 152
3 129 323
45 15 222
112 64 242
67 127 870
64 67 523
90 69 612
128 49 758
48 35 659
109 2 426
48 70 270
49 73 788
60 117 848
41 100 233
98 39 378
11 102 664
120 61 831
67 60 31
56 107 109
81 87 525
50 4 736
117 54 465
53 115 99
3 26 808
18 125 917
29 5 807
109 126 948
127 65 550
65 122 789
37 74 297
10 123 283
55 109 249
43 31 514
18 35 651
95 52 546
79 83 122
35 63 549
54 60 786
3 124 942
57 33 673
70 44 106
88 98 860
29 11 369
87 30 181
42 124 176
124 75 79
80 111 553
35 34 426
55 36 77
67 95 612
23 36 554
100 123 988
28 21 375
117 110 517
112 23 219
28 16 394
29 97 848
94 2 878
88 58 384
77 124 151
99 16 475
36 118 692
68 15 344
115 1 647
63 112 248
4 12 690
22 42 446
19 5 764
50 94 77
119 40 324
23 10 880
93 45 847
26 115 84
110 101 309
45 33 51
5 38 485
110 59 686
51 78 909
128 129 873
1 117 708
128 12 319
15 106 259
16 1 215
32 113 561
53 29 811
55 33 885
70 12 175
126 65 173
58 62 812
83 64 121
19 62 599
97 76 72
90 93 229
70 127 412
19 49 616
3 103 734
25 42 159
108 39 332
9 96 368
39 48 341
58 66 925
87 35 348
96 124 455
105 65 327
98 83 975
121 88 743
47 114 817
119 91 880
124 102 838
63 10 913
65 67 162
2 26 198
14 123 684
120 97 129
93 66 443
113 56 788
110 105 45
17 93 738
95 86 391
7 18 164
97 84 823
124 85 22
55 100 829
111 90 471
101 52 709
46 36 804
80 15 191
98 34 675
78 128 937
29 4 343
121 100 582
22 93 578
80 17 674
130 129 324
16 100 555
99 17 636
108 97 363
90 64 848
37 11 671
67 39 20
118 31 453
125 53 835
87 2 7
20 2 356
44 17 6
119 118 695
99 95 264
94 56 50
124 92 845
21 30 685
54 20 435
56 14 915
22 102 497
7 123 359
121 36 672
75 24 790
46 125 867
115 90 443
117 84 191
129 106 44
53 31 344
6 88 725
12 110 58
20 118 72
29 110 734
57 57 302
73 102 407
54 89 411
92 75 511
93 76 726
126 128 73
48 5 4
116 17 701
27 36 522
60 67 172
129 123 301
96 65 307
54 120 451
104 83 131
109 46 485
90 43 900
103 93 160
73 80 824
25 106 92
94 35 320
14 36 176
121 1 800
71 56 704
109 32 386
91 10 328
21 99 925
80 71 518
11 16 532
93 40 671
80 3 356
3 18 22
50 8 969
33 78 601
6 56 327
64 19 710
36 39 769
53 118 928
32 130 890
90 94 355
125 43 546
65 47 928
41 98 208
22 1 985
58 8 765
125 71 970
71 109 140
118 31 468
108 63 167
112 24 59
26 19 232
73 85 357
8 127 253
83 18 71
105 75 863
54 69 12
22 12 493
29 129 283
24 106 193
22 90 105
113 115 39
117 59 699
40 67 753
60 21 519
80 125 597
109 48 13
81 71 772
31 100 343
14 125 3
58 16 641
126 130 960
82 117 856
122 28 254
31 87 712
87 38 212
87 18 868
28 99 648
110 1 688
61 16 807
121 74 521
8 69 238
13 21 188
74 14 76
76 44 153
97 2 191
113 89 698
50 118 35
55 98 45
32 30 8
130 20 113
118 29 816
103 43 505
78 118 227
78 63 380
38 32 186
33 14 237
45 65 897
30 119 935
15 20 394
15 22 275
91 9 216
103 113 174
7 60 58
56 9 415
19 46 660
114 80 1001
38 124 656
82 25 270
93 39 880
7 56 940
70 18 23
33 122 13
38 130 95
31 55 46
88 76 664
46 59 841
19 98 920
58 52 285
85 16 980
2 23 360
74 92 537
24 125 324
86 32 927
79 64 866
82 23 223
2 68 828
129 88 916
124 15 85
13 102 916
72 105 504
57 49 416
60 72 569
55 30 135
50 110 169
100 64 82
95 65 885
20 66 574
43 59 804
118 73 840
79 14 561
64 70 256
13 2 944
85 58 987
61 107 126
101 77 108
35 41 241
36 61 715
129 105 800
107 92 130
55 43 682
108 108 166
81 120 467
128 75 908
71 7 117
126 107 254
114 13 890
39 51 202
28 49 104
76 25 678
67 82 542
72 61 196
17 14 405
94 11 385
99 83 971
80 79 977
9 64 836
110 104 780
12 2 30
17 77 91
118 15 447
1 87 658
124 105 681
108 68 104
38 38 264
104 119 636
19 129 326
77 109 572
56 120 85
84 8 16
9 128 844
16 130 601
86 125 97
37 102 501
130 11 70
46 115 920
41 3 300
100 79 99
5 7 219
40 90 410
22 100 699
20 118 626
106 73 736
36 110 782
35 111 796
74 26 96
102 69 10
130 38 75
6 42 715
5 84 311
11 105 303
17 126 782
22 103 109
21 8 962
124 44 793
108 118 863
77 91 511
51 90 59
104 97 428
34 101 702
54 111 245
44 127 251
22 20 318
73 41 540
103 34 119
116 13 474
26 92 171
4 12 211
19 117 42
80 21 528
92 76 428
82 121 791
67 13 239
26 85 859
124 60 429
6 47 94
6 74 949
97 77 1000
16 97 23
32 47 380
19 10 82
119 94 77
86 32 498
72 58 802
100 53 948
33 58 727
109 64 55
18 32 88
69 47 586
108 80 975
39 101 601
43 89 762
38 44 707
47 117 399
13 88 78
39 121 860
114 101 218
1 121 23
95 61 484
27 38 992
7 76 74
128 120 154
83 30 372
71 78 318
116 92 846
83 1 384
108 116 726
70 116 818
63 82 658
103 110 618
94 116 427
55 116 164
106 70 256
71 10 845
27 125 82
68 77 914
103 57 416
108 128 641
104 61 378
31 35 860
128 128 409
39 54 625
72 31 322
6 104 501
16 130 910
119 67 624
92 39 852
52 18 810
127 123 518
24 24 160
31 21 374
25 61 583
4 5 586
54 10 456
111 27 861
34 15 940
35 108 778
93 29 98
20 26 716
9 51 638
30 81 481
50 107 373
125 112 476
100 35 42
49 15 913
128 50 170
14 85 426
69 49 96
12 70 464
78 78 611
38 109 42
21 28 514
66 24 651
115 125 122
45 43 779
4 43 823
110 56 285
63 124 661
46 8 759
57 87 150
118 126 287
129 16 245
119 81 604
89 67 947
95 114 783
117 117 916
61 98 338
89 30 825
37 78 768
54 6 937
18 123 263
92 121 929
63 112 656
59 72 919
50 36 755
85 24 428
32 87 457
34 45 264
31 82 296
36 5 365
126 25 80
84 116 832
58 49 484
114 109 37
108 28 258
84 112 275
50 13 909
111 48 497
74 79 641
118 114 154
35 111 831
76 65 955
110 122 120
124 107 280
80 84 379
72 39 548
90 88 350
64 71 174
85 16 492
56 4 420
34 40 245
38 116 875
26 97 589
65 92 392
83 41 848
129 115 62
26 76 162
69 12 252
28 96 592
67 23 827
89 59 672
92 96 852
30 123 899
90 60 295
125 12 778
116 10 549
16 37 935
5 108 842
66 5 413
10 74 990
92 34 725
81 127 445
59 27 102
1 118 815
38 112 916
114 100 77
48 115 549
60 121 677
80 56 986
70 67 613
84 28 326
26 110 719
65 38 666
99 40 104
62 78 71
39 63 412
27 113 243
53 42 667
57 123 989
67 62 94
22 17 511
8 42 260
123 109 840
4 79 849
2 11 229
114 51 458
64 79 730
1 1 682
57 59 153
41 127 258
91 18 631
40 28 348
97 22 201
66 28 939
72 31 78
27 14 530
46 80 722
48 82 200
90 10 342
125 50 133
94 12 829
79 52 459
109 20 738
116 85 329
73 28 38
42 54 229
61 102 14
30 19 283
129 108 756
31 103 716
58 68 957
106 18 989
53 126 772
21 113 791
17 55 246
43 98 713
84 30 649
77 59 780
20 60 490
105 90 577
112 17 1001
130 124 390
69 46 737
27 67 593
72 83 245
15 125 122
11 80 749
110 26 199
99 48 19
65 22 198
6 3 218
13 2 256
38 72 770
58 101 197
62 44 865
121 58 809
20 70 255
78 51 215
64 19 320
110 84 677
117 89 351
10 101 295
29 8 849
94 67 780
98 129 230
55 121 794
7 10 533
39 89 743
99 23 903
75 4 854
73 120 817
76 1 847
84 30 979
31 125 597
81 92 345
44 16 115
64 23 26
26 63 527
39 31 816
70 106 260
56 50 703
130 127 64
46 80 244
102 113 715
97 63 319
89 108 271
72 43 376
67 69 240
20 109 723
127 48 845
109 103 282
82 104 382
55 21 140
58 123 700
54 91 894
14 49 246
118 121 955
117 59 847
47 78 367
10 76 415
81 56 842
70 7 166
60 63 879
129 120 662
50 46 756
33 59 856
125 48 74
1 35 786
76 81 164
128 92 373
98 43 670
43 114 755
92 45 393
31 43 826
94 92 117
119 124 232
60 120 791
126 121 518
119 68 4
62 65 617
79 34 198
24 77 732
106 40 598
121 72 932
126 37 137
47 25 398
27 86 664
55 81 533
116 72 555
130 3 742
108 81 859
129 106 392
6 82 210
58 72 189
22 69 340
77 116 416
128 12 622
41 66 678
75 54 70
47 53 961
83 30 73
22 31 426
42 36 771
100 93 204
100 114 548
5 63 268
65 60 243
82 100 317
49 45 4
88 93 307
130 45 192
123 68 853
94 109 373
17 81 51
12 50 463
78 54 449
130 120 51
66 71 282
70 122 674
126 79 130
105 80 742
118 75 366
28 40 743
108 56 434
19 70 624
47 19 355
7 18 40
26 86 300
17 25 512
56 20 393
55 127 253
98 114 515
81 13 249
44 121 928
85 11 105
49 59 974
66 65 152
75 92 232
27 111 527
99 36 743
120 91 184
92 60 392
10 10 865
97 53 30
109 9 230
61 59 982
30 127 380
21 73 176
95 99 649
67 68 119
59 59 65
48 22 577
23 33 666
10 129 778
119 107 990
110 39 981
29 71 749
12 91 685
90 58 438
17 124 868
111 54 367
37 102 537
20 126 538
17 7 320
67 127 160
125 106 809
113 4 237
98 17 947
25 106 168
50 124 127
17 104 860
41 10 254
89 32 697
38 48 52
116 114 698
42 110 566
8 95 931
43 62 226
40 86 272
94 7 419
13 25 433
116 66 78
60 26 930
1 63 3
78 50 72
21 93 478
69 101 197
124 15 681
63 54 964
112 19 481
24 33 98
39 19 882
68 78 369
128 81 94
108 28 79
73 51 480
19 119 753
60 115 835
31 49 319
90 30 74
27 53 224
118 94 626
17 31 884
70 29 44
56 8 154
96 82 613
96 102 633
70 31 494
56 64 418
97 25 26
30 53 88
123 40 680
107 56 935
38 126 76
51 53 806
93 20 195
56 115 366
7 56 217
74 111 780
59 79 15
74 108 49
14 103 681
48 79 142
111 116 800
76 38 97
50 2 461
103 57 371
130 65 927
59 8 963
51 69 793
69 14 194
7 29 33
118 77 935
25 59 133
61 7 20
20 56 99
128 29 981
92 30 647
112 88 294
115 10 983
68 78 91
128 86 55
31 73 255
13 100 921
113 30 830
119 51 136
129 48 383
66 10 231
67 121 302
77 107 21
28 44 400
120 44 189
114 76 714
53 88 819
52 70 300
57 61 251
117 59 132
78 124 309
69 60 60
18 9 993
107 36 249
16 27 725
9 10 98
77 64 653
114 115 872
55 43 422
46 30 454
84 107 594
2 45 488
44 64 129
62 43 499
124 58 334
101 66 390
21 13 272
31 128 545
112 54 742
125 99 994
66 55 683
1 56 741
130 101 468
6 32 233
50 26 435
117 126 964
68 19 180
83 51 954
82 32 583
123 26 317
66 93 987
116 94 901
83 95 468
116 100 678
58 19 130
62 8 897
1 77 74
82 29 312
34 110 832
38 105 405
15 42 482
43 29 655
129 114 760
56 99 924
13 28 995
129 89 306
111 89 595
112 42 483
34 76 162
118 115 73
98 129 209
42 44 250
81 44 991
82 99 544
56 114 492
51 112 619
55 94 240
6 76 178
115 111 90
77 98 555
14 65 591
123 108 480
1 58 823
124 11 86
85 69 296
74 119 229
21 44 483
56 51 776
5 37 123
29 113 353
38 128 221
45 121 557
97 123 15
62 119 54
125 73 245
42 16 635
74 36 823
67 94 458
10 98 20
60 129 316
78 36 769
35 82 288
97 50 418
90 111 203
94 105 831
36 18 143
99 93 461
74 30 668
104 39 941
Output for test 9
329
Input for test 10
155 1500
40 0
0 139
326 0
2 1
149 0
1 15
0 53
306 38
435 0
0 0
19 0
0 0
33 346
502 0
53 1
0 120
502 0
0 6
0 2
52 838
0 0
0 451
1 25
0 0
1 545
10 84
333 0
6 0
0 6
1 0
208 2
30 0
145 0
14 1
212 1
84 0
0 2
35 18
968 0
2 323
0 0
0 0
239 0
10 0
4 210
270 73
5 74
1 132
0 311
0 1
0 16
9 6
211 100
0 35
98 3
0 0
0 0
1 0
11 0
1000 10
0 0
14 4
0 1
27 0
0 5
0 547
190 17
53 0
0 0
0 0
0 0
0 500
0 0
0 50
493 0
0 102
1 0
0 0
0 2
0 0
32 0
23 90
0 0
255 10
0 70
5 0
0 0
256 398
0 87
9 0
137 0
195 153
82 0
0 2
0 4
0 0
0 180
1 27
3 0
0 0
12 184
0 1
16 88
0 6
19 0
1 0
0 9
0 0
0 0
11 158
158 1
4 0
5 7
0 7
0 12
1 0
1 1
45 5
144 15
30 9
44 0
76 0
41 0
0 33
95 0
149 85
1 201
0 4
0 0
0 0
33 127
87 0
14 431
0 47
367 68
3 19
1 0
0 0
82 0
0 426
0 0
480 211
0 0
0 1000
0 0
0 32
7 0
304 0
0 0
0 0
76 0
0 0
1 987
0 0
0 2
33 143 686499766
47 33 18717802
112 99 816483552
144 91 581573613
18 70 576907016
115 56 149542987
28 40 82276808
127 40 616954283
2 26 257919586
65 11 456117231
144 44 258041194
150 57 28579149
52 13 89449933
70 124 821389171
116 108 966974137
36 34 770300523
57 62 82193308
20 33 79071575
117 1 154539181
133 66 72153801
8 54 420836851
147 15 64141096
130 33 795642728
57 102 86054722
74 30 351163010
127 65 714295878
81 89 610428
74 108 837786104
73 36 472348339
64 14 495932829
98 143 532552729
110 101 106834555
23 75 46847904
103 131 183461682
119 49 112634852
54 143 868109024
55 68 804458616
85 108 813312231
114 147 173492300
21 55 304787411
116 119 501441544
76 73 212139848
50 62 274813268
57 132 778909612
133 62 222073678
82 115 909407203
30 136 125595212
99 65 909666457
55 23 560111421
46 11 850175002
50 93 690137751
41 13 677092997
99 29 522662506
76 86 36874360
29 63 115135076
153 111 122993017
108 141 598483334
131 51 732860409
72 105 25778496
5 150 111454932
146 44 957044617
63 51 138260586
53 116 718772838
71 37 774202107
65 65 488007949
120 62 605918411
101 137 201073948
95 112 887284973
121 150 168506819
137 154 541971910
129 145 798077205
59 19 628908200
89 38 70344018
26 108 382808323
15 139 197724956
66 70 546519391
40 15 367371659
31 77 595228770
7 42 168530010
121 145 104221393
8 119 619380476
93 144 80400637
41 77 149985271
105 70 188923633
16 84 57829358
147 117 857447918
152 1 210769355
137 153 863758524
46 5 592436142
104 92 231932501
127 99 879312930
140 36 182265150
16 44 250272668
84 148 7139754
72 130 683903106
11 122 164248183
19 85 496540512
130 33 263144074
8 78 984437037
82 148 681440446
112 87 72382689
106 71 764692767
21 86 254180584
13 136 758671682
74 53 513488611
31 63 701966726
103 48 708752167
143 144 91860548
25 151 255872435
66 77 207444590
43 1 50796279
85 73 405305855
129 93 189500705
62 106 891493702
141 24 200205503
7 21 673464192
149 124 668714711
32 111 396724290
136 135 721249328
96 12 87240196
15 21 521593712
54 105 932395637
129 45 163779269
102 106 789757402
55 92 493725414
27 65 768938207
28 26 794029318
76 57 79924610
79 4 508473875
78 66 107274456
121 81 543377197
8 101 727291537
123 74 261836993
20 142 386804547
144 8 698992633
136 34 550016611
116 61 465582480
64 103 345086362
122 149 913481999
93 38 455414654
108 3 163939317
110 11 899204062
28 100 919028972
146 119 412912627
92 74 96088004
63 54 345017081
98 137 671290802
126 45 405492024
55 12 929955437
109 71 9090674
41 146 158197569
53 100 280159869
10 95 778595279
41 85 22314500
25 143 596039253
138 50 36655258
8 114 908065041
28 84 61845704
150 105 358498699
77 26 159012127
41 66 556270842
130 86 931778792
74 95 850954264
84 102 399373523
57 93 140097594
70 76 419599781
137 50 626023445
151 44 415595020
88 5 766494064
125 48 797234005
111 56 610710170
53 30 547118353
62 71 343789365
10 154 567232849
9 23 821005388
150 92 848675655
30 40 185904687
146 36 489593684
35 90 827102817
150 60 157160354
136 137 107562684
154 1 203409934
69 63 548601246
78 39 583600046
1 15 506977311
17 9 914770170
74 39 505502029
148 29 187235803
111 63 198073675
78 24 543995015
92 4 222138699
7 124 950644570
73 37 351934522
54 82 86314616
155 82 553156250
91 65 906942369
85 106 405399504
118 65 483902897
154 20 748691522
2 64 628127591
31 1 919442985
8 129 85862100
18 46 821984814
25 66 162243592
70 65 821352808
96 122 310960952
8 18 465354076
81 136 661080823
148 134 49603025
90 102 267375294
55 99 485943338
23 106 636609113
82 90 113426508
145 114 98089963
133 150 364843478
48 90 258791114
150 65 694700918
13 112 839943065
96 71 881751235
11 5 32584455
22 26 807660661
122 16 296020256
73 97 257659606
36 53 235157188
64 31 947920811
90 45 168525635
116 39 422619744
127 19 144375473
84 81 979564719
20 91 367522107
56 79 731339546
3 45 33620329
54 84 155190874
40 86 756162745
74 116 27552365
102 51 585676860
64 133 594011409
58 104 517907965
129 155 842186623
116 19 630835760
108 74 784323866
125 76 979238231
124 97 514056118
64 136 487814431
24 21 189247089
47 122 792549364
82 153 409026599
122 22 895248712
25 150 767414392
130 111 907272751
16 30 361793596
103 154 747989385
46 89 390653202
72 119 533055053
151 143 248478876
36 1 484843356
125 82 248800880
37 15 772322987
142 6 52299378
123 136 406422374
90 118 687823629
130 32 818486643
57 77 655771018
81 116 354865503
19 111 495672117
10 146 120128576
123 83 447004934
45 119 275344033
143 72 932405632
48 40 127278060
62 129 285761395
73 70 397210934
81 126 102733058
23 18 725735679
50 36 782806059
64 46 463189162
78 135 383173624
141 147 951783921
31 101 916782992
114 148 59970580
111 22 97971234
103 94 583222504
94 19 925581923
129 8 530088046
123 57 915406323
7 87 358788461
37 132 330688213
148 84 94291811
2 114 878756835
116 39 132060173
80 149 55588517
140 64 175292248
113 2 147784759
57 97 981352148
108 32 707115542
39 38 630098856
137 74 694169937
26 34 536977675
29 35 81346774
10 150 612197944
105 42 742418793
67 26 124673270
121 138 598619426
6 7 472021750
87 81 294355193
3 119 672165089
5 67 97413429
106 92 748238155
135 120 795842098
89 96 980747523
82 46 201051759
36 79 702207565
52 11 919951672
4 17 441734152
86 103 783253448
10 72 888688713
127 43 131213760
8 148 460222519
43 94 175038232
146 150 154415611
56 76 1636896
128 78 934159606
71 97 979790216
151 100 110052759
16 152 115651178
149 129 84991049
57 100 928747218
31 74 736767132
63 117 679121662
27 74 837155455
54 96 837451809
125 69 260556267
87 139 216752496
59 101 142786674
47 116 334419824
104 109 100392490
77 10 112867638
59 7 292997970
1 36 50889788
37 30 534900271
33 83 225773965
105 52 662690230
100 105 400370860
2 8 6248198
126 21 98312873
92 91 297945083
30 134 508218893
35 38 507828734
114 5 756995000
120 8 621399878
45 41 888552172
66 145 398215529
121 56 260806032
5 25 294240649
143 117 256052808
87 20 261891564
138 50 396745839
133 51 427489603
100 9 105275339
136 129 566059301
13 18 42674456
127 83 5665806
105 16 82492174
154 20 946740650
22 7 769970736
66 93 695954052
46 43 15727044
4 142 637121668
121 86 881908723
87 67 800975874
28 46 576704062
9 140 787382331
102 56 757569061
62 54 887632986
46 75 21949055
80 108 582570266
12 153 719955931
82 123 589805613
81 88 876204524
55 141 188661891
2 14 943541912
88 144 86944542
69 90 621403549
65 151 203402476
80 8 745887689
102 55 533684825
28 66 814295847
151 148 13239423
105 40 176710873
111 94 776888092
29 62 865439928
114 149 661297313
150 63 170123928
119 94 107505143
75 19 610825560
105 120 935665463
88 147 968622857
34 109 549164059
103 25 314408613
70 135 160650594
23 130 536346547
78 55 223231965
155 49 641782374
133 12 578339663
73 86 744276091
21 3 175926066
145 90 265211650
25 90 922732728
18 37 238291936
18 74 426221400
110 63 513309762
76 141 104967081
35 107 450006901
23 84 22346996
71 123 820354163
16 111 633076395
46 100 979808917
35 91 527361803
131 76 274584875
97 93 221928278
9 14 160665458
50 89 603717014
146 123 593670291
103 112 933742412
71 28 745823872
58 43 464479504
81 55 216018726
4 56 616545066
139 32 420254013
1 95 750905978
57 70 607278305
143 86 701974019
92 44 96351834
114 146 241545922
31 28 906539898
71 85 688124082
32 10 571576336
93 136 822106186
57 119 391219188
95 86 326559076
71 110 68732602
60 97 131047403
104 1 265951232
116 81 290353545
85 112 50340612
47 149 190005869
19 25 356811063
45 85 368691863
93 141 929266548
18 80 165634220
125 117 904041399
147 21 524572450
99 92 264037581
94 52 892363561
46 103 33935904
58 150 229542800
121 13 148695185
39 24 640504979
92 116 526548680
76 100 860173495
112 37 421058232
135 28 802091593
33 126 557761826
120 31 770031162
99 76 694830875
34 100 76827615
117 65 413497259
36 71 305188973
7 7 397748216
84 49 96779528
86 127 714452385
50 73 981367536
1 106 852311658
10 70 769492460
70 13 37648839
111 46 325827124
80 129 29064615
28 131 137265569
154 104 209765804
53 33 13958618
18 118 524830026
19 12 675194258
47 134 813363035
12 110 217759292
129 25 590098386
133 102 169347652
81 27 803755607
93 54 670790265
143 20 587213083
44 72 727053411
82 56 964870098
125 74 559848126
86 120 490335564
118 98 152220990
65 38 315533439
145 15 513230538
83 62 645879175
148 121 141361960
1 108 923573583
113 118 433422567
101 45 105816042
52 136 126428462
137 33 314754113
12 151 890007209
151 27 121677233
127 138 18635945
82 65 97354423
30 25 667473272
153 147 247548095
141 104 666050412
11 50 141970274
92 68 818843423
90 16 415024423
20 27 905745311
13 145 185021003
44 83 4818886
55 9 181967283
128 5 358348553
11 2 395396914
90 109 527806120
132 120 320756334
30 23 915374130
64 79 371504657
130 98 517611083
3 111 344041146
24 154 166326162
60 53 497694544
128 147 12798296
32 124 295446493
83 59 650502752
82 35 173257787
97 65 764491961
24 95 403147963
122 69 565848907
59 38 980728751
106 61 431332878
48 87 98166233
152 27 887935036
106 25 511272864
28 107 25079610
58 33 904757481
53 96 335437057
3 120 121572160
65 53 149409282
37 78 867854892
118 151 947539539
132 43 569538586
43 39 901429715
67 111 963429626
60 138 341579187
111 41 196777714
131 60 40425493
92 62 611635929
82 127 134427905
17 8 288281504
79 92 79106022
45 68 25742699
65 77 273366751
111 111 25420428
149 15 34184817
138 93 317065224
126 68 694800109
55 126 770008183
37 52 945835285
105 36 802515673
62 114 968258770
136 125 79428885
97 35 838510493
63 112 190986411
140 72 619352426
45 21 810556296
144 147 859999455
115 13 750599632
25 50 780185464
28 121 745646906
38 149 705482803
106 129 269100843
54 70 6037487
46 132 8366405
25 117 710739292
108 128 483508163
128 116 685319734
60 75 194726247
85 66 785232631
6 93 267522417
84 97 91746109
120 15 160749002
92 68 324013068
66 113 221807614
118 105 336387661
86 57 68840581
42 30 193066191
144 56 947025758
71 140 600724490
46 112 99995545
109 40 423611075
9 126 39826871
38 30 189940820
102 62 550590165
143 146 960241987
112 43 67021543
53 85 828966652
77 73 620461268
142 143 192102898
117 1 500333485
30 76 952668081
7 84 107103718
119 88 203964158
22 2 439930844
127 144 294592250
25 68 654944145
102 120 842621443
53 8 557329229
27 149 803145546
107 111 394075856
143 107 583252973
31 80 124291155
45 44 972903723
87 32 496264053
3 3 887402679
30 150 335221489
133 96 879783986
132 149 566670588
49 142 166646325
75 60 456692166
68 14 198671803
136 45 801806709
99 89 334696586
117 20 149151253
136 144 266982944
144 141 839077602
30 118 946842121
3 62 257369903
139 110 200474013
80 151 968255224
131 30 104207327
100 10 3445519
83 75 139976073
109 37 541502421
12 17 486082157
6 127 268305408
27 2 543114193
110 126 5644182
32 109 198835003
28 33 940217554
84 130 300123316
153 42 23674262
111 124 868254741
2 78 673670181
34 56 112441111
22 61 528804802
150 87 286755574
53 41 266075287
138 39 857173802
56 67 79211673
57 150 536362587
88 147 103553974
94 102 391944338
20 70 117520298
104 103 62526302
17 92 141425965
56 53 560199445
63 72 118203090
7 55 691512521
60 77 509374579
146 100 716300967
18 32 887721081
86 93 217724394
89 112 8155979
15 28 271740326
150 44 52108228
36 66 74399684
129 128 72372841
75 134 227928360
60 39 387381914
77 151 681595012
89 135 72559118
58 32 378912815
96 120 497683672
14 101 926281143
68 96 791531692
147 98 269720792
124 71 809473017
139 113 529377881
53 139 286607062
10 60 160370107
99 115 510768877
154 140 455742698
146 47 34716579
95 60 703338420
37 95 24131548
145 86 109744848
40 21 711021720
152 4 608033402
54 56 316031689
149 65 520647637
18 131 776308964
54 96 632604898
88 87 659774914
53 148 337197060
119 151 289126742
125 140 38894256
40 147 13414365
148 143 741894504
57 8 833553064
105 123 323252632
24 140 878198616
24 38 423464363
42 92 323573086
72 111 723689127
129 75 755125061
125 11 856893251
19 18 136841241
88 10 566311047
127 33 350936176
34 104 762934088
6 94 800801640
74 118 975305584
50 4 580315368
112 42 812416571
133 138 51203238
150 107 115771237
151 92 130250768
143 146 805661425
89 118 426292236
9 118 470043890
84 123 119432174
110 9 327022527
18 25 563546599
139 104 326906054
60 81 130554430
56 42 720453060
29 37 516786233
141 146 342320112
107 46 762688472
72 54 463958606
141 104 754993544
149 58 366506128
118 42 707571121
58 25 130534438
6 85 168437001
91 107 414530621
61 102 740093903
1 87 120094836
54 38 282713469
35 109 240754124
134 95 124053447
46 55 204635145
54 17 648448758
120 41 64582481
101 46 74804683
8 103 377799272
111 131 103722838
62 131 544695149
126 151 358891857
81 31 781956994
56 131 312707279
134 21 56185285
49 75 339411414
39 6 740317618
20 107 247678098
52 81 153916286
35 36 17611990
119 64 355549320
101 35 348175138
120 82 758175790
59 137 711378032
60 82 962773283
114 98 716994420
152 136 681610441
76 122 810895057
12 18 287670620
17 19 512078150
120 137 76725777
43 49 263577337
83 13 17214448
154 38 740260234
12 64 233023767
12 145 671363114
54 108 732499861
101 150 304755763
66 128 448545901
78 112 203537695
125 76 835322983
80 118 741111141
4 45 103533299
8 10 57061530
149 143 385625182
28 122 336053496
126 20 424014362
49 87 51693546
60 119 276120944
88 41 618115396
101 10 919028167
62 56 548793929
71 59 664939616
59 67 54413848
84 27 414205054
107 54 207083542
152 146 326300208
117 39 291592244
76 98 737593980
129 152 966361388
17 97 328099368
101 3 237661299
148 40 606105189
51 98 288772238
85 148 202179156
107 100 226830382
95 63 48474382
69 24 399608892
7 66 423116425
30 40 743799359
93 23 50804935
132 123 517583738
72 115 385243932
70 132 919187816
134 62 838345068
36 13 704597347
146 75 501478821
58 143 829260329
8 117 401503564
22 146 656198472
32 51 873328596
105 149 176953535
25 65 910831537
106 134 606803924
96 79 304894940
78 81 595566118
5 38 347769148
149 95 64060714
128 69 669126254
140 57 119978657
36 88 16072505
76 4 685505040
84 150 394710390
18 100 382886940
83 7 129450880
22 85 822191766
128 89 187937001
120 49 598901094
99 21 130948560
7 128 369064826
60 130 718917397
97 51 245696562
5 101 452596455
67 118 562987760
108 45 334185041
72 66 604531243
50 5 916750462
99 91 610448270
55 2 691141473
46 8 398460385
126 34 388601354
73 130 196761124
24 101 176149706
2 13 75725388
13 120 149772765
31 3 70089333
133 52 889075804
13 151 983274153
96 17 416742971
12 62 667960307
21 154 695031569
5 72 690285739
6 95 1096005
74 63 7783155
104 75 283878084
146 106 606312343
98 83 2309129
143 63 278511161
124 3 238850963
139 136 14274971
95 2 606941205
117 128 940798493
47 101 99670148
78 19 154858342
87 123 859994789
61 113 225520156
3 22 827188606
152 9 448652305
75 100 685969922
14 83 82797157
14 145 199463394
135 73 86438137
16 120 116738987
147 42 113996320
151 95 506450603
75 155 282001352
38 3 143831094
84 121 171659587
36 41 10629133
113 21 77480577
138 35 863913499
8 14 108119775
128 29 295349463
38 142 264825317
89 138 200586970
139 24 210251779
114 62 900129964
76 112 125044880
47 114 767825928
84 39 286742980
49 21 491035326
124 150 16416999
150 90 436779687
74 94 866178890
39 27 473858304
99 133 752905911
3 58 133873298
31 133 77042266
24 147 45450472
147 42 901324316
13 57 403716579
35 26 90218258
70 142 504102082
67 61 776492391
84 99 35770857
17 42 935869605
129 11 273174489
113 41 338998126
54 32 319385456
75 23 48704884
134 2 590047385
25 36 659840687
32 72 366202439
129 138 813833900
131 34 120074615
126 50 809251679
66 145 944131097
62 103 86710983
3 123 685776340
57 42 23537598
153 142 534219260
117 133 737629481
139 9 473924533
114 104 3623376
150 46 16644174
96 139 1230582
83 49 886544988
81 77 130199113
120 80 132975347
123 103 587804834
149 67 248526117
20 28 504466173
49 133 460228612
148 59 267396187
75 53 702459166
2 115 6219835
101 42 556994916
34 123 23636408
36 54 187589553
5 21 911400964
15 136 729385071
133 1 584104340
40 16 782880127
77 130 882558827
63 17 182583885
62 140 141157519
43 85 405658158
40 85 758343649
113 87 300310328
77 91 526686331
143 72 299136007
88 16 328135092
28 55 189439819
133 99 356972596
75 6 481837471
69 34 580676492
22 77 654718116
16 83 428634083
100 7 32621379
114 83 585265751
83 37 350627656
66 92 739102213
15 119 107669820
135 63 711523410
41 137 846831998
118 50 54181500
24 38 311014674
15 53 26840662
25 119 210906271
154 78 874540327
152 127 781658021
100 37 661642299
31 52 922336775
16 153 375394405
99 5 888984414
154 122 321946312
88 145 962919141
65 127 260721365
91 151 768660953
123 116 815821061
49 112 752627295
12 24 878213537
154 54 535100230
105 69 722078991
84 134 1153847
12 99 296609384
143 154 570412127
124 30 948502262
2 121 64545302
153 88 555480867
6 104 49735014
18 82 869158320
33 80 796013305
100 29 571062983
130 80 96474718
10 91 219078383
132 78 816794752
89 46 53152725
139 14 278733089
151 134 542568866
123 139 381068531
141 1 575887979
26 33 626796260
120 99 294256899
93 41 129920780
12 50 846511589
62 148 618489866
77 82 232514025
88 32 934915831
98 150 537516541
129 84 665489014
108 69 100233374
46 95 529314954
152 26 516606814
132 118 607927217
36 129 804427887
152 2 240844958
36 45 473200956
54 133 302512369
118 42 778934897
128 15 134205033
120 122 213022110
80 134 265834480
39 130 559877519
96 107 856858164
39 109 91377884
152 106 629996584
70 108 789506041
69 6 975574057
67 90 128801871
58 29 939239872
133 149 478599693
122 40 308379711
16 78 879115459
58 18 513836666
62 23 328074509
6 142 182725929
107 56 343761464
65 125 234339093
154 36 436855318
97 93 679470635
20 71 113283603
32 4 396598
21 141 693863847
107 43 562806391
111 71 38890721
36 77 102801200
65 28 642863459
14 59 513568487
122 25 650521846
132 121 37689865
16 107 251724692
14 138 696292392
52 126 651612797
133 77 325044098
77 155 925959537
11 2 45734023
52 66 638104264
27 46 183219403
60 13 642263897
6 144 982166366
134 4 980293433
21 140 129630143
34 36 357261926
32 135 747335671
39 57 651814794
117 34 398771680
116 85 170930133
77 79 135790891
129 138 351432319
50 111 621612293
25 89 111410994
106 76 95981024
15 76 575716858
16 107 96996570
61 113 208236950
71 41 772067991
83 124 905676246
127 45 899405845
61 18 457469230
8 34 54127520
32 58 360163773
59 130 8592715
38 145 152541330
18 127 634266371
11 154 616938684
149 70 850257081
10 152 570599539
111 123 63550992
101 28 850458446
74 2 264228900
2 155 448897720
140 26 61013964
44 63 215818173
145 80 108699024
9 58 310731461
141 51 488115629
125 61 863362483
77 138 445528906
73 83 3498983
53 2 241220113
33 3 265914134
37 143 365248519
48 153 458943564
138 109 137101480
44 117 129812031
103 102 645310043
77 38 484436336
13 114 376606428
72 153 59352915
125 17 166401504
24 49 223101785
78 85 942132610
2 100 817696239
110 82 2331878
110 125 115916296
133 72 613514927
52 115 197899081
120 95 425278693
15 11 197331507
115 135 540772444
60 3 557957156
130 48 697781236
154 49 668739321
20 126 862906060
116 47 227107228
52 24 57684684
23 43 666493330
64 129 945668480
153 144 355124391
118 103 693324366
99 129 230261347
95 104 217459866
21 102 34553795
13 122 949838494
119 82 143575748
6 100 173637227
87 122 66623007
127 153 940062619
73 117 37464195
29 79 375016093
86 22 147892647
112 84 564806040
153 104 244144508
87 117 179860767
113 47 21767365
30 20 871390996
92 106 209148293
42 44 204161256
120 116 119835330
31 111 153499897
133 8 845925275
53 86 607582849
77 83 136251729
47 136 910023032
72 60 834963125
23 56 138177111
41 148 319796788
148 34 427605520
63 120 69139935
95 117 408876220
18 94 168911570
117 146 741376332
111 67 196244599
53 80 363034487
79 151 396615919
118 141 88045316
143 148 420311699
151 107 826940633
14 137 733604283
114 43 1506117
14 60 167531228
76 143 217699013
35 98 364296184
77 151 42111202
67 41 416615234
116 125 171443791
65 112 177985746
129 74 821645869
70 54 159099642
98 12 281405318
53 147 356448146
135 34 68280150
19 68 200740658
91 145 713820670
55 23 370057447
15 138 4411989
48 47 740671805
107 20 574889308
118 57 920280416
76 121 860370416
77 18 451516199
138 119 38885812
31 104 11336258
21 40 917627216
129 61 797048797
88 42 46214796
139 90 548134848
112 41 575634879
4 125 146299478
70 13 450567519
115 89 680589074
150 71 18280723
64 68 652564402
45 89 800250520
104 29 503448156
63 83 178770419
126 33 807012895
80 145 418675559
21 115 11660757
140 29 730678528
69 110 357131215
138 105 585594566
15 13 146216878
117 24 401607811
104 127 903714784
151 34 51368074
51 126 982073716
41 50 141534096
38 38 75861442
126 22 367204319
72 91 80964574
73 40 478010204
111 21 435353770
95 137 773683327
101 85 615657522
135 47 405805823
97 65 366599503
58 72 869912683
8 76 343894469
72 13 906067261
131 51 859512805
145 123 708559447
75 46 471485786
17 107 977112701
104 53 878204939
7 32 501949931
65 95 27115969
60 152 84455223
105 4 283287206
31 42 282753346
101 18 4176126
73 129 614038556
84 49 550449431
82 32 945236026
95 136 52520379
126 109 570981594
15 141 933277778
124 45 607092192
148 149 86474013
60 147 889731796
106 59 427230168
47 132 118061304
111 27 897070000
32 109 419028935
60 15 443231834
139 107 247204366
62 121 236750229
47 89 954725404
28 49 137944278
12 75 910878161
127 25 237142099
104 71 947471818
55 149 441069866
20 147 175032427
139 51 317116157
83 2 231135541
70 30 595296987
74 76 274843215
90 103 163581243
67 82 721054756
34 53 82531327
27 2 47151401
118 23 419597489
81 9 235928567
118 148 617637138
15 42 279111731
17 111 953202939
107 152 87573040
131 86 436795751
47 119 116117912
5 153 472105913
141 146 137021353
38 76 38277331
50 1 87329200
21 85 350686566
42 99 638483820
31 83 669147397
49 34 46330081
110 9 181591870
86 23 579779598
109 27 637380971
152 12 591535965
41 17 227843148
74 66 972982783
116 53 854501525
116 94 13254804
3 124 18505765
123 140 127419542
83 61 614837225
96 146 482466809
73 67 627619526
46 63 956565977
99 71 530842915
72 144 579399626
12 71 352550029
37 32 467929136
5 1 42775430
22 90 206548325
72 18 694301534
131 80 957216160
57 152 935149387
131 10 923946403
95 75 75013913
41 147 397852168
20 3 817917118
85 6 347763479
55 132 964002672
115 153 835779117
5 70 185679374
110 45 4647108
50 69 872459792
146 44 117141501
149 138 301451120
67 146 667617149
95 10 41136599
39 61 895216712
136 82 286272597
79 42 380291544
78 46 142819843
94 155 12433994
1 16 295340079
27 6 809801577
62 121 188640090
17 32 124567535
84 127 35110287
121 132 96557648
9 80 424319427
28 3 428073608
11 47 138107791
64 107 72462783
6 107 835835415
138 101 582793983
3 7 870378083
128 145 964245584
55 74 100375402
147 6 82295055
144 14 272153374
67 8 295821178
154 141 3462937
130 49 566368423
106 21 827311494
64 3 496878692
27 127 677821917
78 67 509719039
6 121 836443683
26 79 361000598
23 67 964216894
66 101 784879394
111 99 203277519
14 73 347841509
23 145 69132109
106 53 471841194
11 47 218284568
12 124 482712719
36 129 580337137
99 155 193748780
135 144 405115693
30 55 476884055
54 132 27771427
63 113 5237397
87 135 129225419
9 85 426214864
22 63 140867861
6 74 319818972
24 76 765440531
7 20 592493291
35 121 692624105
130 150 528630301
137 15 43813727
87 77 227247718
110 130 659686050
89 105 20954444
120 126 426637308
43 99 583329390
89 122 15135081
75 95 544108461
28 96 383764357
2 38 498317538
119 19 687032749
57 106 976926784
108 27 730226502
105 115 16061889
153 46 115625933
109 55 85329954
105 110 584143147
21 30 854270798
79 57 103847039
69 25 709210484
86 143 14146893
85 11 17650614
128 118 372439714
145 34 222124965
111 32 169177708
15 107 811300396
50 56 849602036
140 43 873262430
14 88 312901621
139 1 37400191
112 54 46610510
137 105 560602782
46 77 821010078
136 33 325645197
152 111 81072983
26 125 161411414
142 20 340633835
57 126 633873202
91 140 247106124
58 123 902224562
139 46 950060279
51 28 725126697
96 40 394994554
104 143 337371022
145 139 392057265
29 131 674677090
19 117 108687201
31 141 87582542
85 76 480019263
39 100 227971152
149 83 216905171
1 101 284707486
80 41 272767985
81 144 553524257
81 100 10969414
3 95 152408766
82 80 98493655
115 77 241987273
151 7 118020200
105 12 848845853
26 5 676895855
147 6 281873909
108 85 224380674
75 132 516070182
29 24 144455777
88 26 176220842
123 75 949033266
120 34 656041113
68 151 740469379
59 100 463809542
27 125 728284039
11 83 160208773
96 35 822838045
33 109 611163432
113 137 848166353
105 37 130935506
4 4 752853696
137 123 851380955
69 3 514097700
97 61 44762467
136 54 833215408
24 31 772617319
40 126 147673562
107 3 569279723
150 83 90957084
29 154 871156580
56 2 914801206
1 138 320382492
102 19 139239506
9 82 313131723
138 62 881548950
47 52 21384065
39 91 161992501
33 42 365881681
135 37 163507141
152 32 684935055
84 87 768254413
141 55 553142437
10 1 519379511
4 131 245561766
24 80 195496619
65 94 744948780
14 132 259158454
55 131 194056879
33 110 351451443
126 74 241376646
152 2 980378392
24 142 11953481
Output for test 10
205295760
Input for test 11
6 6
10 0
0 3
0 7
3 0
0 2
0 1
1 2 120
5 2 80
5 1 20
5 6 30
6 1 110
4 3 30
Output for test 11
-1
Input for test 12
6 7
10 0
0 3
0 3
3 0
0 2
0 1
1 2 120
5 2 80
5 1 20
5 6 30
6 1 110
4 3 30
2 3 10
Output for test 12
-1
Input for test 13
5 4
2 0
2 2
2 2
2 2
0 2
1 2 4
2 3 5
3 4 9
4 5 8
Output for test 13
9
Input for test 14
10 9
1 0
0 0
0 0
0 1
0 1
0 1
0 1
0 1
0 1
0 1
2 1 10
3 1 4
4 3 2
5 3 5
6 2 11
7 5 1
8 6 7
9 4 1
10 2 10
Output for test 14
6
Input for test 15
8 4
6 1
2 1
3 8
4 5
2 7
0 8
10 5
12 4
2 4 9
3 1 5
8 6 12
5 7 2
Output for test 15
12
Input for test 16
9 8
2 0
2 0
2 0
2 0
0 0
0 2
0 2
0 2
0 2
1 2 4
2 3 5
3 4 9
4 5 8
2 6 3
3 7 4
4 8 2
5 9 3
Output for test 16
11