/home/toolbox/public_html/solutions/118/11849/u4.in
1 1000 1000
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
51 50
52 51
53 52
54 53
55 54
56 55
57 56
58 57
59 58
60 59
61 60
62 61
63 62
64 63
65 64
66 65
67 66
68 67
69 68
70 69
71 70
72 71
73 72
74 73
75 74
76 75
77 76
78 77
79 78
80 79
81 80
82 81
83 82
84 83
85 84
86 85
87 86
88 87
89 88
90 89
91 90
92 91
93 92
94 93
95 94
96 95
97 96
98 97
99 98
100 99
101 100
102 101
103 102
104 103
105 104
106 105
107 106
108 107
109 108
110 109
111 110
112 111
113 112
114 113
115 114
116 115
117 116
118 117
119 118
120 119
121 120
122 121
123 122
124 123
125 124
126 125
127 126
128 127
129 128
130 129
131 130
132 131
133 132
134 133
135 134
136 135
137 136
138 137
139 138
140 139
141 140
142 141
143 142
144 143
145 144
146 145
147 146
148 147
149 148
150 149
151 150
152 151
153 152
154 153
155 154
156 155
157 156
158 157
159 158
160 159
161 160
162 161
163 162
164 163
165 164
166 165
167 166
168 167
169 168
170 169
171 170
172 171
173 172
174 173
175 174
176 175
177 176
178 177
179 178
180 179
181 180
182 181
183 182
184 183
185 184
186 185
187 186
188 187
189 188
190 189
191 190
192 191
193 192
194 193
195 194
196 195
197 196
198 197
199 198
200 199
201 200
202 201
203 202
204 203
205 204
206 205
207 206
208 207
209 208
210 209
211 210
212 211
213 212
214 213
215 214
216 215
217 216
218 217
219 218
220 219
221 220
222 221
223 222
224 223
225 224
226 225
227 226
228 227
229 228
230 229
231 230
232 231
233 232
234 233
235 234
236 235
237 236
238 237
239 238
240 239
241 240
242 241
243 242
244 243
245 244
246 245
247 246
248 247
249 248
250 249
251 250
252 251
253 252
254 253
255 254
256 255
257 256
258 257
259 258
260 259
261 260
262 261
263 262
264 263
265 264
266 265
267 266
268 267
269 268
270 269
271 270
272 271
273 272
274 273
275 274
276 275
277 276
278 277
279 278
280 279
281 280
282 281
283 282
284 283
285 284
286 285
287 286
288 287
289 288
290 289
291 290
292 291
293 292
294 293
295 294
296 295
297 296
298 297
299 298
300 299
301 300
302 301
303 302
304 303
305 304
306 305
307 306
308 307
309 308
310 309
311 310
312 311
313 312
314 313
315 314
316 315
317 316
318 317
319 318
320 319
321 320
322 321
323 322
324 323
325 324
326 325
327 326
328 327
329 328
330 329
331 330
332 331
333 332
334 333
335 334
336 335
337 336
338 337
339 338
340 339
341 340
342 341
343 342
344 343
345 344
346 345
347 346
348 347
349 348
350 349
351 350
352 351
353 352
354 353
355 354
356 355
357 356
358 357
359 358
360 359
361 360
362 361
363 362
364 363
365 364
366 365
367 366
368 367
369 368
370 369
371 370
372 371
373 372
374 373
375 374
376 375
377 376
378 377
379 378
380 379
381 380
382 381
383 382
384 383
385 384
386 385
387 386
388 387
389 388
390 389
391 390
392 391
393 392
394 393
395 394
396 395
397 396
398 397
399 398
400 399
401 400
402 401
403 402
404 403
405 404
406 405
407 406
408 407
409 408
410 409
411 410
412 411
413 412
414 413
415 414
416 415
417 416
418 417
419 418
420 419
421 420
422 421
423 422
424 423
425 424
426 425
427 426
428 427
429 428
430 429
431 430
432 431
433 432
434 433
435 434
436 435
437 436
438 437
439 438
440 439
441 440
442 441
443 442
444 443
445 444
446 445
447 446
448 447
449 448
450 449
451 450
452 451
453 452
454 453
455 454
456 455
457 456
458 457
459 458
460 459
461 460
462 461
463 462
464 463
465 464
466 465
467 466
468 467
469 468
470 469
471 470
472 471
473 472
474 473
475 474
476 475
477 476
478 477
479 478
480 479
481 480
482 481
483 482
484 483
485 484
486 485
487 486
488 487
489 488
490 489
491 490
492 491
493 492
494 493
495 494
496 495
497 496
498 497
499 498
500 499
501 500
502 501
503 502
504 503
505 504
506 505
507 506
508 507
509 508
510 509
511 510
512 511
513 512
514 513
515 514
516 515
517 516
518 517
519 518
520 519
521 520
522 521
523 522
524 523
525 524
526 525
527 526
528 527
529 528
530 529
531 530
532 531
533 532
534 533
535 534
536 535
537 536
538 537
539 538
540 539
541 540
542 541
543 542
544 543
545 544
546 545
547 546
548 547
549 548
550 549
551 550
552 551
553 552
554 553
555 554
556 555
557 556
558 557
559 558
560 559
561 560
562 561
563 562
564 563
565 564
566 565
567 566
568 567
569 568
570 569
571 570
572 571
573 572
574 573
575 574
576 575
577 576
578 577
579 578
580 579
581 580
582 581
583 582
584 583
585 584
586 585
587 586
588 587
589 588
590 589
591 590
592 591
593 592
594 593
595 594
596 595
597 596
598 597
599 598
600 599
601 600
602 601
603 602
604 603
605 604
606 605
607 606
608 607
609 608
610 609
611 610
612 611
613 612
614 613
615 614
616 615
617 616
618 617
619 618
620 619
621 620
622 621
623 622
624 623
625 624
626 625
627 626
628 627
629 628
630 629
631 630
632 631
633 632
634 633
635 634
636 635
637 636
638 637
639 638
640 639
641 640
642 641
643 642
644 643
645 644
646 645
647 646
648 647
649 648
650 649
651 650
652 651
653 652
654 653
655 654
656 655
657 656
658 657
659 658
660 659
661 660
662 661
663 662
664 663
665 664
666 665
667 666
668 667
669 668
670 669
671 670
672 671
673 672
674 673
675 674
676 675
677 676
678 677
679 678
680 679
681 680
682 681
683 682
684 683
685 684
686 685
687 686
688 687
689 688
690 689
691 690
692 691
693 692
694 693
695 694
696 695
697 696
698 697
699 698
700 699
701 700
702 701
703 702
704 703
705 704
706 705
707 706
708 707
709 708
710 709
711 710
712 711
713 712
714 713
715 714
716 715
717 716
718 717
719 718
720 719
721 720
722 721
723 722
724 723
725 724
726 725
727 726
728 727
729 728
730 729
731 730
732 731
733 732
734 733
735 734
736 735
737 736
738 737
739 738
740 739
741 740
742 741
743 742
744 743
745 744
746 745
747 746
748 747
749 748
750 749
751 750
752 751
753 752
754 753
755 754
756 755
757 756
758 757
759 758
760 759
761 760
762 761
763 762
764 763
765 764
766 765
767 766
768 767
769 768
770 769
771 770
772 771
773 772
774 773
775 774
776 775
777 776
778 777
779 778
780 779
781 780
782 781
783 782
784 783
785 784
786 785
787 786
788 787
789 788
790 789
791 790
792 791
793 792
794 793
795 794
796 795
797 796
798 797
799 798
800 799
801 800
802 801
803 802
804 803
805 804
806 805
807 806
808 807
809 808
810 809
811 810
812 811
813 812
814 813
815 814
816 815
817 816
818 817
819 818
820 819
821 820
822 821
823 822
824 823
825 824
826 825
827 826
828 827
829 828
830 829
831 830
832 831
833 832
834 833
835 834
836 835
837 836
838 837
839 838
840 839
841 840
842 841
843 842
844 843
845 844
846 845
847 846
848 847
849 848
850 849
851 850
852 851
853 852
854 853
855 854
856 855
857 856
858 857
859 858
860 859
861 860
862 861
863 862
864 863
865 864
866 865
867 866
868 867
869 868
870 869
871 870
872 871
873 872
874 873
875 874
876 875
877 876
878 877
879 878
880 879
881 880
882 881
883 882
884 883
885 884
886 885
887 886
888 887
889 888
890 889
891 890
892 891
893 892
894 893
895 894
896 895
897 896
898 897
899 898
900 899
901 900
902 901
903 902
904 903
905 904
906 905
907 906
908 907
909 908
910 909
911 910
912 911
913 912
914 913
915 914
916 915
917 916
918 917
919 918
920 919
921 920
922 921
923 922
924 923
925 924
926 925
927 926
928 927
929 928
930 929
931 930
932 931
933 932
934 933
935 934
936 935
937 936
938 937
939 938
940 939
941 940
942 941
943 942
944 943
945 944
946 945
947 946
948 947
949 948
950 949
951 950
952 951
953 952
954 953
955 954
956 955
957 956
958 957
959 958
960 959
961 960
962 961
963 962
964 963
965 964
966 965
967 966
968 967
969 968
970 969
971 970
972 971
973 972
974 973
975 974
976 975
977 976
978 977
979 978
980 979
981 980
982 981
983 982
984 983
985 984
986 985
987 986
988 987
989 988
990 989
991 990
992 991
993 992
994 993
995 994
996 995
997 996
998 997
999 998
1000 999
1001 1000
1002 1
1003 2
1004 3
1005 4
1006 5
1007 6
1008 7
1009 8
1010 9
1011 10
1012 11
1013 12
1014 13
1015 14
1016 15
1017 16
1018 17
1019 18
1020 19
1021 20
1022 21
1023 22
1024 23
1025 24
1026 25
1027 26
1028 27
1029 28
1030 29
1031 30
1032 31
1033 32
1034 33
1035 34
1036 35
1037 36
1038 37
1039 38
1040 39
1041 40
1042 41
1043 42
1044 43
1045 44
1046 45
1047 46
1048 47
1049 48
1050 49
1051 50
1052 51
1053 52
1054 53
1055 54
1056 55
1057 56
1058 57
1059 58
1060 59
1061 60
1062 61
1063 62
1064 63
1065 64
1066 65
1067 66
1068 67
1069 68
1070 69
1071 70
1072 71
1073 72
1074 73
1075 74
1076 75
1077 76
1078 77
1079 78
1080 79
1081 80
1082 81
1083 82
1084 83
1085 84
1086 85
1087 86
1088 87
1089 88
1090 89
1091 90
1092 91
1093 92
1094 93
1095 94
1096 95
1097 96
1098 97
1099 98
1100 99
1101 100
1102 101
1103 102
1104 103
1105 104
1106 105
1107 106
1108 107
1109 108
1110 109
1111 110
1112 111
1113 112
1114 113
1115 114
1116 115
1117 116
1118 117
1119 118
1120 119
1121 120
1122 121
1123 122
1124 123
1125 124
1126 125
1127 126
1128 127
1129 128
1130 129
1131 130
1132 131
1133 132
1134 133
1135 134
1136 135
1137 136
1138 137
1139 138
1140 139
1141 140
1142 141
1143 142
1144 143
1145 144
1146 145
1147 146
1148 147
1149 148
1150 149
1151 150
1152 151
1153 152
1154 153
1155 154
1156 155
1157 156
1158 157
1159 158
1160 159
1161 160
1162 161
1163 162
1164 163
1165 164
1166 165
1167 166
1168 167
1169 168
1170 169
1171 170
1172 171
1173 172
1174 173
1175 174
1176 175
1177 176
1178 177
1179 178
1180 179
1181 180
1182 181
1183 182
1184 183
1185 184
1186 185
1187 186
1188 187
1189 188
1190 189
1191 190
1192 191
1193 192
1194 193
1195 194
1196 195
1197 196
1198 197
1199 198
1200 199
1201 200
1202 201
1203 202
1204 203
1205 204
1206 205
1207 206
1208 207
1209 208
1210 209
1211 210
1212 211
1213 212
1214 213
1215 214
1216 215
1217 216
1218 217
1219 218
1220 219
1221 220
1222 221
1223 222
1224 223
1225 224
1226 225
1227 226
1228 227
1229 228
1230 229
1231 230
1232 231
1233 232
1234 233
1235 234
1236 235
1237 236
1238 237
1239 238
1240 239
1241 240
1242 241
1243 242
1244 243
1245 244
1246 245
1247 246
1248 247
1249 248
1250 249
1251 250
1252 251
1253 252
1254 253
1255 254
1256 255
1257 256
1258 257
1259 258
1260 259
1261 260
1262 261
1263 262
1264 263
1265 264
1266 265
1267 266
1268 267
1269 268
1270 269
1271 270
1272 271
1273 272
1274 273
1275 274
1276 275
1277 276
1278 277
1279 278
1280 279
1281 280
1282 281
1283 282
1284 283
1285 284
1286 285
1287 286
1288 287
1289 288
1290 289
1291 290
1292 291
1293 292
1294 293
1295 294
1296 295
1297 296
1298 297
1299 298
1300 299
1301 300
1302 301
1303 302
1304 303
1305 304
1306 305
1307 306
1308 307
1309 308
1310 309
1311 310
1312 311
1313 312
1314 313
1315 314
1316 315
1317 316
1318 317
1319 318
1320 319
1321 320
1322 321
1323 322
1324 323
1325 324
1326 325
1327 326
1328 327
1329 328
1330 329
1331 330
1332 331
1333 332
1334 333
1335 334
1336 335
1337 336
1338 337
1339 338
1340 339
1341 340
1342 341
1343 342
1344 343
1345 344
1346 345
1347 346
1348 347
1349 348
1350 349
1351 350
1352 351
1353 352
1354 353
1355 354
1356 355
1357 356
1358 357
1359 358
1360 359
1361 360
1362 361
1363 362
1364 363
1365 364
1366 365
1367 366
1368 367
1369 368
1370 369
1371 370
1372 371
1373 372
1374 373
1375 374
1376 375
1377 376
1378 377
1379 378
1380 379
1381 380
1382 381
1383 382
1384 383
1385 384
1386 385
1387 386
1388 387
1389 388
1390 389
1391 390
1392 391
1393 392
1394 393
1395 394
1396 395
1397 396
1398 397
1399 398
1400 399
1401 400
1402 401
1403 402
1404 403
1405 404
1406 405
1407 406
1408 407
1409 408
1410 409
1411 410
1412 411
1413 412
1414 413
1415 414
1416 415
1417 416
1418 417
1419 418
1420 419
1421 420
1422 421
1423 422
1424 423
1425 424
1426 425
1427 426
1428 427
1429 428
1430 429
1431 430
1432 431
1433 432
1434 433
1435 434
1436 435
1437 436
1438 437
1439 438
1440 439
1441 440
1442 441
1443 442
1444 443
1445 444
1446 445
1447 446
1448 447
1449 448
1450 449
1451 450
1452 451
1453 452
1454 453
1455 454
1456 455
1457 456
1458 457
1459 458
1460 459
1461 460
1462 461
1463 462
1464 463
1465 464
1466 465
1467 466
1468 467
1469 468
1470 469
1471 470
1472 471
1473 472
1474 473
1475 474
1476 475
1477 476
1478 477
1479 478
1480 479
1481 480
1482 481
1483 482
1484 483
1485 484
1486 485
1487 486
1488 487
1489 488
1490 489
1491 490
1492 491
1493 492
1494 493
1495 494
1496 495
1497 496
1498 497
1499 498
1500 499
1501 500
1502 501
1503 502
1504 503
1505 504
1506 505
1507 506
1508 507
1509 508
1510 509
1511 510
1512 511
1513 512
1514 513
1515 514
1516 515
1517 516
1518 517
1519 518
1520 519
1521 520
1522 521
1523 522
1524 523
1525 524
1526 525
1527 526
1528 527
1529 528
1530 529
1531 530
1532 531
1533 532
1534 533
1535 534
1536 535
1537 536
1538 537
1539 538
1540 539
1541 540
1542 541
1543 542
1544 543
1545 544
1546 545
1547 546
1548 547
1549 548
1550 549
1551 550
1552 551
1553 552
1554 553
1555 554
1556 555
1557 556
1558 557
1559 558
1560 559
1561 560
1562 561
1563 562
1564 563
1565 564
1566 565
1567 566
1568 567
1569 568
1570 569
1571 570
1572 571
1573 572
1574 573
1575 574
1576 575
1577 576
1578 577
1579 578
1580 579
1581 580
1582 581
1583 582
1584 583
1585 584
1586 585
1587 586
1588 587
1589 588
1590 589
1591 590
1592 591
1593 592
1594 593
1595 594
1596 595
1597 596
1598 597
1599 598
1600 599
1601 600
1602 601
1603 602
1604 603
1605 604
1606 605
1607 606
1608 607
1609 608
1610 609
1611 610
1612 611
1613 612
1614 613
1615 614
1616 615
1617 616
1618 617
1619 618
1620 619
1621 620
1622 621
1623 622
1624 623
1625 624
1626 625
1627 626
1628 627
1629 628
1630 629
1631 630
1632 631
1633 632
1634 633
1635 634
1636 635
1637 636
1638 637
1639 638
1640 639
1641 640
1642 641
1643 642
1644 643
1645 644
1646 645
1647 646
1648 647
1649 648
1650 649
1651 650
1652 651
1653 652
1654 653
1655 654
1656 655
1657 656
1658 657
1659 658
1660 659
1661 660
1662 661
1663 662
1664 663
1665 664
1666 665
1667 666
1668 667
1669 668
1670 669
1671 670
1672 671
1673 672
1674 673
1675 674
1676 675
1677 676
1678 677
1679 678
1680 679
1681 680
1682 681
1683 682
1684 683
1685 684
1686 685
1687 686
1688 687
1689 688
1690 689
1691 690
1692 691
1693 692
1694 693
1695 694
1696 695
1697 696
1698 697
1699 698
1700 699
1701 700
1702 701
1703 702
1704 703
1705 704
1706 705
1707 706
1708 707
1709 708
1710 709
1711 710
1712 711
1713 712
1714 713
1715 714
1716 715
1717 716
1718 717
1719 718
1720 719
1721 720
1722 721
1723 722
1724 723
1725 724
1726 725
1727 726
1728 727
1729 728
1730 729
1731 730
1732 731
1733 732
1734 733
1735 734
1736 735
1737 736
1738 737
1739 738
1740 739
1741 740
1742 741
1743 742
1744 743
1745 744
1746 745
1747 746
1748 747
1749 748
1750 749
1751 750
1752 751
1753 752
1754 753
1755 754
1756 755
1757 756
1758 757
1759 758
1760 759
1761 760
1762 761
1763 762
1764 763
1765 764
1766 765
1767 766
1768 767
1769 768
1770 769
1771 770
1772 771
1773 772
1774 773
1775 774
1776 775
1777 776
1778 777
1779 778
1780 779
1781 780
1782 781
1783 782
1784 783
1785 784
1786 785
1787 786
1788 787
1789 788
1790 789
1791 790
1792 791
1793 792
1794 793
1795 794
1796 795
1797 796
1798 797
1799 798
1800 799
1801 800
1802 801
1803 802
1804 803
1805 804
1806 805
1807 806
1808 807
1809 808
1810 809
1811 810
1812 811
1813 812
1814 813
1815 814
1816 815
1817 816
1818 817
1819 818
1820 819
1821 820
1822 821
1823 822
1824 823
1825 824
1826 825
1827 826
1828 827
1829 828
1830 829
1831 830
1832 831
1833 832
1834 833
1835 834
1836 835
1837 836
1838 837
1839 838
1840 839
1841 840
1842 841
1843 842
1844 843
1845 844
1846 845
1847 846
1848 847
1849 848
1850 849
1851 850
1852 851
1853 852
1854 853
1855 854
1856 855
1857 856
1858 857
1859 858
1860 859
1861 860
1862 861
1863 862
1864 863
1865 864
1866 865
1867 866
1868 867
1869 868
1870 869
1871 870
1872 871
1873 872
1874 873
1875 874
1876 875
1877 876
1878 877
1879 878
1880 879
1881 880
1882 881
1883 882
1884 883
1885 884
1886 885
1887 886
1888 887
1889 888
1890 889
1891 890
1892 891
1893 892
1894 893
1895 894
1896 895
1897 896
1898 897
1899 898
1900 899
1901 900
1902 901
1903 902
1904 903
1905 904
1906 905
1907 906
1908 907
1909 908
1910 909
1911 910
1912 911
1913 912
1914 913
1915 914
1916 915
1917 916
1918 917
1919 918
1920 919
1921 920
1922 921
1923 922
1924 923
1925 924
1926 925
1927 926
1928 927
1929 928
1930 929
1931 930
1932 931
1933 932
1934 933
1935 934
1936 935
1937 936
1938 937
1939 938
1940 939
1941 940
1942 941
1943 942
1944 943
1945 944
1946 945
1947 946
1948 947
1949 948
1950 949
1951 950
1952 951
1953 952
1954 953
1955 954
1956 955
1957 956
1958 957
1959 958
1960 959
1961 960
1962 961
1963 962
1964 963
1965 964
1966 965
1967 966
1968 967
1969 968
1970 969
1971 970
1972 971
1973 972
1974 973
1975 974
1976 975
1977 976
1978 977
1979 978
1980 979
1981 980
1982 981
1983 982
1984 983
1985 984
1986 985
1987 986
1988 987
1989 988
1990 989
1991 990
1992 991
1993 992
1994 993
1995 994
1996 995
1997 996
1998 997
1999 998
2000 999
2001 1000
2002 0 0
2003