uva12654測資A

Input:
1 15 2 9
1
5 20 2 3
2 5 8 11 15
4 20 12 9
1 2 3 13
9 9 8 2
0 1 2 3 4 5 6 7 8
10 10 1 7
0 1 2 3 4 5 6 7 8 9
5 88 52 33
30 32 52 61 63
4 82 37 6
21 22 28 59
956 26502 16285 12901
13 26 48 75 99 105 115 132 156 201 222 257 261 267 272 274 284 289 298 334 335 364 378 384 395 415 451 472 498 520 523 525 534 541 553 569 575 589 596 613 626 647 714 716 744 746 782 787 840 850 857 890 896 923 944 984 1064 1090 1122 1148 1162 1175 1195 1208 1221 1238 1245 1262 1279 1283 1289 1290 1312 1331 1387 1389 1430 1431 1459 1464 1470 1472 1509 1536 1539 1577 1600 1631 1696 1712 1735 1743 1759 1763 1782 1788 1792 1805 1841 1845 1859 1860 1876 1907 1918 1920 1937 1980 1992 2044 2076 2083 2086 2090 2129 2131 2163 2179 2202 2231 2267 2281 2285 2293 2294 2298 2311 2336 2356 2360 2373 2383 2437 2480 2514 2548 2572 2595 2608 2613 2616 2633 2648 2674 2703 2720 2721 2737 2765 2813 2817 2820 2847 2857 2875 2888 2957 2967 2982 2988 2998 3046 3053 3063 3080 3092 3105 3109 3137 3139 3143 3196 3230 3269 3277 3308 3312 3352 3361 3417 3420 3433 3434 3465 3466 3493 3494 3502 3507 3508 3528 3534 3561 3566 3584 3606 3619 3638 3651 3654 3667 3671 3711 3714 3722 3728 3742 3763 3778 3783 3808 3810 3838 3848 3865 3901 3928 3941 3969 3988 3993 3996 4036 4089 4111 4130 4138 4159 4168 4174 4190 4191 4203 4222 4235 4248 4269 4280 4285 4298 4313 4316 4349 4367 4380 4403 4405 4445 4463 4481 4518 4528 4533 4538 4541 4544 4569 4575 4597 4612 4646 4663 4679 4680 4682 4701 4711 4723 4731 4739 4756 4767 4807 4818 4823 4828 4840 4841 4847 4855 4898 4908 4909 4920 4949 4957 4959 4987 4995 5027 5100 5137 5142 5192 5206 5213 5228 5236 5246 5249 5285 5320 5333 5336 5345 5373 5390 5394 5405 5406 5446 5452 5458 5470 5476 5494 5504 5523 5528 5543 5550 5563 5570 5649 5656 5722 5735 5755 5758 5772 5805 5825 5828 5836 5838 5860 5884 5910 5911 5913 5914 5922 5936 5980 5982 5999 6006 6008 6015 6030 6036 6053 6088 6098 6126 6155 6158 6182 6228 6247 6253 6256 6261 6262 6264 6382 6415 6427 6505 6528 6592 6602 6608 6614 6615 6647 6689 6696 6734 6801 6847 6890 6913 6971 7027 7039 7080 7147 7161 7167 7239 7270 7279 7306 7331 7390 7428 7464 7493 7499 7527 7539 7556 7597 7607 7613 7616 7623 7714 7716 7769 7786 7804 7952 8001 8008 8019 8021 8053 8064 8174 8191 8192 8233 8236 8243 8274 8303 8357 8378 8384 8403 8425 8486 8526 8554 8567 8570 8593 8630 8666 8693 8724 8742 8770 8786 8840 8852 8873 8902 8968 9021 9077 9144 9164 9176 9178 9182 9199 9221 9224 9263 9283 9291 9357 9366 9377 9378 9389 9418 9426 9462 9498 9601 9634 9667 9770 9771 9825 9891 9916 9930 9956 10016 10023 10063 10099 10112 10119 10186 10192 10201 10285 10307 10340 10357 10360 10382 10403 10410 10464 10469 10488 10500 10550 10574 10576 10577 10588 10630 10636 10665 10667 10692 10747 10814 10816 10860 10862 10874 10892 10899 10912 10914 10981 11013 11076 11138 11146 11147 11203 11204 11300 11302 11337 11387 11419 11424 11442 11474 11487 11497 11534 11592 11600 11691 11704 11735 11738 11777 11786 11796 11839 11854 11902 11904 11955 11956 12026 12063 12068 12132 12206 12276 12287 12302 12330 12332 12341 12352 12364 12445 12447 12456 12484 12490 12571 12661 12694 12749 12797 12858 12861 12862 12913 12935 12987 13009 13039 13043 13167 13178 13200 13210 13229 13252 13319 13389 13404 13445 13514 13525 13601 13619 13660 13734 13740 13829 13884 13901 13954 14005 14007 14043 14096 14131 14145 14181 14304 14325 14352 14432 14445 14462 14551 14558 14566 14583 14694 14699 14709 14754 14762 14803 14841 14958 14968 15015 15038 15048 15057 15169 15219 15290 15337 15360 15373 15633 15637 15662 15667 15715 15716 15743 15758 15788 15825 15852 16022 16027 16034 16078 16147 16160 16220 16223 16231 16245 16247 16254 16464 16663 16671 16743 16796 16837 16874 16896 16987 17011 17035 17049 17075 17114 17151 17177 17183 17199 17284 17305 17308 17348 17370 17373 17407 17409 17439 17461 17483 17496 17554 17557 17563 17575 17579 17590 17606 17626 17670 17679 17697 17699 17718 17765 17771 17900 17935 17937 18002 18010 18041 18053 18055 18089 18127 18132 18195 18206 18223 18239 18279 18283 18307 18309 18384 18394 18417 18420 18473 18481 18514 18542 18546 18557 18586 18623 18629 18630 18637 18648 18658 18665 18678 18704 18705 18710 18754 18767 18786 18858 18864 18867 18893 18904 18947 18995 19181 19202 19303 19316 19326 19360 19372 19467 19478 19537 19567 19571 19584 19611 19678 19679 19718 19815 19822 19838 19845 19873 19910 19928 19942 20081 20111 20165 20191 20199 20210 20224 20243 20269 20296 20299 20323 20406 20535 20595 20613 20646 20707 20760 20798 20836 20850 20939 21024 21063 21082 21084 21103 21108 21113 21155 21205 21255 21265 21321 21378 21397 21466 21483 21486 21567 21593 21758 21790 21826 21856 21913 21966 22014 22050 22084 22128 22284 22285 22406 22417 22559 22700 22753 22775 22784 22830 22845 22880 22910 22930 22941 23042 23088 23092 23112 23121 23202 23241 23316 23339 23367 23417 23427 23428 23449 23465 23479 23486 23506 23532 23568 23646 23647 23754 23762 23810 23848 23902 23903 23996 23999 24020 24133 24163 24178 24202 24286 24299 24331 24376 24415 24419 24464 24504 24514 24522 24533 24567 24570 24587 24599 24602 24613 24614 24648 24660 24677 24690 24719 24777 24837 24872 24944 24990 25025 25044 25051 25198 25202 25214 25283 25311 25383 25498 25546 25562 25601 25642 25735 25744 25797 25805 25986 26022 26054 26077 26110 26133 26150 26214 26252 26257 26301 26322 26367 26401 26424 26430 26481
4 22779 3409 684
403 2313 2364 5075
86 4515 936 2216
53 121 123 131 158 217 219 224 247 277 281 324 372 606 735 796 878 904 906 991 1029 1054 1209 1214 1230 1231 1315 1381 1441 1579 1669 1732 1739 1805 1824 1830 1835 1871 1908 1940 1986 2016 2069 2157 2200 2219 2258 2351 2372 2375 2431 2468 2588 2651 2682 2700 2720 2739 2758 2928 2970 2971 2979 3016 3018 3041 3153 3269 3297 3329 3444 3506 3525 3535 3546 3594 3868 3885 3937 4099 4155 4212 4276 4343 4361 4441
323 17489 259 8429
17 51 58 91 129 137 253 393 424 425 593 606 611 663 672 736 779 805 813 841 890 983 1144 1154 1271 1466 1527 1617 1641 1942 2033 2215 2300 2306 2370 2411 2460 2532 2633 2650 2681 2696 2712 2716 2726 2802 2839 2963 3032 3041 3071 3083 3087 3095 3182 3214 3240 3289 3360 3385 3420 3472 3515 3589 3715 3821 3853 3868 3878 3885 3980 4009 4145 4230 4246 4285 4295 4304 4306 4330 4492 4496 4543 4554 4560 4590 4609 4644 4669 5067 5107 5114 5173 5182 5227 5244 5249 5338 5360 5394 5433 5487 5555 5619 5650 5802 5838 5890 5909 5938 5981 5999 6078 6079 6141 6183 6231 6252 6278 6293 6333 6374 6409 6442 6462 6512 6561 6563 6661 6742 6746 6794 6858 6861 6890 6911 6956 7080 7159 7188 7221 7239 7255 7291 7412 7447 7467 7521 7539 7637 7707 7857 7971 7979 7988 8034 8131 8146 8168 8187 8194 8267 8374 8393 8433 8547 8641 8722 8867 8880 8903 8913 8914 8925 8952 8955 8994 9087 9167 9337 9353 9367 9396 9397 9433 9514 9547 9643 9656 9732 9906 9957 9967 9995 10016 10020 10066 10137 10177 10179 10248 10292 10394 10555 10584 10657 10742 10759 10794 10828 10842 10868 10873 10890 10958 10999 11001 11023 11025 11091 11105 11249 11253 11319 11324 11325 11345 11466 11545 11595 11627 11819 11853 11854 11904 11944 12125 12126 12198 12204 12295 12508 12552 12659 12735 12742 12755 12796 12856 12869 12995 13028 13058 13166 13201 13389 13395 13401 13419 13441 13523 13587 13604 13648 13699 13732 13746 13780 13788 13869 13953 14020 14038 14071 14078 14084 14085 14106 14116 14168 14187 14190 14299 14363 14381 14396 14428 14471 14476 14484 14543 14544 14649 14701 14704 14872 14886 14931 14949 14952 14968 15041 15054 15106 15180 15380 15612 15630 15662 15748 15891 15905 16246 16350 16447 16554 16802 16884 16983 17257 17289 17399 17480
329 16966 4118 15083
0 35 57 78 93 143 196 266 297 308 347 363 373 435 546 555 558 618 622 625 650 658 720 752 828 883 895 914 936 998 1047 1174 1274 1400 1455 1481 1493 1520 1596 1626 1715 1778 1853 1877 1901 1971 2054 2063 2181 2232 2303 2312 2333 2356 2388 2439 2441 2445 2463 2490 2667 2679 2824 2938 2962 2982 2986 3049 3055 3078 3083 3111 3199 3251 3299 3369 3401 3412 3453 3604 3736 3903 3923 3927 3961 4062 4115 4198 4312 4498 4521 4535 4623 4627 4635 4710 4778 4788 4826 4899 4926 5013 5054 5080 5162 5207 5217 5239 5372 5394 5452 5536 5565 5579 5622 5671 5682 5688 5691 5713 5746 5908 5947 6058 6059 6064 6172 6197 6258 6327 6342 6532 6583 6736 6738 6863 6878 6888 6907 6928 6955 6962 6963 7054 7067 7073 7101 7124 7286 7319 7320 7334 7354 7366 7383 7408 7426 7509 7563 7568 7603 7763 7790 7833 7925 7941 7960 7970 8029 8051 8092 8111 8167 8170 8204 8263 8283 8343 8467 8538 8543 8558 8637 8648 8678 8819 8855 8923 8929 8952 8960 9321 9456 9458 9485 9510 9548 9573 9727 9815 9887 9907 9917 9919 9930 9959 9984 10194 10240 10270 10287 10288 10432 10442 10532 10577 10581 10648 10721 10773 10836 10853 10868 10983 10984 11086 11188 11288 11319 11321 11353 11509 11655 11685 11696 11719 11749 11775 11780 11895 11977 12045 12099 12134 12182 12205 12230 12276 12289 12326 12432 12495 12597 12676 12727 12750 12772 12779 12831 12852 12919 13010 13040 13042 13116 13181 13196 13254 13274 13284 13321 13329 13419 13431 13547 13557 13641 13706 13722 13733 13771 13774 13911 14006 14063 14094 14100 14140 14166 14184 14190 14200 14258 14353 14356 14369 14371 14421 14428 14436 14580 14646 14674 14873 14938 15021 15046 15052 15135 15377 15467 15490 15528 15617 15658 15708 15724 15725 15781 15810 15986 15987 16144 16247 16293 16431 16820 16828 16871
Output:
2
8
12
6
5
33
18
29186
2052
4432
14504
16472