uva11389測資B

Input:
96 1874 5
961 6313 8727 2428 7342 554 2671 9527 2024 7052 3510 8134 2162 9079 42 6700 2549 7762 1698 2905 4335 1310 333 7502 1438 5653 5785 4914 5790 3188 8837 8660 6047 8199 1177 7059 1994 6900 2148 3882 8805 6827 2518 8175 4469 7804 6127 7007 5620 4938 1784 8578 5700 3534 3057 2245 7298 862 2170 5623 7070 8048 5654 6595 6763 8538 5629 208 3666 7228 5185 1670 2507 4192 2627 3298 2542 48 1975 2603 1238 2441 5109 614 1880 671 641 839 5684 98 605 3513 8073 2271 9870 160
2029 7065 7228 2941 6285 1785 7534 433 5921 4500 2134 9574 1892 5772 8664 4602 3187 6666 8545 9981 9860 7818 8757 3389 6169 55 5801 8176 4821 5977 4403 2179 2638 5132 5647 8896 6499 2212 5859 5604 944 4717 4933 6274 752 9095 2027 2002 3731 5618 100 9151 1488 1462 5061 7888 8507 9671 838 9636 8827 7287 9694 2291 1254 1868 1692 6610 7518 915 3272 4967 9648 9589 4985 9711 9449 8298 7113 621 7004 5083 614 6563 1331 6092 9193 4677 7090 6729 556 4956 930 5712 2632 3561
48 9712 4
1659 8035 624 4870 1426 1512 1636 1851 4933 1032 4123 9880 2465 1785 1388 991 4930 7749 9282 8938 9223 950 9558 6467 4401 1922 7692 6551 8637 5737 4416 7448 3891 6077 2067 7731 5773 5120 9456 2386 2955 5109 1476 1042 3590 4256 6942 4967
165 7359 6611 9598 2109 9293 4260 9075 5275 1925 6596 6773 2519 3972 9509 167 3585 2386 2899 9848 8383 4770 7731 1813 9067 6775 7724 525 3478 2473 1927 4646 5217 3337 5044 2926 9038 7666 8558 5557 850 2081 8255 2297 862 4950 4598 993
94 4266 1
1198 290 1091 8916 958 7291 455 1628 9171 8424 206 5377 4964 9009 1578 1247 7123 8067 7323 9641 7615 7598 6254 9893 4106 8907 2838 2603 429 5075 4510 6922 971 9340 4894 6012 3476 4852 524 8875 5339 2611 4788 1332 8154 6428 7307 8811 9603 5140 4161 9087 5322 4567 405 8431 2402 9783 1981 6989 7973 4950 2470 4530 7577 4038 4393 8098 319 1550 7919 4849 1069 8112 2038 7143 4814 6633 1236 8256 7000 1321 3179 3479 1583 1236 446 4948 1064 8968 3059 1763 2560 5679
5753 3127 5870 5239 2444 4798 807 2081 135 4631 4849 9351 1337 9010 8377 289 5100 7031 2393 26 2321 5481 9364 8590 4384 2988 8724 9830 5231 1477 4886 5064 2992 2241 7156 1689 3776 6281 7092 948 1853 4692 7150 3104 5016 8141 5108 6796 7195 9510 845 7022 4173 5534 7235 9117 179 255 7694 8091 6761 2299 4015 1335 1074 3864 4722 4482 8829 8793 4158 1393 5384 1200 430 1266 2809 1825 6869 8754 8538 9768 1102 5966 5957 157 6594 4041 5121 1382 9502 1821 555 9870
43 2534 1
1381 8303 7067 4378 6361 2589 2622 7457 19 5289 6390 6324 5124 5590 3035 9473 3266 3891 8402 9537 6414 7211 3321 4751 7928 4892 9750 9690 1445 3098 1595 4585 640 9621 780 143 1854 3033 2580 9664 1174 9845 613
7346 1953 8798 782 295 702 1924 5458 4186 1914 3380 8423 2872 8382 3824 188 1889 4825 8109 9566 1678 6111 4075 9309 2182 386 4506 6251 3548 4384 5899 5652 6763 1229 6852 9108 6165 4163 3289 3382 6583 343 535
77 7074 1
2706 2104 6742 5584 7266 2393 1247 7500 9049 4229 5028 5916 552 1818 2750 762 4467 2190 5638 7954 2946 8325 2194 2666 1898 6309 8050 8704 4171 2856 5973 675 9930 8513 6785 5380 6562 291 5299 1438 8375 2238 9556 5716 8620 8971 8093 3882 1317 9418 5212 439 3103 8553 55 4922 4271 7960 1776 6234 2616 4332 9210 6898 7569 5857 6427 6413 4822 515 2403 5950 2333 6846 4044 4835 684
6132 2498 7018 7594 2719 5828 7541 1715 3112 9675 6571 7216 2712 6667 6559 9798 7612 4681 5797 9677 5694 4716 4193 3700 5218 3846 1522 5955 4990 9716 4400 2626 3230 9908 2066 4728 9830 5239 1427 7702 2361 2007 181 1221 4522 731 5542 2477 6146 1305 8803 6760 9169 8107 7546 454 9128 3013 2804 7954 3190 6901 6083 9316 8929 4220 8920 7833 8071 8605 2041 1120 4326 9027 8017 454 5241
48 664 4
6580 7331 436 8536 2546 3233 5840 5170 2940 3239 6908 3488 8621 567 2101 2300 628 1426 566 1235 2650 8493 8175 4857 6837 6502 966 6604 1836 1608 4412 7222 4299 8190 8753 3943 5513 3061 6217 8002 3320 4421 9568 2470 8045 5857 7981 417
1 5773 3524 2944 9431 9343 6398 1865 3695 8457 5148 2269 3626 1478 2586 2504 1727 1411 4897 1131 9037 9040 7439 4701 1202 7479 1755 1261 572 5324 2563 5338 1918 9765 168 1255 8325 3004 3821 697 204 9939 3612 4802 2284 24 7066 1412
56 9 4
1934 7512 3417 3273 9387 3491 4356 5826 7131 5971 623 8000 4337 5524 9699 9804 9839 9902 1500 9173 9967 403 7021 3565 5236 2906 5063 7509 4864 2477 793 330 167 448 9689 3568 7939 1363 5252 3839 7642 6362 9123 1450 285 5931 7359 6967 7122 9848 5958 652 3892 7069 9566 1911
3818 7404 2442 9650 2149 8791 6059 388 1630 6942 7688 5947 2911 9194 4160 4776 8496 8985 1759 4460 582 9755 3856 7586 743 6204 7683 5308 5057 1715 159 6947 2779 2810 9257 4233 5388 3567 198 9810 267 1210 4653 6882 1382 1168 3328 7320 2919 663 5180 811 9300 7883 3023 7284
58 4897 2
3501 3340 7355 3480 2200 8033 4043 8942 3619 3995 139 4786 9914 310 891 5233 5085 8800 9132 8795 1540 5046 4414 674 7601 2271 1637 8020 3077 5335 1441 6884 8901 1455 5741 6928 5358 4707 1144 5103 7943 8524 6115 729 1718 6903 4907 1483 3653 7909 1975 4858 9974 3765 7300 8632 8005 6463
9375 7494 7213 6594 9234 2937 7422 481 2899 4464 8270 2680 3737 5988 5117 9590 7841 9952 5933 7174 8368 7332 7921 2590 7321 9605 9317 8875 1506 5159 2976 6140 5426 8349 6101 5839 6797 8944 2128 1561 8052 2767 2479 7210 4870 4486 4670 7872 395 2642 1895 1931 5971 6883 2074 4017 1530 9379
62 4930 4
8230 2312 3934 8390 4051 308 5718 5002 2178 2785 1441 1927 614 9225 6608 1639 892 1137 2420 7594 5 6941 9502 4764 6113 5303 1735 2466 1548 3228 2929 3125 4926 3591 2542 66 9085 2867 6400 5377 7318 3547 4160 6757 9500 1140 98 1795 2912 5134 5113 7526 7041 4262 3591 9683 1173 8416 2584 3960 41 5827
3088 3274 806 2165 258 6528 6197 8201 1731 6266 1989 6341 7662 3510 1946 553 3352 979 2887 5053 7895 1479 4239 2283 8191 3551 7321 4461 4541 1350 8738 6471 2071 5751 7767 5000 8212 9814 6387 3198 7544 3900 150 3640 4419 4657 9799 2255 6795 1648 571 5367 1078 5013 8647 3586 972 6009 5522 8103 2876 1474
14 3729 1
1108 7881 1306 362 9005 7215 8906 584 2400 3170 3995 2503 5872 2092
9663 1761 9679 4820 1091 7806 2423 2800 453 8824 7353 5850 9013 1231
77 6134 5
6478 9481 7859 4675 6270 845 7264 3302 7881 5470 8128 966 8354 9865 2721 8655 7107 5003 7434 554 5751 9511 8563 9324 2313 2999 5785 175 7772 966 8786 4677 4077 1662 1821 8169 5558 7422 7838 4057 4613 4702 2905 9729 2940 8085 5533 2041 9833 971 7619 2627 9257 2507 519 3565 9529 7947 214 654 4573 463 5080 1214 3780 794 5761 3702 3452 2951 2338 3003 706 4040 3861 469 1133
5180 3705 4021 4460 3286 3690 2262 7196 2988 7045 6242 9470 5085 5898 7288 1001 182 2323 5597 8332 5143 5844 3730 8007 6993 6884 1668 9770 2547 6459 9449 9565 2838 8668 6793 1954 5 4133 9419 6808 7425 308 7347 3122 2420 9773 3000 4792 3412 3305 3802 6923 2555 5649 6787 2878 9540 4155 1277 4628 9944 6340 709 1541 1483 7343 1183 4197 9840 4845 2907 2630 2100 5197 1030 7916 313
14 1251 2
4945 4611 4267 5195 7071 7854 9187 9019 2088 2320 8910 88 9999 1015
7138 9355 7506 3209 7711 587 5551 3593 9309 7564 3723 8696 3909 500
80 5805 1
190 8309 9384 2362 8003 4010 5315 7785 8517 405 570 2413 173 9904 5405 9399 1976 8804 771 3823 4206 8858 5553 1289 116 1583 7740 6759 9506 8653 7803 4719 1430 8536 721 4847 9418 2118 8297 8286 3524 691 194 1028 9821 9203 1837 1469 2901 2009 5557 3897 117 2760 543 2056 6084 2632 1361 1749 7246 5420 440 7888 8225 3857 8277 3712 9962 2489 1704 1401 6256 6185 6895 922 8719 7024 7280 7866
3992 8025 1350 9237 9831 914 1321 8129 6870 5326 8545 1814 2480 8152 6619 6733 2471 9545 8269 5111 4906 1340 5079 6690 7297 8864 8474 2424 3003 5918 6110 6424 9947 955 2958 841 1310 2096 6983 1036 9472 7929 7602 2978 1488 2810 9421 5742 4433 4072 6864 2123 7666 7239 5374 8721 64 6672 8219 8324 8025 5254 4574 8286 2757 1945 1751 6639 4497 2970 9570 6690 3724 3600 5100 9265 8694 474 3797 2715
1 5718 1
1989
1945
42 1415 1
803 4593 5977 8345 8354 5056 1864 5141 5550 9801 9046 5950 3016 4248 225 474 2289 8076 3096 3324 3274 4576 4876 461 9036 427 4570 1644 6825 8356 7735 4451 3059 810 9853 6364 2236 7700 3510 1988 1517 8676
8262 3327 5243 2833 5806 2156 7895 7525 5741 266 852 9204 2426 8939 8062 8414 4976 488 1674 9079 2441 6613 7048 2245 3438 5959 5440 7913 749 4371 2220 7618 8301 4712 3234 5214 9502 6512 1638 2387 7140 2131
37 2493 4
2045 7572 4169 8273 3777 6770 5089 2115 2446 4747 88 9653 4865 1879 8313 6696 3915 978 8251 9091 5748 1029 232 4683 8863 7445 1838 725 7888 6347 6005 6440 828 9220 8146 6823 4768
4378 555 4141 309 3730 4268 6905 514 7447 3866 6333 18 5015 2630 4353 9000 3580 7380 2125 3376 9310 6557 2647 664 6056 3650 1178 8575 7496 6770 2936 8108 3210 7533 9920 4642 2711
49 7395 2
2794 7429 7588 8163 4387 4317 6063 3966 6128 2973 4476 9228 9593 3193 1155 6051 7882 4461 8929 7422 5254 3504 5484 8142 3962 4894 8884 7662 2160 7799 1579 6411 9478 4210 262 1603 6446 1142 4452 7069 4823 6746 4558 1674 7948 2666 1680 1034 7995
9821 2664 50 9880 5014 7132 604 1011 2168 1712 4896 6455 685 6472 6162 8277 4536 1563 6908 9681 6906 9081 1661 2266 8018 9838 2050 2400 9096 1751 2292 7313 6236 1060 4146 2661 2234 3263 9232 7947 1233 2653 5184 4499 2516 1810 1665 1949 3857
70 3957 1
4144 2229 791 3042 8462 9650 3932 6573 875 4383 6201 7670 8096 1904 1782 9413 4837 8590 3618 348 1858 1666 7911 6332 2437 3891 7759 2472 9971 2075 8710 106 9666 2737 8898 3717 3174 6275 2513 8620 7898 6385 3298 2881 2146 3154 39 4319 8463 3313 8584 236 3395 584 5772 2058 5557 32 676 9965 8567 4440 2136 8434 710 4932 5654 1773 1298 1096
7992 5059 6031 2821 1046 5978 250 7410 9307 4397 3024 1423 348 8853 3084 3110 4775 1844 8495 5812 1880 7604 453 1735 4050 6368 7093 9703 2124 9441 5402 8441 9417 779 2640 2546 6605 6441 9392 4681 7757 9494 7168 2401 358 1117 516 5893 1472 4228 9370 7829 1460 6709 3253 7136 9276 6557 6295 6194 9067 9864 7637 1744 3613 7965 3830 2673 1295 2965
8 4079 5
2290 8278 5054 5916 6702 5941 7453 2960
3346 2269 6475 1967 584 3550 6764 8719
82 2836 4
1403 3708 5276 4610 715 1631 4441 1337 6133 3464 6021 427 9108 8297 2475 6447 2328 1727 9189 3717 2414 7860 8321 399 2882 1749 9210 5842 6594 8454 2740 493 6517 5316 3479 8058 1403 2395 816 7699 9062 2298 308 422 2138 1396 7383 9131 3521 8760 2445 5254 3555 7571 6318 2041 612 9172 8751 9772 429 6848 9694 1711 3183 8248 9758 2206 2438 6472 8037 7478 2187 5809 6466 2632 3980 2761 9362 2219 8656 2353
5780 39 645 2343 4860 9328 8493 1037 3046 8591 2761 1946 2732 1463 9876 2512 6745 7350 1123 142 2686 9115 75 6790 4308 5799 1059 6401 3508 3079 8284 738 7156 689 1263 7640 1283 9516 4021 7512 3622 6981 7741 5019 8548 1248 1993 7332 9423 1195 2538 2516 84 4841 1454 1713 1541 6078 4182 228 9188 2870 9885 4131 4115 4459 6294 8991 6122 9815 9925 6910 1593 7030 4529 4011 878 6352 7400 3916 665 8853
0 0 0
Output:
3695690
33664
498049
289372
244980
1537012
2233160
662946
921468
76960
1354370
274812
339686
0
347736
1069620
227744
391123
228180
2133292