A = [
10146 19673 37975 13436 18966 19329 16082 17684 19049 18032 18899 19991 19273 18592 18781 18584 18107 18640 18412 18095 17822 17311 17303 16764 16082 16601 17083 16361 16114 16528 15999 15960 15950 15196 15134 15122 15032 14610 15107 14947 14494 14396 13950 13677 13541 13270 13138 13185 12729 12547 12441 12095 11787 11210 10773 10510 10800 10210 10067 9924 9579 9061 9057 8369 8365 8248 8020 7585 7639 7198 7108 6966 6585 6323 6135 6114 5890 5686 5476 5249 5241 4932 4769 4717 4413 4383 4305 4249 4091 3949 3792 3718 3669 3526 3501 3360 3304 3222 3192 3050 3003 3035 2805 2728 2645 2600 2502 2476 2467 2523 2340 2227 2206 2204 2134 2043 2031 2066 1890 1944 1875 1750 1724 1697 1729 1666 1562 1565 1531 1478 1476 1459 1388 1250 1276 1221 1329 1191 1244 1144 1229 1101 1100 1058 1020 1041 993 1002 918 900 809 836 826 841 811 825 786 807 728 776 748 680 689 665 624 660 620 598 584 556 613 551 542 556 506 535 569 524 501 479 469 469 446 462 415 448 456 448 383 427 442 396 412 399 383 369 340 363 386 342 404 339 356 360 324 319 318 348 274 316 317 317 318 278 287 295 282 301 283 270 272 291 284 243 243 255 293 265 236 245 263 216 262 230 224 240 247 221 251 213 241 222 212 235 221 213 203 233 215 197 204 202 228 234 178 200 171 184 179 183 231 192 175 203 185 181 163 219 193 171 194 181 172 197 198 184 164 178 161 175 183 192 140 158 175 178 154 147 152 178 161 159 160 173 145 138 141 158 118 174 150 140 137 142 149 108 128 130 157 130 133 135 123 155 119 118 125 144 131 108 131 129 123 141 123 123 120 113 122 108 108 129 128 110 132 108 126 101 120 118 113 120 135 129 140 96 80 113 104 117 102 98 98 89 97 91 111 105 119 113 111 109 104 112 102 85 97 92 95 95 97 88 97 102 95 100 86 87 94 85 106 99 101 107 90 84 94 90 74 89 101 68 101 84 93 78 89 65 87 94 84 65 82 63 73 72 69 76 65 85 73 82 80 78 81 80 78 60 66 79 62 74 80 72 77 85 75 65 61 75 59 73 64 61 77 59 64 65 63 49 59 74 60 57 64 51 71 56 53 59 63 62 60 50 61 65 45 67 63 62 51 58 67 49 52 50 66 53 62 61 63 63 45 67 60 52 63 46 54 58 56 53 48 62 42 52 41 55 36 39 51 42 61 49 65 52 41 42 46 46 35 37 41 55 49 53 45 67 48 47 44 39 52 41 35 63 48 59 49 46 45 44 41 49 47 35 44 58 47 51 51 42 43 54 35 41 37 49 47 42 46 46 35 42 48 36 43 28 49 35 52 33 46 45 38 22 27 34 36 29 35 35 52 38 33 44 46 45 32 35 41 33 40 31 33 24 43 32 22 41 47 28 28 46 34 31 31 32 26 32 27 29 33 31 28 26 24 31 24 35 29 31 28 24 31 29 35 27 28 37 33 49 23 40 30 34 31 24 31 29 17 27 29 32 24 26 28 26 33 22 21 20 33 24 32 25 29 27 26 37 24 25 29 20 17 16 35 24 20 19 24 15 22 35 32 26 31 22 28 16 22 21 24 30 26 18 21 26 26 20 17 18 23 18 15 14 25 18 27 20 32 19 30 18 22 22 21 23 22 20 22 18 29 30 33 29 30 31 25 23 28 23 17 20 23 24 18 18 23 15 13 24 22 14 20 18 19 15 26 22 18 23 23 25 25 16 24 21 18 18 24 17 20 16 26 17 37 22 13 22 25 15 17 20 14 25 13 17 21 22 17 22 22 16 24 15 25 15 16 12 17 17 19 14 14 26 13 12 16 16 16 15 15 18 10 11 13 12 21 13 12 18 14 17 11 11 15 14 12 12 19 12 14 14 12 13 19 14 14 14 22 9 8 12 16 13 10 21 11 16 17 10 15 12 9 8 11 10 6 14 15 15 14 10 12 10 14 13 16 7 15 16 7 13 13 16 19 12 10 11 13 9 10 11 13 19 15 11 12 19 10 12 9 11 10 13 15 13 11 13 8 8 12 12 13 8 7 12 16 15 8 12 12 8 15 4 9 15 8 11 14 6 11 19 8 7 11 12 12 10 10 13 9 9 11 10 10 15 13 13 5 5 15 16 8 8 6 10 11 12 7 9 11 6 9 6 13 9 10 7 11 14 10 5 6 16 17 15 11 9 17 6 3 10 7 11 6 11 8 5 15 8 10 9 8 10 12 13 9 11 12 8 6 5 8 8 6 8 7 7 10 11 9 13 6 5 5 4 8 7 12 11 11 6 8 3 7 5 6 2 7 12 8 9 6 7 9 5 11 4 5 4 7 8 5 8 4 6 14 9 2 4 8 3 4 6 5 5 12 14 8 5 5 6 7 8 6 12 7 10 3 10 8 8 7 9 4 6 5 12 4 7 11 6 7 0 6 8 3 5 6 10 4 6 6 7 5 3 3 7 4 5 5 3 3 5 4 5 8 8 5 2 8 4 5 4 4 7 3 2 5 5 7 9 4 6 3 2 6 8 3 7 4 10 4 6 5 4 6 8 3 5 3 9 6 5 5 5 4 5 4 3 5 9 1 4 7 6 8 11 7 7 2 2 6 5 8 3 1 4 3 4 6 4 4 4 4 2 3 4 6 1 3 4 5 4 3 4 4 4 2 3 2 5 7 4 3 3 5 2 6 4 2 9 4 5 4 4 4 4 5 5 1 1 4 3 7 4 4 4 2 3 3 5 2 3 4 5 2 1 4 1 1 3 2 1 4 4 3 2 7 4 3 1 4 2 6 1 0 4 9 2 5 3 3 6 4 3 2 0 5 2 5 8 1 5 3 1 4 2 3 1 3 2 4 4 0 3 2 2 2 3 2 1 3 2 2 2 1 2 6 0 4 3 2 5 3 3 3 2 7 2 5 1 3 4 4 3 1 1 3 3 2 1 2 4 0 5 2 4 3 1 4 0 1 0 2 4 1 5 1 3 3 2 0 4 2 3 1 1 4 4 4 4 2 4 1 2 1 1 1 0 5 5 3 2 2 3 4 3 4 1 3 5 3 2 2 3 4 1 2 2 0 4 3 4 2 1 1 5 4 6 6 2 2 2 0 4 2 3 2 4 4 0 4 6 1 1 0 1 3 1 3 2 2 1 4 1 1 1 1 1 0 2 4 3 2 1 2 3 2 1 1 1 0 4 1 3 2 2 3 2 1 0 2 1 0 2 3 4 2 1 3 1 0 4 4 4 6 4 4 0 1 2 0 2 3 0 0 0 1 1 2 0 1 2 0 1 0 2 0 2 2 3 3 1 2 0 1 1 0 0 3 0 0 0 2 1 2 2 0 0 0 0 3 1 0 1 2 1 1 1 1 1 3 2 2 2 1 3 0 2 1 1 1 3 1 0 1 0 1 1 4 0 1 1 1 4 2 2 1 0 0 0 0 1 0 4 1 1 2 0 1 3 0 0 1 2 2 3 0 1 3 1 1 0 0 0 1 0 0 0 0 1 2 1 0 0 1 2 2 0 1 1 2 1 1 0 2 3 1 0 1 1 0 4 0 0 2 0 3 0 2 1 3 1 1 0 0 1 0 0 2 1 0 1 1 2 1 0 2 1 0 1 0 0 0 0 0 3 0 0 0 2 2 2 2 2 0 0 1 1 2 2 2 0 1 0 1 0 1 3 0 1 1 0 1 0 2 0 0 1 2 2 1 1 3 0 1 0 1 0 0 2 2 0 0 0 1 0 1 0 0 2 1 2 0 2 1 0 1 0 0 0 0 2 1 0 2 2 0 0 0 1 3 1 0 1 0 1 1 0 3 1 0 2 3 0 1 2 0 2 0 0 1 1 1 0 3 0 0 0 1 0 1 1 2 1 0 0 0 1 0 2 2 1 2 2 0 2 2 1 1 0 0 0 0 0 2 0 1 1 1 0 1 1 2 1 1 1 0 0 0 1 1 0 2 0 1 1 1 1 1 0 0 2 3 2 5 4 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 2 1 0 0 0 0 2 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 2 0 0 0 0 0 0 1 0 1 2 0 0 0 0 1 0 0 0 0 0 1 1 0 0 2 1 0 1 0 1 2 1 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 2 1 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 1 0 1 0 0 0 1 3 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 2 2 0 1 
];
B = [
0 0 0
 3751 1529 2222
 2115 870 1245
 7148 3927 3221
 1595 585 1010
 1709 676 1033
 2417 1013 1404
 2654 1344 1310
 2683 1195 1488
 5611 3410 2201
 1573 679 894
 1926 864 1062
 1889 935 954
 3944 2183 1761
 1896 907 989
 5703 3935 1768
 1508 859 649
 1741 1034 707
 1865 1126 739
 4252 2744 1508
 1814 1241 573
 6257 4316 1941
 2710 1897 813
 2094 1456 638
 6181 4061 2120
 7564 5626 1938
 1261 806 455
 26050 19539 6511
 324 276 48
 1068 832 236
 620 517 103
 1131 979 152
 395 299 96
 4270 3742 528
 342 270 72
 1003 806 197
 565 466 99
 952 838 114
 119 79 40
 4721 4134 587
 0 0 0
 4 3 1
 101 61 40
 1101 915 186
 121 103 18
 117 89 28
 171 123 48
 320 226 94
 7880 6995 885
 5 4 1
 104 92 12
 127 103 24
 125 103 22
 416 323 93
 7970 7194 776
 149 126 23
 174 140 34
 151 143 8
 7351 6791 560
 3034 2803 231
 521897 509930 11967
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 
];
D = [
2 7 0 0
4 1 0 0
1 1 0 0
4 1 0 0
9 2 0 0
21 6 0 0
544 4 0 0
5176 4 0 2
35394 15 2 0
101079 13 2 2
121448 26 3 2
98712 39 7 1
78919 21 2 4
75222 23 1 2
49247 30 6 0
23238 22 2 8
11360 42 2 6
5853 41 2 2
2482 73 6 8
849 74 9 3
321 40 7 8
165 32 6 9
109 62 5 6
117 79 6 3
115 52 9 13
117 71 2 1
150 112 10 7
222 115 15 13
203 120 14 14
219 172 24 19
211 171 29 30
222 212 27 24
213 166 24 33
217 216 31 30
222 188 28 29
191 163 23 22
208 197 31 36
193 144 22 48
90 114 38 48
117 131 18 23
87 102 21 20
132 118 33 30
77 70 22 21
36 29 19 12
21 17 14 10
7 7 12 10
14 6 9 2
6 11 11 15
18 15 9 9
4 4 12 13
14 12 11 13
4 7 5 3
3 5 7 4
0 2 3 6
4 3 1 2
3 0 0 2
1 2 0 1
0 1 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

];x = [
10 12 15 19 23 28 35 43 53 66 81 100 123 152 187 231 285 351 433 534 658 811 1000 1233 1520 1874 2310 2848 3511 4329 5337 6579 8111 10000 12328 15199 18738 23101 28480 35112 43288 53367 65793 81113 100000 123285 151991 187382 231013 284804 351119 432876 533670 657933 811131 1000000 1232847 1519911 1873817 2310130 2848036 3511192 4328761 5336699 6579332 8111308 10000000 12328467 15199111 18738174 23101297 28480359 35111917 43287613 53366992 65793322 81113083 100000000 123284674 151991108 187381742 231012970 284803587 351119173 432876128 533669923 657933225 811130831 1000000000 1232846739 1519911083 1873817423 2310129700 2848035868 3511191734 4328761281 5336699231 6579332247 8111308308 10000000000 
];
