A.inp.2.txt

5
9
2 20
5 30
7 35
3 12
3 1
5
9
2000 20
5000 30
7000 35
3000 12
3000 1
6
10
5 15
4 23
2 21
4 16
5 19
2 18
2
15
12 47
4 39
5
23
9 43
1 4
2 17
5 13
17 54
6
7
4 14
2 21
7 26
4 18
13 30
2 10
6
10
5 15
4 23
2 21
4 16
5 19
2 18
7
8
4 10
4 12
3 20
3 22
2 21
5 15
2 38
1000
999
555 378
342 360
885 965
104 979
621 73
461 626
84 725
101 172
650 229
430 154
952 625
665 250
680 485
397 676
232 613
689 83
760 128
182 772
385 642
393 942
197 791
729 753
242 376
179 204
582 440
699 23
381 864
794 235
755 724
799 723
39 496
603 975
892 533
204 68
320 66
132 438
3 658
461 822
939 206
142 351
874 621
553 449
764 157
396 219
878 822
159 319
138 269
618 160
868 408
581 363
864 56
693 531
263 694
614 22
419 704
392 130
423 395
571 603
646 353
777 9
738 623
656 532
737 617
151 462
273 463
494 50
713 635
948 887
725 516
252 556
982 796
121 804
240 293
749 747
518 407
425 640
817 362
438 317
719 724
390 899
542 461
250 130
540 295
62 884
744 652
273 570
462 75
66 853
408 966
643 422
158 48
737 555
290 73
871 666
231 428
914 678
62 21
197 192
134 626
772 254
340 630
671 770
683 688
333 175
723 298
510 892
878 468
967 457
885 732
428 710
899 758
872 153
55 864
904 514
282 844
885 497
406 695
10 73
154 407
930 790
303 424
273 872
54 489
896 18
479 509
807 958
617 437
116 443
470 184
895 561
68 8
332 667
261 36
956 939
48 158
142 647
827 910
222 602
154 451
777 149
962 408
165 158
249 671
280 874
244 946
522 480
175 918
299 858
369 3
789 802
678 810
425 340
808 291
980 30
810 726
713 926
712 301
622 711
898 962
418 135
502 500
577 274
269 832
396 536
65 166
172 267
324 810
518 888
246 242
284 496
222 26
771 756
578 236
22 309
753 763
76 213
902 620
444 371
947 833
771 905
815 390
701 664
914 827
242 332
325 704
437 716
785 392
979 267
127 383
353 438
788 909
470 928
577 839
442 127
305 825
264 838
215 719
427 604
269 175
778 372
219 670
416 941
786 915
25 523
842 895
620 805
197 196
186 738
24 420
331 948
933 349
120 843
12 683
550 757
963 721
739 119
732 183
464 407
573 79
914 495
354 945
585 589
96 323
808 734
861 634
156 971
755 379
237 105
150 45
607 189
435 441
302 653
712 566
364 272
813 470
272 943
499 632
650 523
206 58
649 576
274 433
546 521
820 642
736 144
345 764
452 754
882 669
802 497
529 100
909 996
952 771
322 413
918 11
581 544
981 973
45 497
421 498
542 73
452 335
231 913
268 814
114 636
173 702
877 736
715 179
102 945
26 668
645 415
922 506
814 991
200 21
967 926
267 769
302 913
805 284
651 306
23 88
546 506
192 943
230 343
871 747
469 135
121 499
148 869
155 619
617 638
683 41
906 876
450 122
273 510
469 310
446 469
915 133
317 708
319 523
196 720
275 89
26 607
198 669
964 758
82 951
315 511
149 599
650 58
244 706
843 960
377 967
774 587
460 965
962 542
822 259
371 117
587 244
356 672
593 434
738 856
171 724
567 496
525 272
88 332
996 249
934 234
844 442
980 150
159 982
968 920
699 256
495 909
51 252
854 431
394 364
151 117
275 320
466 741
237 720
162 654
284 100
72 396
42 426
419 957
537 773
81 870
220 383
558 775
645 445
307 148
653 372
899 434
143 703
831 746
532 588
546 371
363 720
627 852
918 742
800 505
390 622
11 920
964 398
860 26
580 414
84 874
194 379
385 391
137 929
480 530
339 814
978 668
171 541
803 530
656 56
249 915
731 82
464 875
222 426
971 558
706 717
230 293
811 260
452 611
634 576
111 915
637 49
739 566
543 767
382 690
960 892
539 397
826 803
737 97
156 889
111 438
288 20
711 492
438 660
312 185
545 596
626 679
322 912
744 209
36 649
12 177
61 424
491 683
661 256
84 893
722 86
979 84
366 162
840 215
376 11
74 270
455 205
107 85
130 358
935 803
197 862
383 823
481 759
609 435
740 965
282 812
767 788
217 921
399 871
764 297
412 75
539 776
600 971
600 901
138 330
50 701
162 27
61 402
272 712
118 923
368 614
222 575
536 903
192 43
352 22
896 420
449 751
370 480
549 101
541 234
90 324
931 978
71 496
478 163
235 724
517 182
972 544
958 36
232 246
897 479
433 920
544 805
757 326
309 729
381 121
123 54
147 91
411 287
600 250
168 831
964 170
475 820
403 838
813 255
284 932
579 54
448 671
975 346
732 473
463 88
599 796
213 699
782 34
175 413
651 318
754 468
5 509
555 585
136 947
558 921
675 965
402 651
550 880
910 664
113 224
103 538
924 139
119 339
651 594
509 338
182 168
773 802
590 927
136 424
350 558
571 121
117 759
787 533
53 20
253 682
882 802
897 141
775 303
129 931
10 835
350 692
232 433
662 460
981 989
237 235
672 145
140 141
916 3
723 211
416 569
722 489
878 385
132 43
432 125
545 70
112 388
251 718
515 340
290 891
570 210
979 354
641 463
528 82
596 601
529 249
727 552
946 422
99 333
985 775
19 430
44 757
744 518
634 583
585 242
692 170
255 483
95 803
83 917
140 545
736 757
491 921
643 360
709 2
767 331
25 213
492 988
202 780
997 705
32 262
472 74
448 866
405 670
769 637
579 780
46 85
914 829
722 542
907 737
36 598
315 524
787 799
240 264
916 569
177 585
976 57
421 514
618 722
351 213
336 535
423 195
285 419
175 585
494 910
916 102
387 343
60 614
757 236
153 7
998 406
729 618
833 804
736 904
472 413
999 570
262 770
511 609
702 725
478 130
621 27
383 786
894 394
330 262
398 283
130 39
867 434
225 137
281 976
262 627
285 886
510 189
386 347
557 447
128 820
643 333
38 216
318 832
546 912
467 956
666 633
809 715
471 946
334 40
998 315
837 531
2 304
577 871
330 631
635 513
359 618
416 181
102 294
683 799
629 435
823 204
880 269
689 464
697 924
80 931
465 331
403 81
76 216
957 196
794 917
884 769
235 788
956 148
9 308
858 962
315 591
405 3
58 621
23 422
513 667
963 386
470 576
627 694
660 11
983 950
606 924
343 56
596 641
813 196
77 969
148 804
220 133
334 562
410 24
953 287
274 926
90 676
116 156
268 317
577 693
275 609
252 263
139 394
86 525
21 950
632 975
400 987
60 500
830 802
818 113
434 276
366 804
889 172
675 814
180 893
983 256
867 869
96 593
365 399
23 512
699 364
708 377
465 223
11 910
649 861
532 68
283 801
10 894
538 317
443 768
849 48
199 968
696 557
587 234
500 613
322 978
762 88
128 985
258 105
640 404
680 23
436 925
113 607
340 28
406 88
445 944
405 325
103 917
521 985
94 487
929 101
187 947
295 3
630 624
562 194
7 438
801 968
902 853
800 707
113 298
790 963
577 953
399 945
23 341
235 501
310 4
317 502
489 929
212 171
884 187
575 181
679 798
838 138
618 769
737 357
356 699
72 462
144 278
195 658
654 864
657 584
541 964
84 710
715 364
406 405
245 297
389 381
788 500
831 224
527 43
346 781
323 525
144 46
228 293
905 857
801 497
800 188
94 21
185 434
746 557
69 915
611 22
331 726
581 580
159 812
122 833
138 592
846 456
978 264
518 708
512 132
765 629
287 346
849 118
880 512
2 783
100 440
430 223
587 683
887 889
761 884
956 13
377 972
469 19
474 938
120 577
156 310
369 772
188 375
350 172
455 698
284 532
976 77
654 2
976 567
535 680
439 996
831 435
671 772
608 682
536 154
840 119
585 435
404 657
552 888
578 754
774 667
708 679
141 619
251 922
787 561
16 114
268 283
232 595
903 151
423 598
756 239
399 352
897 946
342 243
843 738
867 444
774 592
806 593
149 180
264 594
355 2
175 821
95 85
993 872
553 783
569 600
864 816
711 850
685 215
79 28
329 614
197 577
639 844
18 167
786 657
125 714
254 683
183 779
278 254
861 355
742 348
384 175
982 88
696 445
680 34
201 794
645 195
128 447
390 763
348 19
176 591
68 707
545 20
698 101
108 25
345 876
708 185
569 618
472 629
26 375
14 543
280 710
116 954
691 7
807 692
249 366
481 486
515 640
870 495
787 1
645 220
619 262
541 985
903 376
257 515
160 779
883 43
181 814
384 234
521 545
486 396
377 610
132 559
525 113
8 341
194 509
218 797
305 795
508 343
896 677
775 246
518 441
560 31
255 210
518 344
294 303
405 306
153 503
993 843
839 139
974 993
17 579
39 383
210 179
293 346
289 137
852 444
49 437
855 381
36 454
938 960
703 763
847 441
126 400
367 385
627 596
568 381
641 100
314 603
779 147
148 584
480 829
581 862
157 309
513 911
438 211
358 360
754 364
228 854
121 716
497 98
666 241
346 971
983 733
955 797
482 457
208 99
251 496
414 55
776 208
566 488
523 233
94 243
618 773
842 138
317 999
306 691
694 303
623 126
778 787
577 472
286 375
443 980
204 80
694 123
657 171
495 370
697 182
279 396
881 912
221 293
107 330
296 216
783 105
494 926
991 159
786 77
486 8
379 575
464 386
885 526
338 810
268 800
418 900
306 585
684 61
399 408
822 682
605 52
331 598
0