commit 099310b36978b3cbe4f4ccd630e24ee070c73f41 parent 7c885bf8a80528f8a1e2401220f5bc4f58b7aa3e Author: Michael Savage <mikejsavage@gmail.com> Date: Sat Jan 9 17:42:05 +0000 Add basic RNGs Diffstat:
| rngs/fixed.cc | | | 26 | ++++++++++++++++++++++++++ |
| rngs/fixed.gen.h | | | 1024 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| rngs/fixed.h | | | 13 | +++++++++++++ |
| rngs/genfixed.cc | | | 15 | +++++++++++++++ |
| rngs/mersenne_twister.cc | | | 184 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| rngs/well512.cc | | | 44 | ++++++++++++++++++++++++++++++++++++++++++++ |
| rngs/well512.h | | | 14 | ++++++++++++++ |
diff --git a/rngs/fixed.cc b/rngs/fixed.cc @@ -0,0 +1,26 @@ +/* + * implementation of a lookup table PRNG + * + * the table is generated by sampling WELL512, so it has the same properties, + * except the period is much lower + * + * on my laptop, WELL512 takes 1.2s to generate 10m numbers and this takes 0.8s + * the speed and badness make it viable for particle systems and not much else + */ + +#include "intrinsics.h" +#include "fixed.h" + +static u32 nums[] = { +#include "fixed.gen.h" +}; + +void rng_fixed_init( RNGFixed * rng ) { + rng->index = 0; +} + +u32 rng_fixed_next( RNGFixed * rng ) { + u32 ret = nums[ rng->index ]; + rng->index = ( rng->index + 1 ) % array_count( nums ); + return ret; +} diff --git a/rngs/fixed.gen.h b/rngs/fixed.gen.h @@ -0,0 +1,1024 @@ +2031697373, 2862711631, 981455028, 2775358433, 1582383432, 3830122867, 1237660837, 1776130127, + 222076696, 3696294784, 1892034728, 2553770640, 1817691711, 1442374832, 587988144, 445081381, + 133690976, 763675007, 2497631750, 418000050, 3230446483, 3901838125, 4143057134, 616853242, +2813508489, 3872005133, 3892019943, 3458834057, 2041842301, 4277010470, 4174917113, 2728453903, +2081709950, 3902695679, 1944985060, 2329675342, 880354782, 4108218325, 1296341267, 668373788, + 568379274, 3536760822, 3014370750, 490984288, 4249027785, 1235063700, 79877510, 2060124223, +2757541860, 238693686, 1865414293, 3686884859, 3082862794, 3414574735, 3921834068, 3155081912, +1418133895, 1985759466, 2911573780, 1782252399, 3884219389, 1221475319, 2309057309, 4253689800, +2524528446, 3057837160, 2519707642, 2707085937, 1435665248, 1220220296, 1545598381, 750394088, +1226876013, 1693049533, 3526058954, 476186162, 873269479, 2961485547, 7564239, 3517665481, +1422756141, 546884158, 3540613284, 1228773854, 4167001307, 1379141732, 959095915, 3816090089, + 765292696, 2441387568, 2997561349, 1331749294, 723583650, 44641686, 683355945, 1660117525, + 471433247, 3715434971, 774534656, 1560628027, 3915413544, 2276320792, 1450626384, 1348487426, +1301393716, 1931503138, 3399861139, 2623071609, 976081105, 2163645888, 930730183, 1673698623, +2260186169, 805916192, 3952954752, 859070419, 2861853347, 3881951590, 1350923736, 4054227748, +4088789196, 371547290, 792016763, 502047646, 2464852590, 866616415, 2261941704, 321817240, +2898077627, 2241850965, 1498898676, 641123948, 4276144923, 3971194129, 1328384166, 787661079, +1973233774, 1286751819, 4117395945, 4202967741, 153359041, 3769401341, 814104638, 1624610879, +3857041698, 2426706365, 2974865132, 1549333630, 2668418828, 2470442935, 1148409856, 3373126896, + 478400358, 505622754, 1846426438, 748173231, 1308476235, 979431213, 3647598386, 3762184267, +3538637781, 2086944304, 2058520128, 2479551605, 3897756373, 896001909, 395451797, 116574824, +3205338237, 3806599004, 787665100, 892482561, 2214544049, 3076883748, 1865360146, 248107980, +2760652002, 2495305481, 3702543600, 1763526105, 1065752079, 2452851751, 3945388213, 3547070789, +2955641450, 3736489002, 23884620, 4175956332, 2288481938, 3884843660, 2037367549, 2241775841, +1984562127, 186741902, 2168099305, 2182062095, 4114380026, 1955593281, 1827214171, 309938481, +2419661249, 1766950148, 452861304, 1223011375, 3514155753, 2309968152, 3851275677, 4217458044, +3573598671, 128398962, 275745406, 850608743, 105538391, 3087221373, 3976942517, 3278705947, + 948744093, 1415310188, 2755756101, 138845089, 1477753572, 2202132353, 2643986023, 1490537023, +1453868790, 972571160, 798945397, 3429741069, 4071809845, 520055973, 2848963588, 3321810808, +1612782958, 3767732866, 3156648073, 3094957082, 1297071801, 2142687760, 2462191750, 533126826, +1388357988, 2439865655, 440324619, 574418771, 1829840848, 4107918178, 2911682741, 2539417450, +3595046218, 516764070, 1364828933, 3146405119, 507778249, 1460377438, 3304511223, 4034886088, +1292424637, 2884962085, 2551854350, 2842892271, 2225802601, 2337206060, 3566016802, 1771880177, +2606267654, 309968768, 2011864142, 4256070573, 64152791, 3758180938, 2163350547, 2111042177, +2575521172, 3107876935, 1213763684, 4010445560, 73703730, 657563092, 1026643893, 992731807, + 391464685, 1644793364, 297476970, 3924370866, 1497711989, 79819453, 1701193803, 3597533192, +2785254580, 3830914090, 2196251619, 1229181969, 3684905240, 2240555905, 2583074507, 3974413671, + 938444478, 1683475833, 987839376, 2093233487, 2733442721, 4128646184, 108536259, 3505798739, + 541533839, 960397380, 1325044000, 1963308360, 3270154114, 3414402067, 645037366, 1178139985, + 934894072, 378016002, 3425277380, 2852850160, 2083691071, 2138102573, 4269092169, 252036327, +1889460444, 1796835864, 259004902, 4222088445, 3523854492, 3500974553, 2410664931, 3921850972, +3615061147, 351182571, 127423862, 3575851344, 2606204500, 2374545168, 2376010335, 3026470237, + 477597124, 2768267962, 770186318, 1518189567, 3898921647, 814171233, 1639171137, 1987731012, + 891952105, 2117081620, 1130583227, 1711211252, 2968081563, 2546459482, 2680929444, 526759440, +2686920250, 1993400590, 2568061516, 414395216, 1612740243, 3596258219, 3058610038, 2669333982, +3212616426, 3559689269, 83180407, 1828116234, 2586374108, 1764626577, 1931005657, 1684848176, +1127552466, 1008054223, 2375648938, 1379419958, 4188112550, 1667647981, 1995675806, 1754092146, +3741322330, 1489296973, 3591584882, 813629995, 3580100044, 2219072316, 1248889953, 3732011634, +1475719887, 2122317031, 495779122, 1657205301, 2849366775, 2196560526, 2677730904, 563800264, +1783416740, 1974519344, 2110572387, 1446158514, 4164103022, 2704733714, 1521545867, 3142535914, +2691405840, 2440226886, 3987209637, 443612984, 1528200184, 3255179034, 3482290156, 2761374579, +1576587826, 31903692, 1604477845, 3487853076, 4153347393, 4194146510, 925972188, 513013382, +1213005763, 2693825385, 1821603842, 417829918, 1570086395, 1858204489, 3165072633, 666003455, + 906325896, 57812575, 3453201183, 1498832380, 4278201680, 99202999, 1312927737, 531019749, +2575495289, 1185192210, 1048511485, 951125851, 4057323443, 4261761936, 2442354227, 2052799905, +3995706831, 959400391, 2039774032, 1210666334, 1355742531, 2075472388, 3574922, 468844061, + 638292830, 44323234, 4145258446, 1966978086, 801306450, 4212326706, 2740328528, 2337373020, +3238750772, 2257537281, 2299851841, 3371613066, 3119341951, 3405533124, 141326362, 303715841, +2319661588, 2616308848, 901766128, 1570968377, 2591590224, 1205746855, 1774816984, 3903512295, + 170337841, 1841711729, 2548877365, 3802194615, 473020487, 857436264, 1359966755, 3470517880, +2245635400, 259854410, 1657913709, 515343843, 1970094144, 599195287, 1482716810, 2993219331, +3862099033, 1441685643, 2580684504, 3878009490, 3639819911, 2773334284, 987491140, 2306336392, +2157517155, 2336529595, 4159661720, 563608205, 4092799342, 3041224449, 855303991, 3760498882, +3978998289, 2474855539, 3777981211, 2665773879, 2909848640, 4105904389, 726346233, 262189719, +1171053247, 3064201903, 771457232, 2664252868, 2546774395, 517261191, 4285284225, 3759421244, + 611969052, 1041779646, 2921648505, 1115392715, 2891323164, 1258500842, 2643152278, 4073978416, +4048998970, 587467074, 115090342, 2267710036, 313406032, 1771858466, 3501444543, 1861558917, +2264832180, 709341911, 3288193877, 2642820261, 814411626, 2261218761, 1940851219, 3364697692, +3764902193, 3861026651, 4171177816, 2843480485, 2799431036, 889582712, 1854138944, 1107898644, +3360588190, 2817053255, 1268074331, 4166318950, 3595321591, 4212731466, 3645289079, 1712201036, +1999530702, 3413809013, 2536021632, 1147297358, 3704688545, 1983873831, 1684693684, 3039641366, + 844804028, 165252114, 1428171245, 3740011768, 3805246565, 2994812360, 443124520, 3083526114, +3296381345, 1864525679, 3775667342, 1587650025, 2051309490, 989544053, 3288498596, 2279826983, + 656473075, 1450346974, 2166852825, 1469280200, 17088228, 2018175327, 1541254858, 4002900020, +3062142769, 4015848965, 323814416, 1828692121, 517795719, 3441961367, 4292314751, 1890927307, +1492332017, 303489242, 1459404649, 2329713149, 1022978347, 1733193683, 2241694909, 250331759, +2417530786, 1300284790, 1427004533, 3270125305, 4246858742, 510565809, 4292648036, 4136278380, +1108996118, 485084589, 328696931, 1896369475, 3660660475, 2548085663, 3397207623, 3149726914, + 494462715, 4276529304, 3928403759, 3888271818, 1815921100, 3359282832, 375395000, 2645767129, +1890944130, 480442805, 622695772, 3918611470, 1749320539, 3390397242, 3299492145, 3377176489, + 531420570, 2173884521, 4184758734, 3228971933, 2566068907, 4203041501, 1781861776, 190353788, +1496011955, 2650029764, 2758262883, 2099500897, 455335137, 4155855981, 2230854997, 271467618, +4175165522, 4207534757, 34635877, 3969673618, 302792347, 1280088778, 2413827881, 683395482, +3306867556, 1654775299, 3102715927, 3150291150, 4267400074, 4208978235, 3831608005, 3670483992, + 463290547, 2579225921, 2322426815, 2540696520, 4066860871, 233906282, 4058113661, 3021269410, + 601646131, 4182880657, 1419110050, 1564629548, 1114335097, 3024514015, 487199270, 3917563208, +4126848953, 2439890336, 2921943682, 565610557, 1581416807, 1238766082, 1068341674, 834535688, + 131046992, 650999940, 3191568679, 774147149, 3921212641, 2462914069, 3036438426, 1313682101, + 855935799, 2396518616, 1158091008, 1630511699, 2858569863, 2038058413, 449583373, 2603827423, +2893161083, 1453826723, 1579720030, 3485492022, 2264774087, 1436909544, 1624452561, 3411640363, +3666481489, 731074388, 3487746471, 2532694478, 2746742599, 1684633884, 2072310044, 1203832332, + 999388152, 1960421937, 4121803075, 1240546431, 2500305486, 1201100597, 2279183343, 458299554, + 358319235, 519037326, 3162305460, 820673743, 3361728154, 3456498516, 3147956076, 754908473, +1007994904, 3450283881, 970541064, 3884033463, 3654524234, 740026582, 3097198999, 3348468295, +1280073840, 3045654345, 4013520604, 1359564566, 4031034348, 3233771685, 3061007858, 3636246362, +1735244060, 980361113, 2580287088, 2238861160, 3043816671, 726690185, 1527160388, 2362391300, +3562760326, 3138708885, 2384830447, 298693222, 3003301509, 3218841404, 1834125313, 856416966, +1470024229, 1342861629, 810976410, 3769681614, 49786586, 2896512842, 1844372632, 3819582802, +2147808259, 1964693089, 3133628786, 3667510928, 3883111643, 4130249377, 933696503, 4064155809, + 602422509, 4241856222, 3671123133, 1764691914, 1583347284, 2478195811, 2320036037, 3188266959, +2017793071, 700772817, 2160143007, 3852623323, 2927653259, 2566414988, 2649947622, 2168617643, +3046101008, 1718548694, 860549149, 333036626, 1742492325, 1636263445, 2972092038, 2631828320, + 923789907, 1624902290, 1121852637, 2070221935, 3834275407, 2072326242, 2933309437, 4015472406, + 755978084, 1578688896, 2467355076, 477921958, 381084849, 203693320, 1887490217, 838144388, +3761755342, 3439804042, 537159705, 2250521005, 1189146238, 1309397009, 4178531695, 3812070464, +2712190291, 2281324181, 1751970176, 1754904364, 78937950, 811938045, 3452444060, 2736584230, +1874691726, 506579743, 3239456812, 1470035225, 1106542465, 3688508426, 1904866861, 1785798359, +1323140084, 53793646, 1405503301, 578940506, 4162296217, 1091468939, 2038679413, 4136431486, +2223033417, 96791364, 779422533, 2086677947, 4115916697, 99200088, 176847707, 3265314643, +4059775879, 2102526139, 2571286661, 2360323835, 4175152920, 26936594, 2760032056, 852708318, +3311301653, 27247280, 730914362, 3148694246, 1714170436, 3369759125, 4259447453, 424998679, +4011987214, 3661073653, 2547462614, 3817017953, 389296954, 1017775844, 1217455456, 266871337, +3982015558, 1419656708, 3120372573, 2769845793, 235785793, 3624246017, 56628980, 3398184449, +1625318869, 2655389680, 1154116952, 25144783, 4045108697, 3015014818, 1707398750, 2355047911, +3625505980, 2064219, 117038769, 2332019220, 1767560572, 570483369, 2359288779, 2744347552, + 132930939, 1157557210, 1687632249, 552325142, 2581597401, 2739826315, 3019848141, 711328539, +2239615509, 1550834820, 613789823, 2211329937, 3560492222, 3751028097, 2523571058, 1441524513, +2270485540, 1156024572, 3555234901, 513604358, 3921537692, 153105414, 1058041807, 4109266970, +2054701578, 1509422089, 2515403904, 1510658911, 748630702, 1606261466, 3619775028, 2915646021, +4036891362, 2381014007, 416257651, 3722732837, 1701895888, 1244101464, 3142541788, 607587479, +2056068064, 1925141008, 3015465463, 1828202568, 2890816030, 3695346674, 503314799, 3798236752, + 150190958, 238320607, 2988056808, 3047773612, 1586737284, 953488594, 1898985240, 3179003694, + 137048916, 1954066267, 1585992291, 2850134683, 4090387656, 3630253267, 410880925, 155688101, +3262030655, 642991581, 3627511153, 606711204, 684234494, 951054160, 437201963, 1083877968, +3071281696, 2976743202, 2248368627, 2890167809, 610368295, 3275084874, 1871423990, 776617954, +3930666393, 2881638502, 3678147305, 4235266638, 3448472389, 3434097477, 948507662, 268147303, + 602964647, 28207984, 1481046195, 1897091476, 2999062392, 1159688417, 1205250539, 3479206648, +1729260554, 102080316, 1186023895, 2264017420, 1078708772, 2270191557, 3363262000, 3782445887, +3965693877, 1519656728, 4276792806, 2244047401, 489162390, 1944560701, 2274061534, 3012694140, +2590524749, 238567364, 2639469218, 424971665, 3619539593, 2197108017, 329825493, 2196361531, +2340172037, 1645092785, 2534951344, 2921530195, 2892017444, 1277152960, 1932318498, 867318409, +4051706427, 1180783979, 2104669225, 1429739887, 4289038222, 2984533779, 3736159565, 1780902917, + 411994518, 3791612597, 602315224, 2709375057, 1699319818, 2364345433, 1824305703, 2862491597, +1607947156, 2797400740, 3599482800, 2749082028, 677760822, 570586206, 1288749118, 1680180789, +1965736614, 2644074189, 3578986609, 3124660893, 3029100596, 1560595452, 1991467137, 1025225082, +2753814526, 3581997502, 54937957, 3230760529, 3677096467, 2210005029, 4067813222, 1107416621, + 957046883, 3428085392, 530899643, 3043535911, 311441450, 1472739512, 993782712, 936532478, +3867269469, 466750824, 86117473, 1507464238, 3862469329, 2814869356, 1534541853, 2791002863, +1760429785, 2465234074, 268922019, 2715598495, 974854576, 3984845324, 357193157, 943229120, +3998605703, 2464033334, 87795447, 4008986406, 3909922860, 85593631, 575841473, 3826134687, + 488295530, 3116333918, 3095022413, 1506807378, 541258970, 1449426123, 1234571654, 3527309900, +4270350817, 2813724233, 3134070354, 1169226863, 2309824208, 496977162, 2384402253, 4245208648, +3252939127, 662321894, 4226081841, 1839121461, 2295650031, 13350581, 2685116960, 1130178996, + 926073226, 382064827, 2492476590, 3035831346, 1966867515, 2125205405, 2433383400, 1279274060, +3471177934, 1458248915, 2342582820, 3434625592, 3619874860, 1963270918, 338423213, 1645523458, +2277607546, 4024313123, 1915477306, 967616382, 311625564, 3951809855, 2121254796, 1832692219, + 148017519, 924923305, 997131004, 899021361, 977124148, 3328190115, 1701151526, 3192793507, +2761853841, 3048834070, 1619524360, 2419048637, 790327793, 2186869331, 3128242369, 4067323884, +2103033798, 1603427931, 2581542175, 796748663, 2939182867, 2879137936, 524878632, 1243245695, +1535006667, 2940842844, 3438203262, 3001812596, 2317913999, 3466103051, 3805370688, 3232763784, + 198980583, 3163405815, 3669846204, 3353427675, 294802068, 2028375158, 4177596756, 2766866684, +1317930769, 5480697, 3886054219, 1204646785, 2637806615, 1929614705, 687375003, 151824260, +2819075166, 4145655092, 3310218887, 3846640779, 1137098129, 4235487537, 508101935, 2358672521, +3620812222, 1633170595, 415686383, 1724409236, 1234095690, 3219476483, 2461830314, 2101801105, +3098393447, 1574031950, 3096668084, 1538034569, 497742039, 429695602, 930876056, 4191811157, +3879961232, 1949121627, 1680120386, 2805092710, 4292898786, 3525193993, 1552228519, 1540165135, + 673671378, 691211068, 2813496905, 2036110458, 2524721123, 63107807, 1159755075, 1440441855, +3947753407, 2227966871, 2119856816, 3783037852, 2309097557, 1329490129, 530017876, 1836667284, + 815232538, 3195063259, 583287632, 1428872937, 1403289410, 4114009830, 1967121924, 1919462342, +1849635710, 647866034, 3469323778, 111450005, 2929100700, 3567231553, 1382496042, 3343920323, +2334581104, 3798402410, 595449225, 3653371150, 2114503097, 2634382427, 2875030859, 914950341, + 277927162, 3914412042, 1576828379, 3588416338, 4257072982, 1157879193, 1451098267, 1970580275, +1378842651, 2025902824, 3207875209, 2731773415, 1281917988, 3813917996, 1186483383, 134923783, + 935450830, 1193951328, 1769809534, 61235920, 1872132104, 2942448418, 132608831, 3268869514, + 620844118, 648473732, 1844904089, 2243118808, 3836261698, 3080096878, 4156554462, 3123557827, +3948627152, 192610359, 735995475, 2503221484, 1030526539, 2061383705, 3133487404, 2811736420, + 48690658, 3279997545, 449492988, 3507883694, 1376796026, 1488212835, 3141908405, 1080416394, +2897457668, 3121902570, 1291338860, 444658572, 1363707873, 498578906, 140633350, 3055654999, + 705379841, 1019323138, 2803251742, 792010720, 601202792, 346040458, 3413128886, 3629115438, + 403689492, 861285029, 2288385703, 412094725, 1944400654, 304295464, 977076495, 2435753948, +4050512373, 2197882974, 2418894903, 987201882, 3229172202, 4196111194, 4222238877, 268403649, +2006717616, 2137803756, 3231447284, 3813985179, 3306492621, 2785511175, 3112529238, 1257197588, +1664570639, 4212218635, 2635395875, 4102333408, 1280781098, 651921339, 1041076335, 1526217704, +1770922185, 3527303962, 2234481489, 3084458975, 1264708368, 3678943375, 1995413217, 899281600, +2494409317, 859044571, 229168543, 2691906802, 1438642779, 1405773662, 1282908319, 1111357751, + 24686347, 2524361884, 3664546889, 141328807, 3014392787, 823039284, 2736274271, 3277933120, +3042838291, 2806377626, 457311545, 3843799680, 716589545, 2621239716, 782389954, 870848491, +3440584870, 657628608, 1254212553, 1218336590, 1345103510, 3394320198, 1428473440, 1077735162, +3104896408, 3382217318, 1675035567, 3685486050, 939210529, 3111025536, 1274284652, 2716053875, +3618382733, 3953207968, 757336414, 3622857657, 1922768078, 547841079, 431322269, 1762426974, +4256998771, 4116821844, 1636213257, 1458057097, 2519988653, 996028307, 3572334526, 2981918153, +3415002030, 1255320391, 1878224740, 2608064937, 2228942732, 1451128673, 3588183006, 460047470, + 905640821, 193303695, 2174744255, 3451836063, 3942773134, 4259076615, 209331306, 2842225252, +3427848603, 2290749997, 1247516117, 3290437500, 890010659, 1476528960, 3975303221, 1601599981, +2446818521, 941400949, 1177820253, 4038308231, 1599279128, 3074529251, 2037767461, 1486138347, +2128787012, 2489856524, 646128688, 587165478, 2988638395, 3354946822, 3511205055, 1970040939, +2671842287, 2281796706, 845971410, 1406455555, 3441270041, 1760568269, 2903651388, 5366561, +3054404699, 2076888218, 1006379187, 2914336208, 1663334414, 3425072084, 1443922179, 590198224, +2144073730, 182802961, 1772603865, 1073073174, 4261671086, 1713547975, 701893067, 2748515183, + 665628135, 3482944322, 809724248, 1168142845, 91998911, 1283277082, 3865432446, 3103380208, +2903906415, 853420323, 1980881215, 719404880, 3225015628, 3137912809, 3982277127, 1208864813, + 329274649, 800356130, 1621244473, 3356788659, 3185026176, 1167649837, 4164519468, 796568034, + 394976855, 971044545, 1414874693, 896989652, 3114103583, 2324707492, 3109532109, 2393786701, + 392856756, 2748746614, 2327748690, 1707003955, 3799093301, 1357381572, 534162152, 2803982721, +4004678017, 3752041246, 2023540947, 3514759323, 2556090897, 3128082254, 129195907, 2411622890, +3992871122, 1625858099, 1238504179, 598406870, 3971975032, 4076872217, 1812936032, 1468490978, +2343484485, 4257310926, 1391600473, 4252977618, 3625552544, 2583294902, 3931104827, 159178136, +2544040740, 1495596540, 1677737558, 303184629, 1624797359, 1207088849, 1038217456, 1521088715, +3290858388, 3078621324, 2552251921, 2941805906, 2145911081, 1008989419, 920812238, 2103599124, + 610920361, 212097200, 3987074068, 1120407767, 3914017691, 2981010516, 3891143030, 661053139, +2408628302, 2940416728, 3582365666, 4234362070, 182234832, 3710739427, 985058043, 3922303056, +2227950498, 2080631237, 744643739, 1505129377, 2197631618, 3465268520, 1835564347, 2015210229, + 981517687, 93783776, 2034183932, 2952469018, 3890571880, 2152122963, 2359805171, 3143565098, + 45773725, 241289946, 3478328660, 199028146, 3064145581, 3618842373, 3029728718, 935466408, +2409369788, 1790396463, 2319554345, 3022088242, 2390868537, 105188503, 162934447, 1840271793, + 463611220, 4071125180, 463051695, 650424186, 4051526694, 815100801, 2243250441, 3893214334, +3858290381, 3071032673, 2100848508, 1640926808, 254198127, 2926492106, 3561528937, 1973070759, +2545280529, 914535968, 3769172694, 1900827356, 1622227530, 2275773524, 2551268182, 3554103710, +1356849240, 3565649203, 1872147208, 3644530259, 1035192022, 1055699743, 2291326354, 120458950, +4004619669, 3858068573, 2732633569, 2432548875, 895355617, 2679488898, 1900339419, 1539125375, +2464989985, 277838681, 795163095, 4285132472, 3749676588, 2949837093, 1838555784, 1634422848, +3083437589, 4137347946, 4102406505, 2424493083, 3666337261, 1061941621, 1881312412, 2086360246, + 119268058, 2688116300, 3651422924, 3134551639, 3223582489, 4115982247, 4169721819, 82989418, +3314441647, 646201222, 2743213147, 1197820396, 3595114580, 440839602, 576922730, 1129767864, +2972227686, 1480046208, 1001892783, 3871845784, 1509994443, 3095519552, 4006835537, 1940844368, +2270899747, 894866604, 4147535922, 2589685579, 3572842584, 2739443944, 3685616018, 349165559, +2201831251, 3541185156, 1773157950, 2182779768, 4119541548, 1387702417, 1543685058, 2241474185, +3240461390, 4048730403, 106275496, 479586937, 361978413, 3858842298, 3629158915, 270185645, +3357986791, 2247889773, 3427706072, 3033691521, 3975169166, 2353438957, 2901377034, 2344370435, +2880207301, 3459610870, 1675703316, 2591899182, 779915104, 3289631849, 1001117674, 579754307, +1435389768, 455606241, 3298349124, 4206979457, 1731652428, 4070335574, 2647455428, 3193406797, + 776557555, 1481618548, 943415009, 282347436, 2976078260, 230496795, 638293880, 1372994653, +2482219359, 1017476877, 3868661163, 882524268, 3044152520, 2471339221, 3823627954, 1213201721, +3857081713, 3398863750, 3147633682, 1859757695, 1328823716, 2943705521, 3701669003, 1866698589, +1430938548, 2771003645, 4092598889, 450504060, 2363028121, 1769065931, 3554609008, 3085551024, +2561506913, 1724409133, 991467593, 3505215530, 3184321611, 1420332010, 3955931112, 1482720309, +3109648197, 3660314592, 3758322620, 895852401, 3077540821, 3299491381, 793792337, 2630861980, +1005896992, 2933958780, 864900992, 1352134483, 2859153398, 2950755011, 1231636552, 2907806882, +1166848127, 659949614, 156896524, 1833636723, 1672329498, 1068172444, 143041824, 3651002788, +2517041234, 2918143538, 2905121362, 619255511, 2877109059, 2034354985, 1076639974, 1925049866, +3849987054, 1017005076, 2377458155, 2183464820, 251768352, 3351710559, 3731321589, 104727525, + 352008874, 3993261488, 2132550807, 3132864732, 3643391420, 1464190021, 2722139826, 3303154552, + 726942463, 3347289019, 2175146413, 3253862186, 3759828558, 4171235629, 3661735392, 1865999642, +4244623683, 1759750176, 2374904151, 3281484126, 1358865916, 3427398153, 3848112122, 2540398731, +2737208078, 2591619744, 932384684, 2998820130, 3458407773, 2361474532, 163168425, 462249950, +2605105976, 2921214715, 1453497996, 1693773882, 2581134848, 3877245430, 1597738876, 3464189674, +3704980455, 4005110556, 706177248, 3694272821, 3189785082, 4177988562, 3290009679, 2580868583, + 87179871, 1435462549, 676128385, 458810398, 2632576951, 4023002617, 510923572, 438783240, +2993036827, 851903981, 2351193227, 2437044010, 2596934428, 2079424682, 255145763, 3073818066, +3681308155, 589344858, 972360744, 1639452378, 2017977442, 2357004364, 2525782843, 2362987548, +1632604457, 2254025221, 485028231, 2219329990, 2599433119, 2286048894, 272132707, 3563016859, +1393908921, 3996352207, 783340539, 40840082, 1514152165, 1754629588, 3360223385, 704198085, + 451442661, 6976495, 3869535894, 3724429037, 480877743, 1833606441, 695769875, 3320035496, +2045220777, 3081405977, 366605661, 876179596, 3859701086, 1249733515, 2996242723, 41097517, +2994432342, 3128109485, 2669412945, 2599761891, 1270512009, 1361107234, 1647570389, 3878510119, +2828706543, 492608961, 1539859985, 3783168291, 1969113274, 82068740, 4089408845, 1053358890, +2483971994, 1259243778, 3729265295, 1734473204, 2503605217, 1519799460, 2423427150, 718566325, + 678397046, 1690585944, 4157634311, 1393264250, 289832522, 3860553753, 4244849401, 1836813594, +4203346432, 1677670051, 783874870, 4192280676, 239202706, 3269589179, 3689940842, 3655489735, +3392412028, 2755484182, 158454828, 2377973204, 2322622353, 576331799, 2920953716, 1984572767, +1397801681, 2356612623, 4091052210, 1414015410, 1921713142, 4046536714, 2136017449, 834902306, +3806779687, 2732241599, 3124271550, 3624568715, 795538650, 3236201244, 1182246940, 4147530154, + 368053948, 1461981369, 2709767106, 1178419188, 384931659, 2925942795, 3520418523, 764493847, +1362479753, 1674689392, 1028284523, 513436349, 2585106611, 912065487, 2919378908, 2417090710, +2367850611, 298212632, 23223954, 1070772426, 3036915922, 2744220459, 2737469368, 2032894215, + 363384451, 2366700634, 3827607165, 3599164269, 96170298, 3267029994, 1672846327, 1478707231, + 186518227, 2443013106, 13010024, 3262962898, 109758067, 1730001526, 1615252375, 2745557376, +2045956658, 376095035, 2528441933, 2506507403, 3747396904, 736513985, 2660680048, 1225522131, + 658830841, 1874834990, 4082920691, 1656741436, 2329402745, 2802427223, 2008115078, 4021559257, +3366192007, 1357633861, 1109101255, 1624977078, 1979952657, 2845589679, 975553725, 1348830071, + 160355776, 2059432354, 378220951, 3727295488, 3131587187, 3271765242, 359863512, 2857478589, +1106923982, 1447065596, 1734377156, 4235916185, 847232737, 3694050983, 229563970, 529834346, +1880704101, 2355458770, 1210355347, 1357735732, 918585097, 1265608013, 2357148112, 3457755555, +1631221353, 2694318685, 232360227, 3335298279, 1763767939, 1752087044, 578829892, 1854114879, + 582686083, 519695830, 1526365630, 2376833769, 1954490043, 2240397322, 3685602896, 490096301, +3004874293, 1577210789, 1796181268, 2991964886, 1497982699, 1704317301, 3767914091, 2757349351, +3271597627, 1521838450, 2218963426, 2794898468, 3705950359, 3540208556, 2189018379, 2555411046, +2369378478, 199965017, 4275788534, 1194516905, 3413408044, 1956367550, 2015305039, 1584024440, +2490294414, 3627394391, 2921745240, 1640390345, 445121798, 625577538, 1634548600, 3932557297, + 466650737, 2219405601, 2849365457, 3691443493, 1364328820, 373171100, 158793382, 3456120140, +2465305457, 2972295965, 3841585751, 2163980084, 1611073051, 3854025328, 3353897809, 470134549, +1384436178, 2596862654, 2079528403, 3933674753, 570853458, 3307869703, 1811652755, 3466081759, + 244231772, 4098397406, 1415164704, 2424236035, 1836213154, 1538237616, 4170351119, 4192031573, + 390499953, 2988910356, 3400473919, 888076298, 489557017, 860982358, 818053373, 1808835849, +3636085944, 2607114655, 1921588514, 3463999470, 565693443, 4175520445, 3526117788, 1594649127, + 70568473, 3058565238, 2986048256, 3246523626, 2730149110, 1031873391, 4268805742, 2706581775, +3669503770, 2961436940, 489060227, 68782034, 1355149022, 1831690694, 1045451422, 905122834, + 684569274, 3344590905, 3097531890, 2249946918, 828965342, 601317021, 2394890487, 254081326, +3576182981, 4143934283, 3829068256, 3671165778, 4055349930, 1364968150, 4032474628, 2868367146, + 619063524, 3588406627, 1098091623, 952676101, 992667810, 1504660756, 1340926533, 171548460, +2610553734, 3012485561, 1995620358, 2108812399, 77263560, 1915202359, 2317016881, 3132491287, +1577577121, 306520376, 3965358816, 3081811116, 315454827, 1649315536, 241436538, 1379616135, +3494098654, 919322873, 1486463354, 1843884846, 2059169473, 2531266739, 2851698474, 3406256737, +2828170714, 4253139927, 865982808, 1491161113, 3584971113, 444497173, 3092037605, 993228645, +3345293317, 1477836007, 1445087019, 874424438, 3602217285, 194339619, 1580385935, 4063263713, +2606681649, 2966838735, 2896667744, 47699414, 1939950875, 2070321037, 1912205427, 3669204832, +3558046831, 1323105224, 257311707, 2603946183, 3465851949, 3833861888, 360150369, 3149058754, +3463638472, 4112703053, 2543737080, 397583277, 604502053, 1603229657, 1935324056, 1807236693, +1346626935, 3946523164, 1576289010, 3401180648, 3178999622, 2334303226, 734366999, 49842954, +2329183529, 2401206115, 1900218646, 811912579, 2381873965, 3253557113, 2043683054, 1059037596, +2620019915, 3787739534, 2808799829, 2349821793, 788406655, 915716846, 3614209989, 2558358123, +1173745995, 3002018505, 3109576034, 1695464125, 1013845959, 1422283856, 187567881, 2162789212, + 688622651, 799491659, 2779213316, 1853043207, 230419435, 2851413717, 1970877872, 268038672, +4043343772, 399182590, 1603319862, 3787602542, 2295436284, 1284612186, 2556313537, 2364445928, +1773768622, 185439529, 3391613107, 1801819795, 1300780397, 3131585052, 290437580, 2838842922, +1406956798, 3345460510, 3986045393, 4065129232, 2358776923, 2519958398, 530694002, 4262815452, + 368788858, 649702208, 3493347579, 294692029, 1945837630, 3584956918, 3053748753, 150239693, +1259908336, 2743081037, 3611517916, 2389715333, 3353697683, 618495178, 524053632, 297421858, +2589871352, 962517594, 3623841819, 2252106915, 549809054, 2321026673, 3956360998, 536096462, +3988046613, 4016590372, 2788521856, 1231556502, 4072281969, 3034647845, 2606219407, 2444712859, +2149884810, 3610471467, 4250853489, 2383363514, 4135781539, 2057293698, 3087235098, 3726080695, +2125868580, 2773824232, 3933721307, 3088580505, 2121577757, 513743429, 2506460865, 4231095932, +1929488295, 3733389343, 2017508446, 3175635075, 3046081513, 2735253602, 1985357168, 282105796, + 780975320, 235667844, 947806684, 1604806809, 408634660, 766114214, 5310261, 3272402374, + 572608268, 140932896, 2361906634, 3973563965, 3206370088, 170780397, 521527396, 2646428631, +3250282972, 880316906, 2687334262, 367486164, 3635372279, 1446816449, 3394235312, 2759550509, +2095789697, 2436196944, 1668142950, 2640077999, 2083848600, 3204207139, 2316969511, 1159733858, + 439166928, 3170932002, 4021704178, 2346628784, 2029389292, 1822484493, 3692242599, 630649490, +3868853245, 3161361567, 3393832776, 1570379983, 801089175, 2435111061, 1460296532, 4165251417, + 770682462, 600225815, 2372297635, 1048065561, 1204249826, 2279810648, 501102604, 3588737188, +2413368422, 552901779, 1536159682, 490295672, 1499004469, 469665784, 2895812770, 2363012186, +1094980008, 3076239346, 135551762, 3413560377, 4050840326, 1756584867, 2812295934, 2909415612, +2802409259, 3520179629, 4186277036, 632130901, 2232346080, 1524844655, 14248381, 1929604678, +2219613235, 1621776739, 3272212736, 2273305798, 1986081484, 271369785, 1379768838, 1274237492, +4043568575, 358687505, 1787062015, 2979876532, 1806110552, 2829677378, 3643388737, 71450189, +3063325376, 4263986621, 2125776504, 2922082315, 2036095364, 2908278355, 776561964, 3238410038, +2606348985, 576655156, 1931423664, 1166391622, 2993377109, 3512520562, 2687138604, 1888739369, +3791697004, 1853483445, 216371735, 2611819934, 4077035670, 4215163848, 684163642, 4063496323, +2309444777, 1992495453, 426722532, 3359952312, 1959799091, 123305166, 3801071257, 975682966, +3018613720, 2918512551, 482465020, 521191466, 862797175, 2093576135, 305251036, 1149511297, +3381066681, 598328431, 2140794128, 1432996683, 2078944511, 1406728184, 3267950260, 3989222376, +1789520784, 3102267643, 58517787, 1493731745, 4192786423, 1109657564, 3967661850, 103860683, +3137646882, 424368603, 1974317232, 1725675522, 2381738378, 879654322, 2152469097, 3249616192, + 942128846, 812309141, 1703134813, 3999546874, 3746823094, 2915923550, 1204544865, 2952944224, +2550561841, 837245153, 531264, 3891174989, 1255647100, 2611213042, 3522917888, 2822145586, + 817628975, 2738086608, 463612145, 3104608521, 2852292096, 1287448310, 627942311, 616308852, +2188060117, 2395173745, 2813615335, 1843987207, 832526903, 1897189470, 3665642255, 713095094, +1152976813, 2258714309, 2898012765, 3399672873, 1805309631, 3398409606, 924698673, 3429714145, + 333839352, 3697582225, 835553689, 3769949320, 3235972839, 293952511, 2647911713, 1530870572, +3481830327, 2358828146, 1167052216, 4210741734, 1515313481, 2985054354, 3093932534, 2209974322, +1300919700, 1202379967, 4254292009, 1799809792, 3840849562, 1844726239, 450690748, 1740257308, +3403574413, 1470019263, 608833589, 3651354686, 45525255, 2868210556, 3666889016, 3440975333, +1682499354, 338749073, 823955337, 2995365666, 524066667, 2065308303, 4285523458, 2111541225, +2005828944, 1372591411, 2576357991, 1103312265, 2813428071, 2690922541, 187312733, 1103130362, + 832252167, 1049347460, 1368512928, 1711907994, 323846934, 1075563896, 2789590481, 656820798, +3639413730, 3693807134, 2955711983, 3057048807, 1548603872, 1519852530, 2725938767, 3444041450, +3329519355, 1281013524, 2795206629, 2061306151, 3924676820, 4261517866, 1894411332, 129358663, +4071693541, 2972457105, 431845280, 4235051532, 1328064547, 3492107614, 678090598, 3188765239, +3809178579, 2691012362, 1078082762, 2799221091, 547728024, 2500678292, 969778023, 532076661, +1091572759, 602065561, 4160227882, 2710987295, 3962738641, 574256633, 3498063174, 1668328895, +2907603990, 3751225315, 1514504896, 3195760849, 278873734, 112532705, 1321606020, 2923405322, +2693213470, 3438181654, 1441495208, 2353434695, 3032676309, 3652787758, 812023589, 4191903605, +3867748065, 431666254, 3178276944, 984064073, 867692640, 297274977, 4011380626, 1780450408, +1441075430, 919828977, 2914827240, 494835504, 2356698298, 1103264231, 4127835959, 1801658185, +3771311839, 913607789, 951012236, 796332956, 2321344256, 1154007831, 235436224, 1467805555, +1247719401, 3398887964, 1254750062, 3318855723, 2300311092, 1027561363, 2042222273, 1577430131, +3894650409, 4240908573, 986356405, 2512010025, 3051160076, 1452960964, 3166873353, 651517154, +1660733356, 3537206241, 3123566784, 3417247784, 2848619886, 1353410982, 1903528926, 1364724892, + 506133011, 2828422429, 86779308, 2898212918, 2368191528, 2652996513, 2179519120, 288074523, +4150380565, 143337579, 3646335052, 822088251, 3394236274, 2028602611, 314322832, 3282652506, +1966714873, 797389616, 2034418507, 3073128509, 820916788, 472674277, 555194163, 2962312095, + 183244106, 3800064318, 2477667890, 1722774194, 453503849, 2886497421, 1966101225, 3085149681, +3694233668, 3121795769, 1399786584, 2934169882, 3656845797, 3472186741, 937680372, 1229082805, + 826982530, 3485966847, 2452339329, 482974380, 1313267457, 2123202716, 1056178974, 2163669545, +3477580761, 1717637260, 3281186509, 2862854120, 2769784490, 3401414997, 2158420696, 2132521908, +2159435771, 4174367710, 2805186126, 645846248, 1092141410, 100596853, 1005421241, 2095075897, +2134456562, 4291286343, 1486768393, 306409035, 720463053, 2311780388, 4171071286, 3811800890, +3932491268, 4156384934, 4268122136, 2623439564, 3024499814, 4019947012, 831636818, 4051511925, + 81701343, 488250690, 1286281617, 3768792073, 2864849423, 3304096264, 910182719, 129553526, +1241799873, 3166605441, 2605721987, 770640714, 4168294850, 2446866840, 491666088, 3080792457, +1000504278, 1219740305, 1374979328, 1391730436, 3390191820, 4169882449, 2115078299, 3346720125, +2264965928, 3342294775, 2442933122, 3446677013, 740767776, 834881845, 2926084923, 2303936411, +1423896917, 4175499030, 1986717536, 2704212882, 3129537504, 3812475711, 1395815403, 714365389, +2544103473, 3039876261, 1902852275, 182854849, 149352451, 513321471, 1384584826, 240384997, +3070691793, 1085898003, 3271180015, 2586671240, 2280448220, 3430167951, 2399842576, 1335646635, + 726478263, 738345531, 1437401151, 3084381644, 3947020629, 3961248213, 1788394953, 2246799440, +3318169369, 793525744, 348652270, 2102692148, 3296882156, 3136990090, 30077241, 2765741211, +2247133312, 1032010678, 3465680440, 2365481775, 396961165, 1754804940, 849178597, 3965717683, +4070784075, 2775771339, 1243703198, 4282456420, 885996862, 2587014734, 93586654, 4038077629, + 568378914, 1772350927, 2871111448, 2643502914, 1464218379, 3782421097, 3215665562, 3468619873, +1959769302, 3734505837, 2509271223, 1327993686, 3041845762, 1350024747, 2989242540, 3369672037, + 755529178, 3154256869, 3807616456, 3623352183, 2255870556, 3420886756, 2108521784, 635991760, + 302023698, 3454690302, 4196956515, 1259900408, 517202990, 4239077682, 781363896, 3541816878, +2862057468, 966473879, 2847364329, 3639277499, 309480636, 3611954221, 281760754, 2115436367, +4290498426, 1619652964, 819341360, 2211316758, 3015450571, 3360462162, 103553250, 1329961326, + 14736507, 3238549959, 3722935743, 377237595, 2407774708, 1230597579, 1512147590, 26439747, +1934753420, 482109479, 1744883098, 3632518563, 2071535733, 2694547065, 30280383, 869877884, +2712636743, 392286503, 1343777668, 3282913356, 931244427, 2032167911, 462177969, 2319635879, +2272354914, 4159360841, 3767186083, 2902289045, 324312391, 1163368852, 3273328211, 425991822, +2327319681, 2110590324, 940400446, 1998926639, 2575079695, 670595044, 3933549759, 4200862461, + 933545478, 2742066386, 839069342, 4289509153, 3595560360, 3041764870, 895429739, 2778318126, +3733229439, 616001307, 1519667499, 4001854610, 4031904338, 3656368724, 2183380672, 3789059180, +2199749732, 869360428, 3870783931, 794356827, 3826783115, 4257595703, 2654016554, 167758688, +1073427158, 725227046, 352594998, 312278601, 2354494484, 533921868, 80336188, 2577734340, +1772182619, 1442224153, 2780805622, 967166574, 2591465829, 1552151656, 3514074141, 2200576696, +1304061987, 4074343903, 2690599768, 1575968537, 1534705159, 3120120914, 73862770, 2681597086, +1468925548, 3106909791, 1900137072, 3817206273, 2016720650, 3836281115, 2132403561, 2749276937, +2305319767, 3025397597, 3438841994, 608748971, 1577718967, 216575840, 2585045729, 1480745161, + 144969153, 2585435662, 1723260145, 3320971255, 3530311474, 3096146119, 1501215459, 3890449573, +1757912055, 1361851341, 3911004378, 1862651079, 4106378466, 3722712421, 2227149775, 1084712791, +1774750304, 257683797, 3063510141, 1390194696, 2317892687, 1415728588, 2989140251, 3960385220, +2779554104, 2346856688, 2403807871, 3460573512, 1676520982, 1073184192, 2601826395, 1759202957, + 802657367, 83101047, 2334908488, 3930421103, 3325097926, 1016619626, 1293664587, 3047286968, +1765900088, 3527763393, 3462559237, 3057056530, 1594713459, 2543687176, 3906651181, 2693919186, + 226354449, 4211697432, 1661344111, 663578686, 2409735618, 1466550926, 1210280723, 2218990501, +3121401731, 1556392848, 4122533974, 3178001755, 68156114, 2344440056, 3664718002, 644900351, +3105959697, 2265906919, 3791884342, 3274218936, 2102062837, 743069309, 2371873335, 1556624435, +1302289109, 90207425, 160278155, 903851437, 3855153757, 2887808539, 2733238082, 373129967, + 424513200, 4283721600, 3671615522, 2068184509, 712430294, 1449738768, 4116299373, 3810470572, +3668928015, 142665575, 1125656065, 3951846474, 3789580124, 3356520584, 2397820953, 859983088, +1009219231, 1936204314, 2402054803, 2787432874, 3375120816, 3389395916, 1530877640, 1303334444, +1288025680, 2882838206, 3369195648, 3130714351, 654254562, 2363203598, 769250882, 3457500828, +3991229850, 4104845622, 4030869515, 1917149164, 3950412656, 2679478683, 671653752, 582726079, +1492946693, 1755064547, 820034901, 3333567415, 2802767707, 1016341192, 2679420209, 4160848294, +1604211390, 2105538272, 4185355119, 2855935120, 2133192665, 2433232514, 987409681, 1075696586, +1962002886, 2768040769, 1930480833, 2409361490, 275288182, 2109556470, 3211302487, 3706550038, +2616293553, 146379028, 4267973763, 4122254800, 321984358, 1842858496, 2372911848, 1074855212, +1098698592, 3751800308, 511503832, 2329864175, 3547924126, 2152123256, 3058309127, 353008119, +1302356436, 4188340557, 652930604, 3176973907, 1613597317, 338659279, 1281308806, 2739101235, +1828789089, 1757379100, 1824951671, 2150538312, 869277849, 2323377312, 2545607567, 4235625919, +2228137866, 1999314657, 1552176752, 2253814894, 344439037, 3190054437, 202875396, 563946144, + 67003968, 3372579556, 1966790529, 4039858748, 1912663738, 52628096, 593549874, 3594180878, +3202569294, 2444117521, 1048538579, 497189557, 617644673, 670613238, 944711874, 3450441114, +2318690224, 4110292171, 3024913133, 1177288957, 4084557520, 1021357516, 3898623069, 4058162358, +1101525517, 422177235, 3746262783, 982007713, 2985461593, 3214191736, 627276451, 72158722, + 87398824, 2452192897, 610984191, 605203593, 3553676501, 1922153880, 1976488570, 1732044711, +2565605205, 1921616472, 3600096266, 271916937, 1957097952, 2872685095, 2723286090, 3606257214, +1802345147, 2080058253, 682538023, 2617277250, 621694752, 703178798, 3944516336, 68308575, +1194897823, 1314376751, 4229904227, 3458766570, 3819967173, 1757520626, 2843605160, 2525111240, +2957257891, 1088500754, 1510119578, 3229809448, 633731697, 1282182758, 2783916414, 977085685, +3289388611, 666599726, 1189953578, 2197193926, 3952487744, 2798824899, 1599913891, 2328507565, +3909113950, 1791138122, 627641229, 2889829160, 45967683, 3435944703, 253823483, 986977196, +1940570007, 1222179373, 4196905454, 550986239, 580754480, 845880824, 163245113, 3321477087, +1475620908, 1599068216, 1981210210, 3036582078, 3243971610, 3025077313, 303232816, 1705661673, +3947971677, 4002302187, 1265774855, 3012976725, 3749312057, 1137432580, 687177145, 2711419115, +4153050765, 2897844195, 822147918, 3809785491, 1083552343, 629938804, 1659041620, 332020038, +1570437067, 1662639795, 4034597698, 2277984812, 2799596947, 3059107375, 3982502207, 3199767877, + 328595767, 1607572427, 4026264074, 2710718992, 1007069933, 477995505, 1580250318, 2349735301, +3649945317, 3145124453, 3709448726, 721854973, 966252725, 3029439936, 2843369940, 956116294, +4168421955, 4033699564, 3871815934, 2853389543, 239852599, 4182417079, 3542635516, 776858861, +2996830151, 26908294, 2329237967, 4272429602, 971853223, 2142851799, 3554661204, 2601579477, +2950689389, 1233007063, 1868207615, 74591221, 1618465859, 1605399910, 1061162474, 3675020450, +4190220696, 334084644, 1079973840, 1070368480, 2753825559, 2139857960, 480257040, 722171016, + 987593228, 2587026174, 2982135595, 2117556190, 436300732, 4156878499, 3156099337, 2692210790, +1765401806, 1334034391, 2186471391, 2042030436, 1812652148, 4105413079, 2592723975, 548854798, +2693569244, 3152360723, 1038011155, 1283047817, 1812508576, 1675824788, 3439736497, 3108748863, +2821429535, 2367302563, 1329626043, 529259241, 3738262615, 213708992, 1857977503, 1537753426, +2199500543, 237679612, 3697445926, 180671464, 952130782, 2993101665, 4222072179, 2003601687, +2716671043, 851021726, 2093834800, 2916745692, 879096174, 1730537519, 4091378303, 4278476606, +1169548170, 806369650, 2498862880, 2358331102, 3545239989, 1875610361, 4083140515, 1337076168, + 152431410, 855933048, 499568413, 371435717, 3413784062, 3031151469, 3359869737, 3124957719, +3707143836, 2764591100, 4201386427, 4024549436, 315491228, 3861304980, 517876119, 3642011859, + 120468464, 2198643692, 3244978061, 464980096, 1542305503, 3711204024, 3562421139, 560337567, +2267562194, 3213970599, 3953987449, 1600288434, 2215505133, 911878329, 653379516, 2441323297, +3239343917, 3708021584, 2780261190, 3494900359, 593963998, 2540911968, 3963978226, 1041230950, +1956900894, 1617761174, 3814357741, 824113666, 1542715914, 355871328, 3994743728, 339408053, +3533860150, 1924597010, 1253594969, 3343048860, 2486924653, 2071524647, 3625547242, 2748632876, +4286610326, 2583502786, 198373047, 1270603819, 4198633538, 2551257173, 3450601167, 2169591845, +2992224560, 2774989613, 3008507315, 1240732429, 3884268810, 147800974, 1953392546, 2388860382, + 284434735, 96159573, 492425096, 3354688792, 236380231, 3058348881, 1049839335, 639427464, +2164295853, 3568868694, 104089061, 3154326130, 4289885112, 1817544535, 3164781522, 1314507463, +2162911442, 3952555128, 2839824005, 3610891508, 3836924906, 505615471, 2706309086, 944495849, + 414819378, 129820439, 560874930, 1305736329, 1584214844, 1806051173, 2969406909, 2991282592, +1021127549, 2516029269, 3494850917, 1152939417, 552357126, 1775350908, 3964224252, 2342227170, +3449603861, 2169378848, 1551937010, 1170544771, 2280951198, 2031787011, 2180009672, 1724768703, +3607830177, 4051929243, 1279281650, 3892934150, 469839832, 3866475927, 4067321203, 2497845369, +3406647924, 559158986, 2771269031, 1642491269, 980693757, 2012280891, 2657458655, 4053479450, + 264235684, 4094703913, 794782762, 2360813623, 1425837132, 4052680047, 3163243210, 822174485, +3468840517, 3665646456, 1985308901, 2260410453, 2161937268, 3101319149, 2857792357, 921431960, +1364928857, 2944914528, 2536409506, 1565376606, 2444403474, 1497647715, 1937731773, 887042111, + 656832297, 127047297, 177586251, 3400966091, 421569086, 1146970515, 2957508153, 1307819588, +3693285165, 2796763868, 285846538, 3628130378, 2956807004, 3889153350, 2727755112, 266429584, +1360218148, 3763797826, 1787514192, 1791191865, 1883759672, 3985708210, 379695292, 2033000991, + 352479520, 831031330, 3185079303, 3036026012, 1790316482, 3158080921, 3953869166, 3711945835, +2753751454, 3756270054, 1009300188, 1266146841, 3740996098, 4232007635, 3889325198, 1657711303, +2357354781, 704870927, 1277982608, 1720523278, 580956779, 3434264225, 2619409451, 3307622822, +4119768478, 3472672286, 1010834298, 3509840639, 400717960, 1626218561, 353386276, 3809030006, +2327624214, 2099890109, 2997939147, 1695588567, 3161263565, 2795549178, 2755145400, 3937798983, +3985893320, 1939255064, 4259199686, 2909033137, 2329195899, 1620997166, 1312949832, 626984692, +4251697685, 957773024, 1949408325, 2759290236, 1521894772, 2726338542, 3491519055, 896474838, +3605921569, 3568336479, 2364468709, 3544500551, 2784326640, 1847706893, 3782805295, 459446095, +1791438494, 307623736, 638906160, 1033792397, 247384531, 1043328981, 3183161238, 2165017105, +2017979494, 2026438149, 3701479393, 668624942, 1151988304, 4071088267, 3062685645, 1576788079, + 944422456, 3015834454, 429171250, 3264681142, 1803019948, 3708148557, 3978583890, 3316944386, +1014123382, 1659509960, 3749863547, 2071852375, 2736680813, 4292340238, 156745160, 1380655402, +2483457380, 2331566762, 2293409056, 516700592, 1145325175, 3947583429, 1543955025, 134010440, + 375233593, 2599119627, 3754516425, 1517199923, 3813438999, 283718521, 4143918099, 2367234983, +2056114045, 4102000475, 4071711513, 3483542291, 2767416531, 944301398, 342668190, 1208360168, +3766124124, 3963373061, 1585714557, 3140266070, 2274820888, 2641051086, 1802674289, 788518517, +1491260824, 1920693947, 4090433219, 1522700421, 1885319311, 936159343, 343103046, 3910754236, +1454265696, 569476710, 17511040, 1280169597, 1992537118, 3972865281, 131709817, 3529509462, +3922482674, 1300683648, 1068145673, 615282929, 2246346489, 2007816284, 2687034401, 1356922551, +2546928916, 4223048571, 3624937846, 2668358115, 211311335, 3367372481, 309849136, 783037816, + 245203374, 1528411347, 3467212872, 1058580570, 943509232, 571714206, 1651982999, 3774077111, +2011488641, 685347607, 799158695, 2263367773, 1092514136, 373513273, 47535651, 357561634, +4184542062, 2595521688, 4220649384, 3270413622, 794737778, 3473569879, 2797993375, 1350439398, +2342847801, 501728961, 4283861170, 3922993732, 4116351657, 481071844, 1148794350, 647012207, +2598455792, 1011790519, 421124495, 504729113, 2695639033, 1809492559, 1536063931, 1959448176, +3945436409, 2365517976, 1805453732, 3457145146, 2318665374, 2915100950, 795492292, 3345840308, +2315178739, 3885587971, 1938643696, 3243743524, 1370859244, 825059175, 484019550, 1800322554, +4023035646, 1742699922, 3561245683, 3723534336, 3909353659, 4174327075, 3551466406, 3243681731, +2216546572, 4255775430, 1734448599, 491435567, 1408175679, 4091743113, 856689436, 3491100245, +1405633251, 2097958391, 1513253953, 439643341, 999706651, 456732758, 144141912, 738605677, + 734241587, 4149874448, 3179478624, 12867707, 3460133369, 1715196940, 301483336, 616824547, +1415263275, 2543628637, 1469845413, 1734266219, 1235557878, 1405745709, 2042082206, 1177759339, +2643209578, 461613225, 2824902910, 1446076118, 1189067804, 3394674693, 2052424018, 3186266772, +3656506187, 3181754381, 3432223514, 1085640749, 1613435170, 3433652338, 3503848195, 1932630638, +2752656452, 2392980870, 2722770861, 2537718127, 525013903, 2395008436, 2974660622, 4255476905, + 715784794, 2245758081, 2203335436, 653443998, 626731283, 3181383851, 2361747743, 4165820377, +4278948211, 3904432443, 2194409862, 3802098945, 2281102801, 3032755548, 2305703150, 746159082, + 558432527, 2475455410, 1129220834, 3042270392, 1351547898, 2244905889, 3698181471, 4048742924, + 79876274, 3551186701, 4093032404, 1744634851, 1824964920, 1032565137, 3225440883, 99060001, +3535057854, 474691407, 2947117952, 647489095, 3416662990, 3047497892, 505052349, 608338149, +1384688919, 3003039801, 3690098999, 1492513485, 1906774078, 3259041512, 3059750237, 3778312311, + 526947409, 1209167257, 3137793299, 643335306, 1301069530, 2194711614, 3820284102, 2027303748, + 184109831, 2600319967, 333805703, 758042696, 4160315559, 1129796959, 2284833319, 954043309, + 872029025, 210556414, 1253616593, 441260224, 103148696, 2480137917, 2298241066, 663276879, +2957447363, 2869488895, 1497144519, 3542300664, 1650398210, 756625301, 731625702, 1664559486, + 74904453, 3612993210, 589768989, 3570141851, 3887956300, 4048533972, 1511341853, 210051158, +2406684093, 1506849863, 1023539346, 3675089315, 2926471878, 3910403047, 551605854, 1826725923, +3518076598, 3660744481, 637171377, 803716290, 620481850, 1278208777, 3229270325, 249237096, +3824603692, 2573709561, 3602880152, 1003990280, 560563842, 2712772825, 3362580533, 1028710294, +3510521279, 3082154114, 3654176118, 925040778, 1325620381, 860894013, 4023362710, 226543301, + 521490450, 249306709, 3845302552, 1755809662, 3397902301, 331889951, 2174479097, 1975781110, +1874825298, 1882501489, 4036138526, 1596649816, 664890830, 3101802194, 767765232, 1052480631, +1944096804, 861837870, 2311678932, 1414396340, 2064397075, 4104834231, 3140966796, 1203582515, +2508353749, 1455194091, 2351648792, 684216444, 1919828405, 3295429650, 4192363843, 879215108, +1657610752, 1744252091, 1768074543, 1017485336, 3996759199, 1329891812, 3260849813, 3746052944, +2685509117, 1349763848, 1571987042, 1291182314, 838944386, 1137981240, 2066209834, 1038397787, +2150125678, 376826883, 2406275722, 1813325545, 3669071350, 1572586583, 1299168286, 4007513903, +2251886619, 3050017908, 2369751448, 894781638, 2053022093, 696499757, 3589411416, 2363129514, +3412831441, 1731672213, 2788122505, 3075853178, 748323796, 1725625687, 1308661510, 3005396175, +4023270220, 3080655048, 1236348416, 2830124309, 3454450919, 4129665177, 1468750768, 2916222135, +3485388163, 1074396243, 2744952730, 2387572766, 2225123700, 3504099258, 3052623359, 885959494, +2692789861, 2724128262, 2220354047, 2086371782, 2479072565, 1073130990, 957750836, 1014462386, +2110447908, 552368729, 2785655318, 2679690544, 374219475, 2274300514, 4050356540, 4244245276, +4257238108, 3745515193, 1220358103, 2681959644, 3694304686, 2431006568, 3899772651, 1498407987, +2912557029, 2374842401, 480959046, 333277974, 3768398324, 1795318460, 3082592903, 2189930723, +4172061612, 3766007129, 3676708660, 2702336570, 673698551, 3758269525, 2490243861, 4084816024, +1798176402, 85798653, 1212588422, 565211328, 1805071281, 3997814968, 3019577964, 3678826393, +2645651314, 2552910321, 3453528880, 3506491851, 2552821673, 2531298376, 2813701660, 526587332, +3809755330, 3584497015, 144604614, 2925288259, 2592196972, 4120842248, 3041624247, 121070122, +1387878991, 2044998309, 3156285139, 1857370880, 2336448249, 3133017236, 609717280, 3706521294, +1714054889, 1352392322, 3283363812, 1593447417, 2785712148, 2473587956, 96084299, 1914966310, +3344429418, 3335969205, 2072751844, 1849330285, 649380201, 3325399810, 2551776815, 2674876578, + 634812362, 2835696254, 1516910649, 3766608301, 2790823422, 428887969, 2131681318, 92491911, +3564363884, 4144560224, 745089072, 1873229209, 2141703283, 2721384217, 2870573035, 105197283, +4088900703, 3828118595, 3697228916, 2569443362, 2502820415, 3052685279, 2340515948, 992706727, +2886260276, 1158554, 2283827288, 85583848, 1099209934, 1217450301, 1913714174, 1229832365, +3535785443, 920464207, 356606094, 1606165161, 3817883255, 2311020264, 396436746, 4128542375, + 483211148, 266389075, 3616065013, 3204520766, 2209463763, 2840456526, 3760251170, 3421066426, +3519480008, 2479573372, 4150381085, 2089255668, 3061756536, 1401780426, 1747044263, 3564014128, +4132761020, 2751234758, 3645608197, 2294460432, 653481681, 3789789607, 1691735688, 3520435504, +2087426545, 2684303365, 1152972227, 4032530450, 1733312636, 1793603444, 3800878707, 39127283, +1165427336, 3942059516, 4008815558, 3841123296, 2875770940, 3540358380, 2486690968, 4245202056, +2009859052, 3691178609, 3021753500, 4266902053, 3992812852, 1991205139, 4176971481, 474669783, + 509400771, 2029404226, 4166964710, 3701821203, 1878929518, 2686394132, 2358492953, 977710276, + 935859707, 2055968417, 2092929390, 1127560894, 2458731686, 2488921432, 884564983, 471687335, +2965041699, 546810479, 4281251686, 3860133708, 4275139573, 4182924703, 2056170723, 2410296883, +2468474797, 986434615, 2751638378, 715223417, 2014636524, 1843504658, 1926014122, 1229921435, +4086492791, 388957634, 1678319118, 148741727, 484916457, 3875731855, 3300353179, 212274072, +3057425366, 405439777, 1891434926, 1657822218, 3561202919, 895309023, 2890289784, 3414325467, +1025877978, 438419853, 309374955, 1898389380, 749334190, 3811121762, 148396338, 2638160192, +4165948768, 2690960287, 2633649008, 2578086934, 3445736813, 2235601598, 706530197, 3626639056, +2263615884, 3026511214, 4167843950, 2848061291, 1400467270, 685961045, 2938931995, 3904057830, +3175662281, 852840913, 3855218630, 2208150571, 973007291, 712425249, 3446437806, 964388748, +3930642510, 2043723476, 456872447, 2126662269, 1183623117, 248498210, 2224787492, 1180479066, +1612046501, 467717373, 2278489967, 2099322413, 2283810783, 4245696768, 655136341, 1565052746, +2367709655, 2705215439, 1548648621, 3304389054, 852414124, 3474906796, 2293073383, 1793497279, +1115240205, 4029707448, 2412296155, 3962683251, 2878462260, 1180358580, 1680033134, 3503086810, +2196018685, 3254264987, 783477949, 932904200, 2900876330, 3105908378, 31153011, 1039774275, +3975490799, 109349830, 2816773123, 2147663342, 863455389, 2897132169, 3051359198, 176210549, +2086991502, 1632275220, 1848643567, 923808875, 4106336824, 2825578083, 431040919, 3336880509, +1186059886, 933523182, 3920522880, 710820544, 2556531882, 3994137175, 2365250212, 169679091, +2563866843, 671716458, 1707738580, 3219258600, 335061174, 3016690405, 3357852686, 2658060486, + 375633784, 1723093476, 904734593, 105759080, 2712196020, 2699656757, 3283506364, 758694971, +2236473344, 526759974, 2660746435, 1589071102, 3029021676, 2432956564, 4270825171, 2209951328, +3413405444, 4218857178, 2031167215, 1543191723, 2083904438, 4076433294, 2926594603, 592785834, + 408391128, 4078875352, 489927657, 964227879, 3219153405, 637249509, 1316059215, 3945134684, +2143107284, 3248254375, 4042697501, 2589774781, 1407810067, 3390158961, 4012408749, 2730335083, + 585199130, 3756549062, 1280727732, 2149773490, 1387455866, 1998368076, 3209263710, 907467025, +1297597586, 3096866132, 1596101399, 3642264594, 1714921351, 322696198, 2856288195, 1218616812, +2664840841, 1190497282, 75110733, 1743348493, 1786044208, 4230932380, 2708608446, 3297357200, +1188034057, 3855005410, 1411535664, 429809575, 177618413, 1899133182, 2812226916, 3061887692, +2697059288, 4192199610, 3698964641, 76909037, 1050341030, 2270700806, 4219833915, 1361170935, +3227270551, 3145265960, 2643913981, 923747001, 3119720191, 2226576536, 2669347798, 1405584583, +2461516835, 1765770568, 3182376262, 2017415024, 4100505242, 791021184, 2610638710, 4172032180, +1781338374, 290129582, 1842349142, 1137182002, 1224611321, 1708382335, 1501673593, 3662337161, + 623795435, 2312461957, 3183440592, 534142814, 313845975, 602336538, 3460704639, 978049982, + 185753026, 1179032956, 3970712362, 4049078247, 3595825775, 2440205552, 4159630164, 2931719926, +1487182594, 1176546331, 1560453448, 3992594599, 1123572449, 3114345526, 528846798, 803107078, + 173152894, 2112839657, 2314228397, 3044874174, 4041341726, 2277512655, 4274203559, 1877677578, +4013814879, 1366335621, 3928867591, 3125929585, 4094480046, 4045710953, 579386709, 792599182, +1985581921, 2964291469, 2481874295, 3957301404, 2516051406, 4211274929, 1941317365, 1899963850, +4131140926, 3210843655, 4212228192, 3017515609, 3926091224, 2835130358, 3178164417, 3091070077, +2948324962, 3074090374, 3240820310, 2438699357, 883638676, 1713621317, 1440908118, 3791819450, + 952913472, 3833193307, 3460872049, 2378812121, 4048880164, 1566020348, 2774219910, 371285363, +3689791533, 2393381001, 3171157926, 2443725773, 2983925337, 4074829491, 2764476399, 2782578253, +3523224752, 2930284238, 3085415252, 1098020641, 764780288, 3184064650, 1724530231, 359738348, + 553414669, 452620307, 379725282, 3660293693, 3438001530, 1518471911, 4047069741, 3269577695, +1290278906, 904116971, 1080256529, 2796580315, 1723820211, 1201512619, 589864065, 175405039, +1861585971, 2677565001, 3670568474, 1924339222, 2964731253, 1516584828, 1557050883, 2681904365, +4068926669, 3738366867, 2214522845, 2503538992, 1337547461, 319325591, 2420991409, 1031588439, +3462472679, 2315735127, 3953676886, 2050886983, 562178341, 4151470471, 2491923876, 1012701900, +2964269886, 2850739686, 907189250, 1553818870, 3906346205, 3098930970, 3917677244, 646647014, + 74578099, 1260007448, 2057182554, 676603716, 4089538400, 2919785040, 3744654344, 2028653635, + 188350392, 3057800600, 2469750759, 3893191424, 883319764, 3939006904, 3823944081, 104150873, + 599126645, 3018243142, 1535975043, 2460322625, 2862235220, 4132006286, 2939249594, 3969513462, + 986543340, 334176536, 1374952380, 513944213, 3204513420, 3376998603, 4126569344, 2289713240, +1391625386, 3726864817, 1921366350, 166233194, 2397505087, 370164061, 1466884271, 689019962, +4065054770, 3195642843, 207711393, 135289216, 2777141332, 4157321885, 3424170968, 838704853, +3281455440, 506395372, 593597960, 3646459323, 2699679868, 4261201693, 2349199452, 3491959556, +1727997732, 2144200642, 1173527226, 2170632678, 703315473, 908732768, 4072603537, 226859933, +1116457819, 4027838708, 1662920792, 1768248637, 541691458, 1470702495, 3072259485, 304905776, +1026727922, 3830738193, 1762184233, 2483090009, 663489335, 693950986, 2285313098, 3459302444, + 759371650, 218201359, 3918032895, 4257310329, 1777163962, 24098608, 4149052424, 3235599427, +2939165848, 1666491681, 2520286208, 3905332934, 3471032594, 1232229632, 2985647502, 2506911896, + 370283476, 1177891818, 2548359083, 3851157668, 2626390979, 3036602208, 1815933691, 598024951, +2251908639, 3279978947, 4083411631, 1135979240, 3871392499, 1217231191, 3012542004, 2674986237, +1364494244, 752421604, 1137479653, 1128059532, 3189309073, 1600636206, 2227360933, 2683767384, +3488034963, 3053840755, 464528114, 4009464122, 3198361653, 3989961348, 1618610696, 1797397491, + 1986143, 1553307931, 2798344663, 3306507073, 3121857543, 300350702, 3921002810, 3837298175, +3536945753, 1663758479, 2089087893, 1048374268, 1810898449, 4243023166, 3468667912, 116073550, +2387854639, 1958779734, 1132720057, 2930978519, 653127934, 845751033, 976281435, 1387003816, +3201661796, 3342477147, 845750969, 3653380631, 4032153528, 3649603612, 3411802006, 3557134610, + 833831008, 3801162093, 3135763668, 785618736, 2614817395, 1916994364, 2058550914, 633275879, +1685512872, 1274573191, 2247602241, 3116930377, 1204488707, 164701521, 3687864374, 1028560494, +2520674380, 4049353579, 914285635, 4275743865, 820857623, 2477241787, 1609856237, 3187279013, +3661550208, 379281984, 698575564, 2859269023, 1976332611, 1466234398, 3390158545, 3923471145, +1091305221, 3635078088, 2253380053, 966052299, 2841942191, 2983401741, 3672977796, 3243939359, + 35000397, 3138797594, 1815276943, 3963001502, 1212946968, 1276144264, 2962355083, 1131185479, +3250448743, 1033643681, 4213428530, 3296586402, 502233425, 752210912, 94149527, 606061503, + 209355808, 3313399652, 1945509875, 1502992839, 3539473416, 3242936365, 260573842, 3358183954, +2323140074, 1189710038, 1919634310, 4027202087, 3710598359, 1660789073, 179928800, 3788575670, +2381785772, 2452118467, 3725906176, 3544304609, 1869780128, 683978721, 3885278142, 422270597, +1099239645, 2490520118, 3433518907, 3617546504, 2764474493, 501894183, 2505240487, 110274289, +2492951913, 3113985195, 3432456868, 1389035111, 2806671028, 1364431989, 3105290871, 57881790, +4287171292, 829906867, 434443982, 3593227458, 1155923428, 4079361396, 715465304, 784863034, +2689750412, 909170243, 3516110212, 3343552221, 2515729246, 4028205678, 3208875920, 1359897922, +1497625550, 2179498133, 1095561816, 3124924825, 81400246, 2804373845, 1856526161, 675025135, + 452186636, 3391939598, 3665219852, 3684544766, 3456729069, 2491828512, 3722018367, 2254982823, +4224087835, 1577746046, 1224859272, 791290043, 1147190794, 669707827, 2750408948, 3409661622, +2509463694, 1519402065, 4083521003, 2242390043, 3918629282, 2981309096, 99504857, 2891618513, + 373329081, 2744822852, 3875115384, 3137923439, 639903331, 2368602703, 491100648, 1069851144, +3595433416, 2536647983, 2696846899, 4243560674, 2588834980, 1805061105, 1421926694, 3311350557, +2858053954, 503964634, 2350822505, 1959983840, 1327911680, 906499280, 2962218398, 2427925905, +3504618792, 3401128117, 73995173, 541550117, 3463469007, 3756664870, 3269262233, 1888713271, +2908552971, 2761396616, 824259301, 2818064173, 2242631615, 2618843010, 2663491095, 2544462935, +2836362790, 942360016, 4049718573, 1075027348, 3506504045, 4035594649, 1413370152, 261464549, +4047162387, 3090716005, 3149852562, 1467694417, 2788637381, 361978775, 647412756, 2336044160, + 448704637, 568049748, 4259947544, 350987281, 637820048, 4081022414, 1058737058, 3036802447, + 463047501, 1120607160, 3273372891, 936939219, 3143293257, 2488318092, 2695419018, 1291529947, + 262205291, 2241503743, 3743594277, 3426385344, 3708623270, 2582785087, 2284333118, 230209633, +3522527186, 2344705038, 3104049761, 1335934201, 318749960, 1400132718, 1360949824, 539537333, +3867432218, 370384008, 2694609219, 2837048122, 3346222662, 411644704, 2814506464, 2006039034, +1257624399, 984460921, 2679424320, 2148573086, 2001666037, 3343754561, 744742423, 2177363097, +4129933641, 1382024884, 2079738823, 40540064, 2550066149, 3701361071, 3249325042, 2376985131, +2416630869, 2878999113, 2282742390, 625256155, 3472512288, 2817244324, 1771546771, 287458868, +3476413286, 1544709148, 2190764743, 2270629202, 1071685627, 214697572, 2734493338, 4287602704, +1300387922, 3744537165, 1994186021, 2285139979, 1013499004, 1349381434, 1791981932, 2355963899, +4090324257, 595721961, 3487173627, 1820638407, 3569648221, 4091302039, 3216670957, 159949253, + 180358632, 2895077714, 111653090, 3431942307, 1975183631, 670784348, 1750706629, 2436919293, +1147643807, 3888123928, 3622659042, 202396748, 4079929522, 168851420, 3833019224, 1994533571, + 223496457, 373460687, 1112276, 1328679087, 162662631, 3539787435, 3201880164, 413778912, + 880126834, 3301347530, 3131921659, 1418953910, 1892537530, 2697329787, 4153636500, 3132175604, + 20723319, 2673550265, 1979989175, 3472380300, 1255846203, 1564118709, 67049946, 2489751895, +1188103475, 2879014587, 2202050546, 4286563426, 3569426419, 3852099048, 1475300199, 1739350008, +1464483565, 3769978423, 2042216937, 2924033872, 4134122137, 1470543499, 4020743226, 3955819058, + 837732727, 2219547867, 2100401344, 2452494870, 3516407011, 3180587305, 1626876042, 1726110023, +1755299040, 1153418462, 143513380, 3506175619, 3503058027, 591055906, 2836991215, 3418161010, +4230281260, 2039250972, 2810118760, 476440202, 4061625612, 2818187447, 2577939906, 2281404122, +1566133943, 242015155, 2282561066, 2149305170, 3551319086, 3595942977, 261189197, 2095809511, +3881673696, 721127113, 4206728060, 3668045492, 1184596902, 1668164640, 628096235, 2764800345, +4215630589, 1615422582, 3424657770, 948677895, 719421079, 1645370445, 1412440246, 403398560, +3767918059, 3715538310, 1157486897, 4118232733, 578257452, 2713307156, 1374110348, 3949989571, +1322421094, 915717319, 299107966, 1061738496, 3476454702, 344497126, 1026621023, 2300461983, +1314640043, 2967, 1709544646, 3599986590, 1463602440, 1777988873, 3471136475, 4174278834, +1748430351, 760487829, 1743620852, 3834377800, 3350910493, 2598803510, 539962768, 1556348384, + 41904128, 1160599966, 2493337106, 2079221261, 1377247768, 3821691490, 3923713650, 3979663372, + 452270259, 2892836364, 3924409149, 3267341584, 3496824916, 3257515537, 4096781178, 2381391354, +2299036395, 159136683, 62764641, 2451264411, 2515570682, 2062802768, 4024620124, 2158976915, +2496922387, 2700682509, 1958788984, 2211797653, 3173554890, 807770854, 4103237775, 1929669932, + 259309296, 1415700416, 4113678509, 4044069833, 2518365188, 3557409268, 3967059116, 470576421, + 468686952, 1854358385, 277114580, 768546502, 1972531314, 1467339904, 1596890879, 3637332181, +3008997322, 3348576693, 4277095951, 1030054706, 1791006079, 3901673063, 2320988187, 438497893, +3816279404, 3541930822, 1943650316, 596498149, 2730573396, 3175831369, 2061500997, 3032084727, + 741518079, 2773255777, 877537650, 2194577794, 96147064, 3577904156, 2547938884, 960341785, +3777155654, 2310768155, 871244185, 922566708, 3306364082, 1376299960, 438469000, 4032704869, +3312923123, 4048437036, 3222220868, 3764672984, 903616390, 3931134775, 1026382561, 983212950, +2138595383, 538994560, 2420134591, 3096417234, 673151374, 856818252, 4177872074, 2552447922, +2086007976, 3524366246, 1156090822, 2455210935, 2970331724, 3004593882, 550144216, 2933205002, + 591141797, 1325297894, 3051949001, 4155553714, 3983198039, 2474666, 811123880, 1898236288, +2989012638, 2983650765, 1363695096, 1966633073, 796494312, 231264458, 4145845521, 68982891, +4139936143, 2420257995, 599932587, 3121555378, 1049004193, 976623736, 1455996300, 400937870, +2965096558, 1584417336, 2545889502, 1744249205, 904481133, 3385783805, 463360006, 905877356, +2769197006, 816400450, 990571597, 303261757, 829135703, 4053106499, 374073367, 2201892580, +2950387191, 2395633172, 4255525944, 829840909, 3513836037, 1960667202, 1900188980, 2220840099, +3451793921, 850835990, 3989281181, 295541881, 98498401, 3889542930, 371813610, 1897735028, +4028816203, 692024650, 3754878655, 3639300823, 240210228, 1804027823, 556911067, 2784664291, +3286295199, 2823785358, 352290137, 633458320, 1061017772, 535139107, 1361983236, 4128058735, +2349854689, 3793320803, 1316860048, 1547700455, 198968577, 790890421, 3157147960, 1953147920, +3488562313, 3966615742, 1421250377, 1570484376, 2541877333, 368522687, 284324403, 4137953845, +4007965956, 3567817008, 4188825035, 1592368847, 2571449601, 1340050607, 198851959, 2136348394, +2302941592, 104957984, 2925502384, 1397302745, 2992950687, 816300155, 1827051941, 2044201575, +1654960533, 1062414773, 2913142630, 2472552626, 1376862789, 709251732, 3059966873, 2623090805, +3309668103, 1106590109, 1312273934, 1742550029, 616925330, 4140700968, 1283233248, 3591986784, +2436172902, 4085854149, 413108065, 3986900837, 1460266535, 3789065417, 4004252828, 2685878805, +1384229466, 2479525058, 1280244220, 2844481581, 2086815440, 3473378717, 3981105684, 1727346803, +2021133706, 33232257, 1073408006, 3320685593, 1309350857, 1153909032, 1308906925, 683878718, + 888402483, 4152465207, 229240703, 2480855025, 1703422679, 3433480694, 1495876462, 319049854, +3117483328, 2557621855, 1384462764, 281703542, 2362767531, 1727442871, 3951820053, 3647518512, +3415045913, 4213538393, 1682162779, 784488827, 2834923073, 2441198674, 3630109321, 3880510901, +2928952893, 2386845309, 1110799229, 1375729101, 701018612, 986397839, 2662330566, 1382590117, +1692821651, 520564658, 2278341264, 1495167050, 162601585, 740910358, 1007238206, 3462567514, +2914027054, 1534658646, 1597846189, 1992612766, 1009936658, 4160339318, 3395668464, 1652163747, +1813823685, 819628782, 339596811, 900830322, 85900135, 322712783, 3941810683, 3626863169, +3742782933, 519092535, 2587789352, 1721773355, 3392454351, 180130217, 2361776498, 2309561340, + 232261362, 3460987305, 4159723857, 3168001322, 1265228139, 994362501, 2067876292, 1679148990, +1113160553, 2898130749, 1151210435, 3356376312, 1818126261, 388498488, 3992869482, 4128198714, + 901478351, 2982313302, 107170708, 4113691491, 4229960800, 3407403054, 3893275262, 2176741231, +4183935425, 3871781816, 2331134927, 106747410, 2533041276, 4249499080, 140503760, 2102940395, +3240225900, 3086730980, 74099867, 1354675769, 3050513381, 2039510517, 1409809049, 1960738062, +4053322091, 3381913446, 929377024, 358073996, 1681459667, 4103288475, 2706088905, 1758956228, +2260244647, 3136605940, 1486634973, 2168542927, 2589564462, 2537155068, 4056883778, 2972305744, +1541433778, 160268492, 3231969831, 979970741, 3354068881, 4017446718, 2080073701, 942821643, +1406227998, 2736080141, 587596928, 1237245859, 3292031099, 398254987, 3786700531, 776991437, +3926518563, 197945513, 2129799844, 3692711349, 2233104369, 2695674295, 1415677513, 2068972511, +1682076893, 845390575, 2092598419, 1357964332, 1207115456, 3291733622, 1509957130, 791901696, +2992810729, 517733924, 4207508411, 312231634, 3889588396, 1166586791, 3077552892, 3732590023, +3865439428, 315119121, 2748906986, 729141560, 3691085117, 4052291406, 2008140295, 2955136002, +1448559608, 3114726255, 3326303125, 2482752523, 3077952794, 1462939033, 4102847857, 233544244, + 111554286, 1125349408, 3521239128, 857292448, 3987456418, 877554760, 2620186075, 1992516938, +1817691951, 100174677, 1229574489, 615691721, 2859034512, 767700046, 378458811, 1285793368, +2035292385, 715540359, 316350162, 508543402, 1630229325, 1078207157, 3762710628, 681200336, +2941317361, 2433495146, 75994767, 4185683852, 2610731581, 2188964210, 1266425890, 2531944050, +1442323484, 739487938, 696956671, 1794414935, 2388048144, 1280157019, 1398084377, 3110733605, + 598048518, 3080622492, 2200393898, 31827830, 70217364, 327303333, 504363313, 548848848, +2170591413, 1357919030, 3865635272, 1172796716, 2278843845, 426220525, 3893164739, 2144284414, + 284595278, 2923570832, 4271930102, 2929971067, 4281092834, 1053953166, 19289123, 3359574301, +2969757626, 2106261262, 4105404383, 2234364257, 601658804, 3930826526, 3231754093, 3275040262, + 420698430, 3994938060, 993685537, 986195650, 2472787859, 986248494, 4131166636, 3834575296, + 771607899, 2012088565, 3224952217, 241009317, 1938007052, 2130219279, 3727254499, 3521204098, +2873783814, 897360544, 2129702285, 159338995, 2475941806, 2310067523, 3947708782, 4130696701, +1099084051, 177295004, 4077432987, 1696276232, 113671999, 2317006361, 3546100020, 1789183913, +2863077772, 383212074, 2947351742, 1153050808, 3232727676, 221783601, 407771697, 261905119, +2442573575, 3926619131, 2405595429, 2193095616, 409477998, 4171800022, 636614037, 2300327206, +2376255059, 3778065290, 237804867, 1422974823, 2011005781, 1269729317, 729180980, 2253323547, +1437066853, 2917091888, 1412232901, 1218215016, 1601565535, 1273084656, 560896250, 1791444915, +3087038401, 1172917144, 1514969535, 918726571, 1236609665, 3204421829, 236566324, 3991263055, +2308175242, 1718827982, 300522104, 1900543210, 3890084326, 3103790648, 326404845, 3146762423, +3564310427, 3832015802, 737286430, 2687620322, 489024084, 4199220196, 550525135, 4054507130, +4219412509, 1053267779, 3129889993, 2271899779, 1088182219, 2090177588, 1907060249, 368104946, +3773890690, 1124792057, 1482390538, 92775216, 1702846721, 290562854, 3666535201, 2838520171, +3366652006, 2219833468, 854716525, 2105580071, 1858577024, 2791414136, 917234603, 1650089064, +3523573766, 2577808206, 684473893, 3412030390, 2416953405, 282929832, 3605234130, 2672768900, + 398047292, 673503205, 2618915414, 1816925167, 2314358467, 3995156083, 2751716112, 3295366533, +3391173784, 3215457744, 472133820, 2186203005, 2241453194, 2078478338, 2202417, 3145338685, +2699363522, 3396714612, 3386088221, 3342101415, 3340185056, 2407534896, 1987823392, 152997691, +3151108924, 3161889456, 1205919379, 2986066200, 1768739992, 1663254951, 3518949367, 3756279819, +2240816061, 1145099520, 260657921, 3347061013, 2193822967, 2600238557, 2309852523, 1255718646, +1226811256, 2634244102, 500070539, 290094265, 1297364095, 3940715536, 2974879673, 3757945935, +1828506660, 2165252781, 1376905001, 2754052229, 3942962987, 3795435276, 2213540793, 3475953341, + 936802338, 3635197568, 1946166738, 1778802907, 1474316282, 3380122903, 2706440397, 860864758, +3319706642, 2376937291, 180283880, 290678937, 28064765, 3418923066, 214519802, 1905329232, +2931489107, 366044560, 2345293411, 258080371, 2812855589, 3927079842, 2114683126, 147857928, +3366718532, 1262251270, 1409146276, 381559734, 1958304280, 3546987184, 3335617174, 3671107724, + 28535616, 3742234540, 3374406338, 2552513147, 3413231888, 3541734750, 1071051032, 2747709473, + 925083633, 1713873234, 1158084700, 598695155, 1509445951, 2107378889, 1684640513, 189066324, +1900525852, 2900923515, 3359347589, 1884873708, 1350407178, 4059386286, 3655920384, 2186569749, + 553172172, 1139672901, 978437924, 1802799282, 548894613, 1030029144, 3467212198, 327763114, +1328808935, 677353406, 778665394, 2448471505, 2235029867, 2030505232, 2850202216, 2869688110, +3916851536, 950669716, 3056990736, 4061680526, 2515453094, 2005227546, 1177145031, 2304887928, +1316943618, 2418027665, 3777840498, 1091910565, 1212007601, 586096126, 3184448977, 1034928027, +2897868016, 3073590475, 1976305207, 3604305626, 732291599, 1459958302, 4088949897, 2232547055, +4190426876, 1300341120, 2212278639, 1071534149, 1487605576, 1816658736, 1851166039, 570145581, +1886148250, 3144484906, 429712836, 1748961378, 1478215945, 405104318, 1407008531, 4210401036, + 707114818, 3108398353, 4078785593, 3938184005, 853854907, 2102932860, 3870035985, 2786277662, + 515142347, 2324449088, 2041171461, 1074470359, 2119866459, 3934997773, 2084187670, 2204460445, +1401303554, 3768960339, 3505481291, 591159472, 1244291988, 1778342125, 93535322, 892652854, +3197118198, 2226939484, 1535102181, 854431857, 3093014721, 316467247, 4052556230, 1689804363, +1726488923, 385582657, 3588313688, 104226930, 1324083918, 2971375082, 272607181, 1579651295, +2739267145, 1067860773, 45278914, 4067170487, 4206943858, 4042786901, 2553940885, 1543523385, +3725630274, 1952240070, 109078159, 3732923938, 2673942720, 3071414964, 3272812151, 3572776039, +3004069850, 63090661, 2388213313, 2160564914, 4174549658, 2768166766, 2096973410, 3643001574, +3845454907, 1646299675, 2977038640, 2656597678, 2868213123, 1063236192, 2029124867, 2155406006, +2763297079, 31509558, 19563559, 1239468048, 2786024500, 3626022484, 2026135033, 2096920323, +3001676444, 4234333758, 1690594798, 1271420219, 2130898596, 2249982675, 1771692807, 992679065, + 916242567, 226294629, 357696861, 742671001, 1765968144, 3934051680, 2359495039, 3454412062, +1208763762, 2890006306, 3284300131, 1144331569, 2835068707, 1137861483, 166582695, 2063151028, +1950375011, 1341816836, 1458041693, 3257542324, 4243461648, 4155201316, 3382298049, 3977382841, +3620756548, 2017781363, 989537388, 2221618789, 42328142, 780323509, 3937275509, 1013428442, +2254956847, 1420434884, 2920855608, 1178259154, 2122449489, 2136988803, 1833851098, 3489243181, +1305569018, 584673930, 1320600810, 3912924607, 3293796602, 1617954130, 2390057758, 957953525, +4258941247, 2314102972, 3586792910, 2226752103, 2173650557, 1382222496, 3582155850, 3155866949, +1366453432, 1942902267, 1304980436, 3749845254, 1805817211, 3748528918, 3317874335, 3516587260, +4215087511, 3088286561, 2951118212, 3833994282, 3235470097, 2831882018, 3681050324, 2248952989, +1693209076, 3703550185, 2892880966, 2944438719, 2812221640, 3632066186, 721762446, 2378302901, + 205110296, 3990083468, 3455651811, 4136532178, 4131253850, 3532423453, 3478988084, 2844801316, + 747201253, 1401218286, 3587227960, 3963081631, 3338974080, 2681872567, 3838278775, 20834349, +2949589241, 3410959433, 2072936575, 1412119548, 3540657766, 4104627114, 3642099230, 2024133264, +1704197734, 1186201562, 2045325704, 3803430885, 1674977069, 546455178, 2287864445, 2703687783, +3411538199, 2063296398, 103963478, 3736006539, 3641345844, 2556183754, 736547502, 4179458268, + 544780179, 2889652801, 1535111001, 2652985185, 2303443189, 960575557, 3670215732, 3303823483, + 625271810, 4053336516, 1819015729, 355941209, 2448302469, 198971091, 2537112730, 1793117107, + 746716927, 3338624956, 1576367872, 1449076523, 2345643464, 307215097, 1382726230, 1347837923, + 778423515, 3474581064, 629229172, 3463053161, 2281422785, 4003447235, 767110490, 1083236530, +2855602407, 432841611, 1677298702, 3811098269, 2912119393, 1574328998, 1798362107, 3668633117, +2271500908, 1297844528, 2566886541, 2329955175, 1296003651, 1072437497, 2136423994, 386324491, +2325626497, 3701869172, 1963284593, 3110155482, 1427631871, 230435716, 3990777428, 2673414391, +1336011713, 3193791649, 2024994295, 1827497208, 2857582773, 1242554274, 2427793715, 3777444299, +3617643108, 3162574275, 1758584003, 368435953, 3652528767, 651249852, 517038258, 3734703249, + 41638563, 3325240455, 1065055827, 1975887109, 2221950207, 4142254856, 3585133222, 2670129439, +3404710730, 583676782, 2933928923, 3149124523, 1702959851, 973784767, 1277067852, 2454509017, + 979153603, 1746228149, 1380282473, 62326272, 2083310099, 3528519614, 4128132748, 300461763, + 214064545, 4145736475, 1279625063, 1862160549, 3630315097, 350584927, 708756129, 1824578695, + 918739052, 1425008105, 213073405, 391242730, 1392974261, 2931873958, 3246454048, 2767720111, + 968857056, 2934199634, 1062628305, 3419637544, 902220118, 3549624684, 3607687155, 1258266708, +4250663348, 3598547159, 1562145095, 2812508388, 3242020813, 623584730, 4129658781, 3633067422, +1216950210, 1475309413, 1085547819, 2934376554, 1938202921, 828799989, 2887678629, 2712566759, +4008837170, 3965633806, 30154425, 1848115865, 2092414407, 2135113030, 860436360, 4105181640, +2905424098, 3334460390, 178557461, 389249339, 2176461913, 1940297951, 455236300, 838226282, + 604029185, 2877027539, 2343082159, 1803306957, 1977342353, 2896425205, 3933843640, 13684181, +2642773714, 3163587307, 3903468189, 1511537583, 3743200267, 3175249708, 1240048776, 1242124, +3730591450, 1427222160, 389439038, 1660501042, 2965566659, 2258562311, 1848430158, 2638210551, + 475822218, 3981752568, 250980215, 2495196168, 2473212219, 3573710958, 1691155262, 3693618250, +2538798270, 161930446, 1423213822, 3599959167, 2172837109, 3200690178, 2017743020, 3446917776, + 572348501, 1192094873, 309104070, 1637333050, 3498135163, 3395323150, 3406944403, 3336470680, +4108740497, 3805475011, 3411741948, 2447640379, 940731212, 3125684240, 1078044905, 3695177153, +2982071866, 777432451, 3128796885, 2987648771, 4220829195, 1058993947, 117414463, 3215928718, +1194067368, 1702299036, 3628545294, 198680665, 3292747524, 24084253, 3910677204, 2046947101, + 743462965, 1983778710, 647877727, 3566938130, 2711792734, 2077397133, 2693408022, 3159845961, +2559355541, 1507688786, 1454738658, 1729607451, 390376811, 1813588182, 778771988, 376437356, +1046284835, 3124318273, 517516764, 2882670188, 430180385, 2863008107, 2683795302, 3337109673, +3079495598, 3383758724, 2144130404, 3297313206, 1120415195, 1332504039, 4243682827, 1519779392, +1660447981, 837418935, 1335486596, 2249839568, 4097051479, 3117639329, 4212978777, 1628620736, +4267278172, 4072933619, 136961373, 1112656096, 4117778225, 1603371193, 1516057704, 1005514379, +3428243799, 2212004835, 2972992500, 1269544444, 4157816278, 1596088665, 3314429965, 3368839966, +2348274229, 1643840451, 4293574783, 3176710902, 2664997276, 1660021252, 1528168824, 2446587321, +1812501082, 2319747889, 4243747622, 2803248535, 1430850478, 3098520392, 3027677759, 500315244, +1467492542, 1594210399, 995390696, 892251272, 466705288, 870343493, 4206756526, 1565837421, +2106843617, 107064511, 2745698070, 2016621469, 3299365264, 1473060857, 491254481, 3580155120, +3545215985, 2849368465, 593299562, 2174771307, 3487062185, 3981983122, 4033026908, 1249710398, +2114341369, 1135815032, 2748913228, 3601662270, 704876844, 3453036479, 823209667, 82922689, +3607364300, 1995495382, 723211454, 2194318348, 709424289, 2248109604, 3611967941, 3086330247, +4205577343, 3239085137, 171493716, 460571102, 1702369937, 512959087, 1567259464, 412732826, +1170756236, 629102247, 1877201272, 1055840598, 351654717, 1665570079, 3765854297, 1267817280, +4069484570, 1882080151, 195073235, 1228566196, 9371250, 1650408147, 1418374822, 1265769686, + 663663842, 4010104331, 289857049, 3795999806, 3116891717, 2896265900, 1089072935, 1579226770, +1460702801, 2616742843, 4193647102, 3360277298, 2244195230, 3661011249, 1986573890, 3868722979, +1825304219, 1429848864, 4166633360, 1800134593, 4071123487, 603518441, 3623340104, 2090999315, +3145145093, 3863399996, 4015514953, 1588612494, 4216906551, 657769223, 320893437, 3837272395, +1395708194, 4260990987, 534247179, 355252762, 2229641041, 1913995424, 2545314512, 3738418234, +3178333492, 1864436699, 2380297097, 2448877014, 782891997, 3197938179, 3549297949, 1746491341, +1159607312, 1668288200, 1201280649, 1335283613, 4113694627, 290239839, 3853284671, 2985711179, +4288413072, 1579504013, 2187139264, 3773288466, 479620012, 538605479, 3684923187, 978908376, +3437314920, 314485634, 1358413672, 3924638450, 4009740074, 1932341692, 110687908, 2731095522, +1597130302, 2003705730, 4286281427, 2344428742, 2925628892, 2811773830, 533116631, 1003255396, + 773581328, 1559806884, 2480489287, 1424979991, 53980393, 1341650252, 1365284021, 979639766, +3663481599, 2018841376, 1029088987, 545355564, 3823568127, 2042823581, 3424068195, 2922724019, +1607207461, 326321946, 95733668, 3096251621, 446144371, 1839530392, 3914233462, 2404001994, + 648272557, 2494207774, 3428967839, 117862819, 2425753752, 192449869, 1082417902, 1249438041, + 459866914, 2027833710, 1111758417, 1705545113, 3338638042, 4256772226, 1058798720, 4158140355, +4157327032, 303934236, 3951170655, 4271208246, 906163167, 2611841755, 2368722803, 2535101318, +2108624568, 2672653290, 2538685630, 3056185356, 2138066339, 1948024717, 779229831, 146291073, +3253525095, 1558175660, 629397520, 3774579247, 4269513529, 3545977500, 888187835, 2938826039, +2782112129, 58561118, 292469522, 458391968, 729703752, 2734273599, 414717513, 530157261, +4016781058, 3251102012, 2996607776, 1021712402, 3179768520, 3933902345, 4204697779, 320457704, +1143923382, 3707415940, 1861276530, 1553133469, 2451462470, 2963693347, 3337912232, 1347636308, +1015912763, 4003256956, 1261882197, 284025985, 348514632, 4002590407, 1507497261, 3254882977, +1872372798, 1303946327, 1719809889, 4111160763, 2409394460, 3852735420, 37716677, 3370706508, +4046771308, 831617372, 1491253546, 3207864748, 3874744174, 2047866311, 1122380277, 2869586906, +1732322251, 3331656256, 2762571901, 2148455358, 388615138, 1374363706, 3046722866, 1386784815, +1499293446, 4260380283, 2299125624, 1113742272, 4143521957, 1645791836, 3848698501, 535196157, + 54002792, 3407448387, 2209566753, 1160507355, 3837397307, 3754294091, 1862264483, 4031289362, + 954012246, 927023337, 4020526988, 1537070109, 1223206626, 4071687676, 1440188014, 3723195393, +1522759449, 4186910581, 3367699017, 2274489300, 2474204151, 991286736, 2632095310, 4147949411, +1467954721, 91683811, 1939448612, 146099855, 48803181, 2896399124, 300139235, 3130888524, +1201485607, 2991581332, 742573058, 2290328692, 3104701535, 1439895581, 976715979, 333812726, +3617742573, 168515407, 3707044184, 688342501, 772868043, 9064101, 3984181250, 1583910619, +1984591106, 1914430057, 4078267829, 2589719936, 2682907107, 3607578386, 2229334154, 1718837793, +2614439707, 3007382125, 4085085239, 3196945561, 4107046492, 1956298772, 2525801253, 1266662716, +3024027302, 1633017067, 228039527, 2828753945, 4292760697, 518382945, 4208724714, 4254281626, +1730677191, 3961649204, 280595809, 940435433, 1141090467, 3666791718, 2042347891, 3931209774, +3607735489, 154794599, 1164005319, 2392871177, 1313582464, 3396667971, 312884744, 1465927447, +3270010390, 2571001774, 3848848317, 695202814, 2515580846, 1099677535, 4153338569, 2279832106, + 498031116, 4124446604, 1279079844, 2045433826, 1985257780, 1332172881, 2437761079, 3424952108, +3250939926, 2378427436, 4287785002, 2152045200, 4169322900, 1556189751, 1220375688, 2753914352, +1165124760, 1196242365, 1954626556, 128606264, 4111209914, 2204933102, 2875876891, 279053174, +2571968163, 455980676, 2411421064, 2236258504, 3289079113, 894578745, 4071837109, 3466702129, +2936605186, 2088352386, 2976589923, 324750119, 2593455627, 4103305788, 3674442123, 2248453121, + 777441147, 1630216955, 3791046640, 1902354302, 2277543476, 4036543606, 471722852, 2367279353, + 344072913, 3396290385, 2911224377, 570033009, 912779250, 602928217, 432436612, 2650622551, +2598822449, 2334386694, 483558920, 2046314573, 4021377867, 2479151537, 1616873198, 2956133068, + 277639859, 2279128306, 2319273699, 2328809556, 3256848644, 3155540300, 1255775357, 3977137046, +2791575279, 464984386, 1462480274, 3172281737, 321961165, 3871890665, 2098766893, 2420300653, +2490195483, 4294637405, 4220678954, 1156365454, 4258871321, 4294791682, 1152359808, 150850049, + 43829809, 3600414148, 1822979875, 2094923910, 4176627919, 868653570, 804328342, 4433340, + 804799633, 708369185, 3321428454, 125647236, 1752316021, 3313391850, 2144157908, 3117112549, + 605838744, 561130251, 3444958634, 3830836825, 1775839606, 3351774814, 778105422, 1477208535, + 982679184, 1441031627, 4253408588, 1591972142, 187548007, 2597412792, 570084368, 1762198564, +2123309806, 2117930162, 2015539282, 1453463748, 454451938, 2011698593, 1193086502, 279055100, +1791726579, 290061065, 1381509677, 3845772914, 1545335611, 2391160479, 859699721, 273687362, + 230182367, 1696384612, 2486152046, 2537734267, 1128123011, 805154281, 240825225, 3390780057, +1181925148, 758446167, 1247720489, 3740438113, 1588837817, 843146965, 2819645278, 48055415, +3715251913, 3056489410, 2039950633, 314907227, 3106462648, 2558603899, 2128152185, 4263753100, +2663102624, 2943592806, 2184077754, 257344063, 3672373406, 3502999603, 2111798873, 3369632437, +3473233347, 2870642506, 2056689202, 176671711, 1700676340, 1603942866, 188553483, 126386854, +2258411480, 2714216814, 3559900453, 840261495, 24026567, 4247391239, 980936218, 3998960728, +2167495789, 2518201133, 3021416510, 572338041, 198922032, 36190633, 1994710415, 949130638, +2500093513, 377840054, 442993577, 1154552612, 133737703, 3668548033, 601920126, 2413244696, +2662780264, 2310821632, 2724894439, 80733236, 3901004513, 3472454963, 1503248595, 628388502, + 642396490, 1969342326, 1703840199, 1631247024, 3408827085, 1816611186, 4209100907, 690583402, +1238021801, 3791998262, 583014872, 2232544925, 3479858700, 1154152998, 4068754090, 1277040292, + 458181447, 2145388269, 4070466616, 3048402638, 292620105, 1439411906, 1873996649, 2513889943, +1896453783, 105581677, 4030996316, 2734534318, 3858733193, 3690667636, 2400070515, 2958461742, +1303468267, 2120891514, 3943230017, 1822121834, 3815977146, 3619968152, 428431177, 2290823027, +2219524110, 158556923, 275495059, 1180659330, 2945127002, 412317908, 1121507273, 558622647, + 58834349, 3564163049, 1424375676, 3914071244, 180736543, 429107794, 836932016, 3030555461, + 65794026, 3453227869, 1205223041, 1965324808, 3582553484, 3639143276, 3387668149, 2152295494, +1031340226, 3263567687, 2755952631, 370206691, 279334625, 3477544087, 3394064603, 581885958, +1361722640, 2777024042, 2831342605, 1501257895, 1443424349, 1955796363, 1187342255, 3749328734, +1058822498, 3321679173, 156626257, 4186480621, 485302380, 1606707062, 4045027318, 3421709114, + 334750189, 4252070441, 2596552769, 87956336, 2581669268, 949362227, 3179203808, 725352749, +2479986317, 3417290512, 2921604368, 1866733329, 2441698714, 2274730484, 331516612, 3603178415, + 448271693, 1478069821, 2720213480, 3583602455, 1292129627, 4108386355, 3116636164, 1361876061, +2904952642, 3312182331, 1976967938, 2182208357, 3398984472, 2477914849, 1621042189, 3532758925, +2645417318, 4075684795, 1480056795, 3361891550, 667787349, 1022664307, 1150536596, 778285002, +3429092426, 3081669198, 2116085119, 2653939895, 2446285937, 55009414, 316976304, 1754719966, +2383427958, 2066121599, 3506149962, 4046075821, 3381809206, 2518617952, 872580284, 3639537344, +1796351044, 1715209730, 1926649353, 3391755854, 2685952136, 1426155247, 359893939, 1127491585, +2452436914, 681065343, 2604219718, 3107109441, 3674605047, 3219943288, 1199157163, 339454174, +4101272408, 231960037, 3479483017, 3057826796, 2370159116, 1003847269, 487937203, 3516173930, + 801511852, 4186602477, 2754406509, 1245423864, 973672497, 738821512, 726665837, 3467311117, +3006986499, 4151684781, 4166722293, 1058297775, 2151061373, 3538512931, 419391003, 1537101277, + 885450269, 1749794725, 1493960722, 3273090010, 2914768538, 4026605717, 267613602, 556467205, +2978940594, 882886563, 1226122675, 3008709995, 3972717731, 382899013, 3062826208, 1672560388, +4001846814, 3693908619, 265798740, 3112182172, 1748843044, 1732362988, 3389268005, 344822466, +2029970742, 1881825612, 2250826865, 672219379, 1473252296, 3950089955, 3708065178, 3628342324, + 561062747, 954641965, 4080406914, 292345600, 346569730, 2062444159, 3846430689, 3384108213, +2913572322, 3244458095, 4068331906, 2174839721, 3476958115, 1056182415, 2651470110, 3385517048, +2219834580, 1179973970, 2752224554, 965899504, 3306395909, 96342625, 176954421, 2613206946, +3635952366, 2000725452, 38298391, 118538050, 1677893057, 2794412766, 2443247622, 325983301, +2731168782, 2002972734, 1676682595, 777188982, 2223504287, 101930638, 1771714159, 3765931304, +2664867842, 921678204, 2154588887, 4068904570, 3688040505, 1984045073, 2516439425, 3128401773, + 279357751, 693668883, 612430782, 2557724708, 770497725, 3572788003, 2247200624, 3186641799, +1939834195, 3491366668, 3855347497, 881282772, 976188350, 2127994350, 1899121226, 1029864746, +3261242309, 1610022236, 4287552812, 591146349, 3288825393, 2885577824, 693671175, 2198146202, +3366117624, 3715725779, 3046072502, 1071371513, 715649716, 2141566112, 2221004985, 2948716359, +2795633792, 900691684, 131001344, 2941498872, 4077294323, 4049704593, 223594679, 99477202, +2132218011, 4087984319, 2185949019, 4187046231, 1871555796, 2405525050, 530794570, 1243981715, +3387661484, 2060416675, 3228062576, 4129047041, 2397012740, 3929349751, 1213596515, 3201151056, +3982379635, 1467032715, 3102000570, 61337987, 3622289137, 1493463473, 2786663303, 129688670, +3762799531, 2534264179, 1491485731, 1863602456, 1189018971, 473131398, 3562246345, 1872894391, +2734011256, 3233886914, 3054904617, 1323791086, 991322019, 2641557288, 1860897847, 2230047857, +1509164406, 403979741, 930800279, 4214300394, 1015503055, 3114398730, 2207867140, 2852530037, + 49844555, 3182290438, 3989115068, 1242387395, 1534585672, 2077478052, 2859309457, 608462283, + 446139448, 1111085484, 996872832, 1698094435, 1644738546, 3114144037, 608543695, 2767235876, +3718043650, 2143621548, 2367195334, 1830330653, 2507360319, 3668653137, 141461036, 3692379147, + 471208272, 1260121168, 2261864183, 69477129, 3579673125, 3665936509, 1624575673, 1030224712, + 742188741, 1009887515, 3874213008, 2940832530, 3265868232, 2143817440, 2415303525, 413685933, +1333789844, 3697450569, 2873203619, 2481979410, 189305283, 1488791252, 3663629737, 1189084043, + 352310595, 551475032, 389783930, 3202157952, 2103520359, 2530207139, 744869053, 2041067217, +1573162046, 275937492, 3221808279, 3720343563, 2040151720, 3537689552, 3729436874, 347682566, +2126377759, 2296164625, 3105626614, 3627045114, 1076036535, 693965643, 3210693647, 2915109522, + 925289687, 497754043, 3230351564, 131719069, 1803969880, 1695257039, 1722812556, 2184552212, + 804457759, 874258857, 2212096374, 3537933879, 1817047611, 3669358548, 1242254247, 3985001334, +2551638366, 2099446608, 3597828854, 2172002871, 2292242005, 3070241737, 2075185675, 4054517158, +2676812115, 2470924989, 1095734874, 563081707, 237508615, 457145542, 866589101, 2322514036, +4029725248, 4040219387, 1525811016, 960508495, 2330273694, 1740040894, 2089513301, 3337711909, + 722563159, 1548739748, 2150131, 3835991314, 3472013982, 1138539359, 3500447816, 122004483, + 412375466, 261192122, 3863709492, 4148908864, 844018603, 1096465482, 3481916370, 3190572791, +3629692482, 1061893487, 1185595079, 2357997153, 1096442749, 557130428, 2793480834, 4244039753, + 735084915, 3558036709, 3669529907, 3961060015, 624979268, 4075491747, 1995882552, 2698241010, +1057521581, 708458335, 3895784796, 1677613852, 3726170897, 531096450, 1860272039, 2660672430, +1764607627, 1918407455, 3597864467, 2667247302, 2076096964, 4272881370, 3750708081, 775039921, +2021250817, 3505954603, 416279287, 2599899233, 4123482069, 3133920606, 2350319959, 3371910552, + 564538792, 4177926190, 1137405670, 548119003, 3431794706, 4048113063, 337008772, 3705481027, +1488699589, 2161427903, 3302845108, 2466523920, 264798046, 3326133682, 3470213373, 720618237, +3763224664, 2328086283, 3254520867, 596731144, 3303036976, 567404398, 3205941143, 1796428292, + 695413060, 134834108, 1848829159, 2550596556, 1186411946, 936928874, 1720236797, 3387656213, +3906833270, 2108833117, 1290111523, 3674237173, 3218519108, 2332742117, 2418423806, 3251928205, +4009569811, 3816455248, 3087804776, 4081653513, 427141885, 4102602521, 2602398142, 698007959, +1256345206, 2472380220, 252576272, 2761824905, 3092537739, 1578115681, 1019980992, 1718903451, +1345482200, 1313052862, 413031920, 958760926, 2063943847, 3208330727, 3076228206, 3231980090, +2393399367, 2354848496, 2331089771, 1729555640, 4022341384, 2109673359, 669271632, 980682459, +1079180689, 278762454, 388023128, 4106609363, 1069417182, 96476240, 4242737617, 4049537867, +4028367605, 3259865452, 608503204, 2963045738, 370549052, 3865835813, 1857565240, 4221843674, + 368507839, 948521195, 1853712821, 1069103955, 594262111, 2469896527, 2597423739, 4086751207, + 141976301, 1648950409, 849099313, 1672808368, 3881806569, 1150675744, 1397881617, 3670561111, + 772409669, 1529132227, 777249769, 801633607, 804544070, 525545584, 3783789727, 1599103033, +2858778874, 477254510, 2578045920, 1358327399, 1956665283, 2271498821, 2392072170, 1373030463, +2094211039, 3014392950, 2887858017, 514659278, 4081092517, 2638176875, 2811907741, 1872670426, +3930906699, 685775358, 2950100308, 2723323695, 2512373768, 1279162261, 2338891682, 2627434116, +3887968197, 3009569734, 2543900375, 3574392346, 2108132621, 551641329, 2951846923, 1025261583, +1048590243, 279359155, 1202363566, 3302907874, 423218900, 4051583039, 127436024, 732793937, +4113853920, 4249140965, 1314587480, 1160020626, 3698439460, 775793520, 2510115514, 596538756, + 266082182, 1577599296, 1230363127, 1172195994, 3464525211, 4088431155, 3629083433, 1051721390, +1971752472, 3064581084, 3907777680, 4257012065, 3614145053, 4072282807, 3577254387, 2895779857, +1738592193, 2473456565, 1950491635, 3223890727, 2074935096, 2500077916, 2374504773, 1374431698, +2605278682, 73830924, 1792538917, 491110152, 3451394027, 2864743086, 4135333650, 2873789071, +1142380211, 2327302589, 2387580271, 1550802558, 1361725818, 3556798435, 1313623293, 3085154546, +2363773442, 3817142864, 2153074884, 730977362, 3719696688, 3396611510, 1965057039, 981026918, +3008817889, 3580670463, 2140951395, 3774603245, 2978847975, 3121750048, 2863039900, 1887402398, +2859258502, 2718730260, 2052394963, 4142241734, 1051891231, 459397278, 740478943, 673836180, +4069423969, 1567249566, 1557578961, 108545236, 1757996272, 3047437243, 3157914198, 1952283072, +1040616676, 1005677544, 1280047612, 4179006074, 1173501301, 3857413634, 3183450303, 174698069, + 671520599, 4048585645, 2035230445, 323006643, 2713425215, 640501002, 72064140, 1338477212, +1653543712, 117573592, 544968678, 3675948139, 2507560617, 479065349, 198550260, 3539160711, + 618587400, 2853187710, 3697999642, 117915097, 1808271686, 2993668361, 551984991, 2057748227, +3783827989, 1810196271, 1788919767, 2586426648, 2200150454, 4110225173, 3960463375, 3822734445, + 529666841, 2513508998, 2742803689, 541024503, 1354838087, 3184690129, 3230939070, 2798423022, +3898375327, 4215526638, 1285861589, 3752146130, 2018488271, 1645799025, 43587063, 3609363243, +2625637001, 2351357639, 3986690511, 2519420519, 2423690995, 897376981, 2345923579, 278495054, +3075980586, 1160720989, 2380324453, 1243878687, 2218641372, 3197107508, 3277472324, 2430159271, +3713877740, 3613836327, 949540070, 3550241140, 357354135, 3623178950, 762580355, 22581509, + 559405289, 3603287672, 4022515133, 1195773986, 282155245, 3282605611, 3302663908, 1041906275, +2113415807, 505663307, 35561439, 340926442, 4082726944, 1841708663, 4149920300, 2792286214, + 900618765, 2693030827, 4200334318, 2305682068, 1369609103, 2060682767, 1725756752, 1481448724, +2595762353, 1880336987, 2001415811, 527015876, 4104982805, 2517815408, 800036145, 724798806, + 635924342, 3989608361, 1140640754, 3880118953, 1177854902, 3001625220, 2400870789, 3789955657, +2068287459, 2915183132, 3360991626, 2877478405, 3892778026, 1144107253, 2850097915, 908433824, +3596045042, 3695740896, 3401721361, 1968485291, 3782258869, 2529441713, 1455559393, 2177101006, + 675470118, 1377037359, 517152126, 3181811853, 768334826, 2262779164, 1555845620, 3771830146, +1859305029, 3231536701, 2749860078, 1130357833, 815220329, 1369565803, 3348965884, 2495361219, + 648421962, 3702863288, 2880734890, 3934587665, 529258747, 2598301656, 2536836364, 4259289151, + 96979922, 1706759323, 1984527305, 1912540453, 4274888083, 721838232, 1708859618, 2300813870, +2044343635, 368301520, 1542515647, 782364374, 1674131496, 48843978, 2767832002, 386682217, +3163766886, 679611784, 974807258, 3413092173, 834866911, 2683495981, 2773351223, 2486051955, +1796630775, 424331654, 1832729113, 99198163, 1309013885, 3759543349, 1046351754, 3951405423, +1627967311, 2163811005, 4283661448, 1678279946, 1877214637, 2181668505, 1765312347, 2390621580, +3234659069, 1076905053, 1190616880, 1306098616, 1854543338, 1273861087, 3100396888, 3913332153, +1181434101, 3301518017, 1637220885, 1034067281, 3871825611, 4272850332, 1747719371, 2476663221, +3740316383, 3270526613, 1059228594, 857016992, 1973435789, 1531127920, 597456949, 328315692, +4115723891, 542535403, 2961742314, 3412071716, 3280087651, 4022734271, 580248715, 4197594504, diff --git a/rngs/fixed.h b/rngs/fixed.h @@ -0,0 +1,13 @@ +#ifndef _FIXED_H_ +#define _FIXED_H_ + +#include "intrinsics.h" + +struct RNGFixed { + u16 index; +}; + +void rng_fixed_init( RNGFixed * rng ); +u32 rng_fixed_next( RNGFixed * rng ); + +#endif // _FIXED_H_ diff --git a/rngs/genfixed.cc b/rngs/genfixed.cc @@ -0,0 +1,15 @@ +#include <stdio.h> + +#include "intrinsics.h" +#include "well512.h" + +int main() { + RNGWell512 rng; + rng_well512_init( &rng ); + for( int i = 0; i < 8192; i++ ) { + printf( "%10u,", rng_well512_next( &rng ) ); + if( i % 8 == 7 ) printf( "\n" ); + else printf( " " ); + } + return 0; +} diff --git a/rngs/mersenne_twister.cc b/rngs/mersenne_twister.cc @@ -0,0 +1,184 @@ +/* + A C-program for MT19937, with initialization improved 2002/1/26. + Coded by Takuji Nishimura and Makoto Matsumoto. + + Before using, initialize the state by using init_genrand(seed) + or init_by_array(init_key, key_length). + + Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + 3. The names of its contributors may not be used to endorse or promote + products derived from this software without specific prior written + permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + + Any feedback is very welcome. + http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html + email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space) +*/ + +#include <stdio.h> + +/* Period parameters */ +#define N 624 +#define M 397 +#define MATRIX_A 0x9908b0dfUL /* constant vector a */ +#define UPPER_MASK 0x80000000UL /* most significant w-r bits */ +#define LOWER_MASK 0x7fffffffUL /* least significant r bits */ + +static unsigned long mt[N]; /* the array for the state vector */ +static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */ + +/* initializes mt[N] with a seed */ +void init_genrand(unsigned long s) +{ + mt[0]= s & 0xffffffffUL; + for (mti=1; mti<N; mti++) { + mt[mti] = + (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous versions, MSBs of the seed affect */ + /* only MSBs of the array mt[]. */ + /* 2002/01/09 modified by Makoto Matsumoto */ + mt[mti] &= 0xffffffffUL; + /* for >32 bit machines */ + } +} + +/* initialize by an array with array-length */ +/* init_key is the array for initializing keys */ +/* key_length is its length */ +/* slight change for C++, 2004/2/26 */ +void init_by_array(unsigned long init_key[], int key_length) +{ + int i, j, k; + init_genrand(19650218UL); + i=1; j=0; + k = (N>key_length ? N : key_length); + for (; k; k--) { + mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL)) + + init_key[j] + j; /* non linear */ + mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ + i++; j++; + if (i>=N) { mt[0] = mt[N-1]; i=1; } + if (j>=key_length) j=0; + } + for (k=N-1; k; k--) { + mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL)) + - i; /* non linear */ + mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ + i++; + if (i>=N) { mt[0] = mt[N-1]; i=1; } + } + + mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ +} + +/* generates a random number on [0,0xffffffff]-interval */ +unsigned long genrand_int32(void) +{ + unsigned long y; + static unsigned long mag01[2]={0x0UL, MATRIX_A}; + /* mag01[x] = x * MATRIX_A for x=0,1 */ + + if (mti >= N) { /* generate N words at one time */ + int kk; + + if (mti == N+1) /* if init_genrand() has not been called, */ + init_genrand(5489UL); /* a default initial seed is used */ + + for (kk=0;kk<N-M;kk++) { + y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); + mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL]; + } + for (;kk<N-1;kk++) { + y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); + mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL]; + } + y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); + mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL]; + + mti = 0; + } + + y = mt[mti++]; + + /* Tempering */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680UL; + y ^= (y << 15) & 0xefc60000UL; + y ^= (y >> 18); + + return y; +} + +/* generates a random number on [0,0x7fffffff]-interval */ +long genrand_int31(void) +{ + return (long)(genrand_int32()>>1); +} + +/* generates a random number on [0,1]-real-interval */ +double genrand_real1(void) +{ + return genrand_int32()*(1.0/4294967295.0); + /* divided by 2^32-1 */ +} + +/* generates a random number on [0,1)-real-interval */ +double genrand_real2(void) +{ + return genrand_int32()*(1.0/4294967296.0); + /* divided by 2^32 */ +} + +/* generates a random number on (0,1)-real-interval */ +double genrand_real3(void) +{ + return (((double)genrand_int32()) + 0.5)*(1.0/4294967296.0); + /* divided by 2^32 */ +} + +/* generates a random number on [0,1) with 53-bit resolution*/ +double genrand_res53(void) +{ + unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6; + return(a*67108864.0+b)*(1.0/9007199254740992.0); +} +/* These real versions are due to Isaku Wada, 2002/01/09 added */ + +int main(void) +{ + int i; + unsigned long init[4]={0x123, 0x234, 0x345, 0x456}, length=4; + init_by_array(init, length); + for( i = 0; i < 10000000; i++ ) { + int x = genrand_int32(); + printf( "%d\n", x ); + } + return 0; +} diff --git a/rngs/well512.cc b/rngs/well512.cc @@ -0,0 +1,44 @@ +/* + * WELL512 PRNG written by Chris Lomont + * www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf + */ + +#include "intrinsics.h" +#include "well512.h" + +void rng_well512_init( RNGWell512 * rng ) { + // generated with + // for i in (seq 1 16); od -A n -t u -N 4 /dev/urandom; end + rng->state[ 0 ] = 3485465937; + rng->state[ 1 ] = 619988921; + rng->state[ 2 ] = 1151619954; + rng->state[ 3 ] = 1259802506; + rng->state[ 4 ] = 2391016736; + rng->state[ 5 ] = 1833603341; + rng->state[ 6 ] = 3529478173; + rng->state[ 7 ] = 2843655677; + rng->state[ 8 ] = 1227810011; + rng->state[ 9 ] = 3849695542; + rng->state[ 10 ] = 3734095823; + rng->state[ 11 ] = 582871035; + rng->state[ 12 ] = 3217102166; + rng->state[ 13 ] = 1925191046; + rng->state[ 14 ] = 1602871528; + rng->state[ 15 ] = 1661469209; + rng->index = 0; +} + +u32 rng_well512_next( RNGWell512 * rng ) { + u32 a, b, c, d; + a = rng->state[rng->index]; + c = rng->state[(rng->index+13)&15]; + b = a^c^(a<<16)^(c<<15); + c = rng->state[(rng->index+9)&15]; + c ^= (c>>11); + a = rng->state[rng->index] = b^c; + d = a^((a<<5)&0xDA442D24UL); + rng->index = (rng->index + 15)&15; + a = rng->state[rng->index]; + rng->state[rng->index] = a^b^d^(a<<2)^(b<<18)^(c<<28); + return rng->state[rng->index]; +} diff --git a/rngs/well512.h b/rngs/well512.h @@ -0,0 +1,14 @@ +#ifndef _WELL512_H_ +#define _WELL512_H_ + +#include "intrinsics.h" + +struct RNGWell512 { + u32 state[ 16 ]; + u32 index; +}; + +void rng_well512_init( RNGWell512 * rng ); +u32 rng_well512_next( RNGWell512 * rng ); + +#endif // _WELL512_H_