mt_srand with array seed?

On 8/11/16 10:13 AM, Lauri Kenttä wrote:

The second question is controversial. People have asserted that nobody does statistical work in PHP, or that if they do it's not a "legitimate" use of PHP. There were demands for evidence that anyone has ever legitimately needed to seed an RNG in PHP. I disagree. #32145 in itself is sufficient for me. For statistical work 2^32 starting positions is not enough. MT's period is Vast, like Dennett's Vast with a capital V. Nobody needs *that* much but if MT is what we've got then it seems reasonable to allow access to more of it. mt_srand() will work. But what would be in the array? Integers from which the upper 32 bits, if they exist, are discarded? Tom

--- ext/standard/basic_functions.c | 5 + ext/standard/mt_rand.c | 67 ++- ext/standard/php_math.h | 1 + ext/standard/tests/math/mt_srand_array_basic.phpt | 146 ++++++ ext/standard/tests/math/mt_srand_array_values.phpt | 532 +++++++++++++++++++++ 5 files changed, 750 insertions(+), 1 deletion(-) create mode 100644 ext/standard/tests/math/mt_srand_array_basic.phpt create mode 100644 ext/standard/tests/math/mt_srand_array_values.phpt diff --git a/ext/standard/basic_functions.c b/ext/standard/basic_functions.c index ef628cc..bcceb20 100644 --- a/ext/standard/basic_functions.c +++ b/ext/standard/basic_functions.c @@ -1891,6 +1891,10 @@ ZEND_BEGIN_ARG_INFO_EX(arginfo_mt_srand, 0, 0, 0) ZEND_ARG_INFO(0, mode) ZEND_END_ARG_INFO() +ZEND_BEGIN_ARG_INFO(arginfo_mt_srand_array, 0) + ZEND_ARG_INFO(0, seed) +ZEND_END_ARG_INFO() + ZEND_BEGIN_ARG_INFO_EX(arginfo_mt_rand, 0, 0, 0) ZEND_ARG_INFO(0, min) ZEND_ARG_INFO(0, max) @@ -2856,6 +2860,7 @@ const zend_function_entry basic_functions[] = { /* {{{ */ PHP_FALIAS(getrandmax, mt_getrandmax, arginfo_mt_getrandmax) PHP_FE(mt_rand, arginfo_mt_rand) PHP_FE(mt_srand, arginfo_mt_srand) + PHP_FE(mt_srand_array, arginfo_mt_srand_array) PHP_FE(mt_getrandmax, arginfo_mt_getrandmax) PHP_FE(random_bytes, arginfo_random_bytes) diff --git a/ext/standard/mt_rand.c b/ext/standard/mt_rand.c index dde9a77..04e83dd 100644 --- a/ext/standard/mt_rand.c +++ b/ext/standard/mt_rand.c @@ -151,7 +151,10 @@ PHPAPI void php_mt_srand(uint32_t seed) { /* Seed the generator with a simple uint32 */ php_mt_initialize(seed, BG(state)); - php_mt_reload(); + + /* Reload the generator when mt_rand is next called. + * (Reloading immediately would break php_mt_srand_array.) */ + BG(left) = 0; /* Seed only once */ BG(mt_rand_is_seeded) = 1; @@ -209,6 +212,68 @@ PHP_FUNCTION(mt_srand) } /* }}} */ +/* {{{ proto void mt_srand_array(array seed) + Seeds Mersenne Twister random number generator with multiple integers */ +PHP_FUNCTION(mt_srand_array) +{ + zval* arr = 0; + zval* tmp; + uint32_t length = 0, seed_j; + int i, j, k, first_loop = 1; + uint32_t* mt = BG(state); + + if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &arr) == FAILURE) + return; + + length = zend_hash_num_elements(Z_ARRVAL_P(arr)); + if (length == 0) { + php_error_docref(NULL, E_WARNING, "Argument must be an array with at least 1 element"); + return; + } + + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(arr), tmp) { + if (Z_TYPE_P(tmp) != IS_LONG) { + php_error_docref(NULL, E_WARNING, "Argument must be an array with only integer elements"); + return; + } + if (Z_LVAL_P(tmp) > 0xffffffffU) { + php_error_docref(NULL, E_WARNING, "Seed values will be truncated at 32 bits"); + return; + } + } ZEND_HASH_FOREACH_END(); + + php_mt_srand(19650218U); + i = 1; + k = 0; + while (k < N) { + j = 0; + ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(arr), tmp) { + seed_j = Z_LVAL_P(tmp); + mt[i] = ((mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U)) + seed_j + j) & 0xffffffffU; + i++; j++; k++; + if (i == N) { + mt[0] = mt[N-1]; + i = 1; + } + if (!first_loop && k == N) { + break; + } + } ZEND_HASH_FOREACH_END(); + first_loop = 0; + } + for (k = 1; k < N; ++k) { + mt[i] = ((mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U)) - i) & 0xffffffffU; + i++; + if (i == N) { + mt[0] = mt[N-1]; + i = 1; + } + } + + mt[0] = 0x80000000UL; +} +/* }}} */ + /* {{{ php_mt_rand_range */ PHPAPI zend_long php_mt_rand_range(zend_long min, zend_long max) diff --git a/ext/standard/php_math.h b/ext/standard/php_math.h index 3ff0f04..0eaf34c 100644 --- a/ext/standard/php_math.h +++ b/ext/standard/php_math.h @@ -48,6 +48,7 @@ PHP_FUNCTION(pow); PHP_FUNCTION(sqrt); PHP_FUNCTION(rand); PHP_FUNCTION(mt_srand); +PHP_FUNCTION(mt_srand_array); PHP_FUNCTION(mt_rand); PHP_FUNCTION(mt_getrandmax); PHP_FUNCTION(abs); diff --git a/ext/standard/tests/math/mt_srand_array_basic.phpt b/ext/standard/tests/math/mt_srand_array_basic.phpt new file mode 100644 index 0000000..9632ff6 --- /dev/null +++ b/ext/standard/tests/math/mt_srand_array_basic.phpt @@ -0,0 +1,146 @@ +--TEST-- +Test mt_srand_array() - basic function mt_srand_array() +--FILE-- +<?php + +// Should produce the same mt_rand output with the same seed. +mt_srand_array([1,2,3,4,5]); +$a = [mt_rand(), mt_rand(), mt_rand(), mt_rand(), mt_rand(), mt_rand()]; +mt_srand_array([1,2,3,4,5]); +$b = [mt_rand(), mt_rand(), mt_rand(), mt_rand(), mt_rand(), mt_rand()]; +var_dump($a == $b); + +// Should produce different mt_rand output with a different seed. +mt_srand_array([1,2,3,4,6]); +$c = [mt_rand(), mt_rand(), mt_rand(), mt_rand(), mt_rand(), mt_rand()]; +var_dump($a == $c); + +// Should return NULL if the argument is an array of integers. +var_dump(mt_srand_array([1])); +var_dump(mt_srand_array([1, 2])); +var_dump(mt_srand_array([1, 2, 3])); + +// Should give warnings if the argument is not an array of integers. +var_dump(mt_srand_array()); +var_dump(mt_srand_array(NULL)); +var_dump(mt_srand_array(true)); +var_dump(mt_srand_array(false)); +var_dump(mt_srand_array(1)); +var_dump(mt_srand_array(1.2)); +var_dump(mt_srand_array('x')); +var_dump(mt_srand_array([])); + +var_dump(mt_srand_array([NULL])); +var_dump(mt_srand_array([true])); +var_dump(mt_srand_array([false])); +var_dump(mt_srand_array([1.2])); +var_dump(mt_srand_array(['x'])); + +var_dump(mt_srand_array([1, NULL])); +var_dump(mt_srand_array([1, true])); +var_dump(mt_srand_array([1, false])); +var_dump(mt_srand_array([1, 1.2])); +var_dump(mt_srand_array([1, 'x'])); + +var_dump(mt_srand_array([NULL, 1])); +var_dump(mt_srand_array([true, 1])); +var_dump(mt_srand_array([false, 1])); +var_dump(mt_srand_array([1.2, 1])); +var_dump(mt_srand_array(['x', 1])); + +var_dump(mt_srand_array([NULL, NULL])); +var_dump(mt_srand_array([true, true])); +var_dump(mt_srand_array([false, false])); +var_dump(mt_srand_array([1.2, 1.2])); +var_dump(mt_srand_array(['x', 'x'])); +?> +--EXPECTF-- +bool(true) +bool(false) +NULL +NULL +NULL + +Warning: mt_srand_array() expects exactly 1 parameter, 0 given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, null given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, boolean given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, boolean given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, integer given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, float given in %s on line %d +NULL + +Warning: mt_srand_array() expects parameter 1 to be array, string given in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with at least 1 element in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL + +Warning: mt_srand_array(): Argument must be an array with only integer elements in %s on line %d +NULL diff --git a/ext/standard/tests/math/mt_srand_array_values.phpt b/ext/standard/tests/math/mt_srand_array_values.phpt new file mode 100644 index 0000000..267087b --- /dev/null +++ b/ext/standard/tests/math/mt_srand_array_values.phpt @@ -0,0 +1,532 @@ +--TEST-- +Test mt_srand_array() - check compability with init_by_array in mt19937ar.c +--FILE-- +<?php +// This seed data has been generated with mt_rand. +// The result of this test has been verified with the +// init_by_array() function as implemented in mt19937ar.c, +// www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c +// Retrieved on 2016-08-14. +$init = [ +533797649, 477972911, 238644764, 2053609391, 2114488238, 1672166357, +1677789847, 113814253, 405100136, 1295645083, 1280130337, 1621368104, +323373334, 739758941, 2122736136, 571686319, 1931835247, 1610510985, +886805278, 569348619, 710948850, 634958263, 1429967020, 882231681, +1937446023, 1982659960, 36274821, 1191994465, 1300109346, 1618746190, +1396450738, 362665554, 302920921, 135629471, 357568549, 1648999768, +661482772, 2114789554, 697545551, 1867848860, 1050863912, 1865143872, +1475217165, 830960919, 1447789791, 1185255739, 502046053, 1123548340, +1055621189, 1618672631, 2041212379, 109892516, 1227019944, 1854791485, +417803109, 1205974941, 1367602515, 378210590, 1087604852, 936932976, +1381267118, 2080903927, 1675549670, 90564939, 1634945948, 388014899, +1109080989, 1500872898, 933412936, 1066813864, 17431367, 595967286, +1551155677, 1458258881, 506201381, 1092415658, 2128699724, 1449748569, +1909047531, 1515378367, 641080814, 210001821, 1163210738, 1370727858, +639010335, 1872089810, 135888508, 1313165009, 1280281995, 1527988850, +2116763783, 614198830, 1797789661, 538957503, 1197965949, 925963643, +1506841753, 999985965, 1503444481, 524890767, 744379479, 1745888115, +52209032, 1224133648, 1537807057, 1936166300, 445956095, 1968273879, +1134590481, 1316727542, 523818403, 1302306188, 1354652864, 976108357, +103796790, 1424949017, 335385878, 1105235554, 233855582, 131523436, +1784833957, 521145555, 1931758539, 732135002, 1379160676, 1895399908, +1150639362, 1553140715, 3987400, 1396230818, 277995666, 310883379, +661226546, 426814614, 343481125, 727560266, 478876580, 901016650, +510767095, 1743023655, 951064457, 1850569028, 2088212331, 897804349, +280429432, 1868876377, 1570585499, 776776692, 1683903637, 355773179, +1237562751, 131484929, 125708162, 1490038497, 903282947, 484763921, +1764663586, 1368171520, 1493598367, 824508183, 1103087905, 1524087400, +1831251776, 1569425806, 1330071902, 831508806, 908341615, 205958001, +1943730657, 1173522039, 507655877, 601796216, 1085473883, 1284710358, +406936046, 552693839, 715571237, 110285275, 2121816357, 2089795927, +1303734565, 1545306620, 141170901, 867120865, 695911088, 500627405, +413963957, 943343585, 1967548673, 1315894357, 1952581633, 55277097, +1223977823, 1858601487, 1652396537, 1869807239, 1529563734, 476959585, +1295061857, 566255510, 1897796839, 1394015214, 491077539, 1736174778, +429971276, 1340503695, 1149812026, 323721773, 116800211, 304084477, +1844663726, 924889110, 804219111, 1984079178, 1346488888, 1425936286, +123375196, 1791409314, 1664826154, 2018183455, 506485465, 475390404, +1979884372, 1269275022, 95711359, 1329071187, 1638184505, 1463868742, +617100013, 960407801, 1768037344, 767806250, 1092071035, 1638477527, +214244044, 1189205992, 2029884775, 1956872370, 1366069623, 32184929, +1877835037, 421419782, 1409947233, 1207359486, 505030335, 919857673, +1205155568, 76387164, 1742504740, 2051050756, 1426362152, 439972012, +892503831, 1374142231, 677384032, 1633892368, 1134563858, 1500620380, +1589898381, 447861609, 432962471, 2145785468, 44677632, 735513485, +2057090372, 1600969875, 1433738499, 1230433030, 1801937285, 1119440216, +1654208084, 1036123305, 1377826919, 1886868624, 854533290, 2141365733, +1373085085, 1416284165, 216719504, 1587889366, 13124183, 1275691400, +91607173, 1946669758, 964084222, 668578809, 1714548277, 1637585450, +891023658, 2132201878, 938297201, 2144829786, 1611917447, 864352756, +2034122367, 1433920143, 573899348, 151439910, 865203873, 961912203, +590298954, 784893319, 99398163, 280396586, 1053672810, 1352995158, +1724386053, 1839187077, 379317857, 442262335, 243178258, 887432801, +1940613113, 1317606803, 590560793, 754404910, 1589494120, 797096816, +617577060, 163058622, 1152015712, 468527387, 1343707972, 1596194670, +1001870219, 911883094, 1379771701, 5033855, 766626331, 2066247492, +41189068, 210307945, 1733781581, 270781045, 1767974932, 1138659598, +1665411426, 1607827087, 2056915989, 2102498495, 1081124166, 1627546761, +1109544454, 1489139518, 127909289, 1429674314, 1548640155, 1284860561, +930975560, 1453540039, 1359733583, 499159547, 1260967563, 1202062669, +129728016, 1043430497, 919924248, 946773678, 1263998762, 744696562, +1430427674, 38224117, 1132467017, 372457291, 1293395629, 692690250, +33264961, 909551629, 949650166, 1049086914, 896915547, 138231579, +180066472, 2089106029, 297507614, 88535919, 1400040145, 786778873, +774499467, 189227111, 730267148, 558137141, 1556192531, 1854880898, +413999674, 1790021423, 956950507, 307010644, 2139264011, 952588702, +22703969, 1649091617, 592424405, 1822463165, 1961817729, 813523106, +1838938379, 484886386, 580262376, 761220596, 226184966, 763751275, +416245423, 501649838, 535690555, 1445627738, 486873654, 2043448554, +923777271, 1947825799, 1113910169, 810625470, 1440672345, 1791782910, +1755202249, 424681059, 431435735, 398929029, 1433887466, 1410641306, +1636201573, 1998989952, 104589354, 902567826, 3391690, 1411680711, +396290247, 2131874885, 388219790, 1899096911, 1426722047, 1364753737, +535936670, 664505103, 644668225, 1663840379, 1005745889, 40078604, +461214428, 579471610, 833615480, 1230511410, 1304422579, 193758057, +1672675955, 747814555, 2049077078, 1578324806, 1762849299, 2067454018, +223356632, 1068768699, 1808701756, 406983376, 578971973, 1867346482, +840150829, 1590199236, 1754927355, 1114057306, 504051145, 243402561, +431895923, 1594562645, 525154058, 1888670763, 2145863250, 422030732, +673730895, 1413240790, 372732506, 1027902875, 2130104737, 1193346548, +1490323370, 223614718, 1038891332, 616471406, 2011501366, 699505754, +1570284924, 1289954611, 1897428735, 450379033, 1443599841, 860128998, +1683747465, 1334460614, 477769514, 1909363216, 552852481, 1944603627, +1138684653, 1373242252, 880923256, 1206958392, 1342563542, 2120128971, +583363449, 2107607857, 1541046033, 1980230973, 831652021, 1043736620, +2081294993, 1253655389, 789832753, 383617105, 485338008, 246103765, +720839801, 657392545, 1631101285, 1708545871, 780994605, 1505703390, +573304601, 1631160520, 687436085, 817344356, 640229444, 1115011991, +209661902, 1631449900, 19891655, 820809520, 850184329, 1103973314, +1285650469, 1212039883, 390145457, 1357597548, 1695478847, 81575737, +1154767271, 930009212, 277877561, 140160052, 802415541, 1356511191, +864493720, 1819977751, 311532744, 1914315473, 2137739525, 1758173691, +1171975597, 1215338878, 317767496, 1934349874, 404221217, 1535322034, +2141083001, 1046590691, 1011777816, 784331043, 1711186310, 2067261175, +1508489771, 1629660117, 1444015364, 1592626938, 2129389821, 633652185, +511258736, 407971522, 464510006, 1497625509, 1685641648, 1804014524, +1009242557, 61061698, 1405334575, 705682809, 619195664, 593393238, +1577984545, 1121470655, 882777441, 139560580, 2139919257, 820789257, +1898162007, 6675532, 51758493, 804847213, 275705871, 1246885804, +658168523, 1966325428, 2094850101, 231698998, 1468867533, 927808264, +1313423995, 27545931, 1911675605, 376724485, 2022522750, 637063886, +562091128, 46019904, 1063172776, 212986628, 193143948, 1294935095, +993881399, 2042413486, 1086228342, 1683291727, 1801483326, 1189401767, +1450882216, 1858464503, 1855079500, 1326724577, 1734871315, 1548222238, +1966282326, 1297628716, 159487328, 1573101242, 426785719, 72200136, +1884204420, 391317200, 1080554501, 285019761, 943120760, 7124744, +1115402114, 802470849, 1964356667, 1960971254, 1077903446, 67183127, +215253688, 962005861, 138356688, 98240943, 1807405496, 805010592, +892878533, 425673084, 1880574321, 1459417821, 1682211192, 1506142233, +1867979425, 1321576946, 1889304115, 582144916, 102926510, 1438056115, +1751699141, 1539198500, 1736018960, 874447426, 1370430737, 158028091, +830213454, 84442953, 478002763, 1992177394, 283260781, 500554761, +608355287, 1476142378, 1917216540, 1921304150, 1233676204, 1987220632, +1628300872, 704676962, 664952429, 1153780146, 1562608939, 1811460092, +1916392842, 1941182975, 1154268557, 1329577514, 725220972, 1766128801, +1593162097, 612801712, 562123274, 87904352, 1504571159, 1398355079, +1825995053, 80381375, 951127489, 849324238, 567490334, 248572213, +1651344667, 2028742815, 1801765381, 2043626293, 213906326, 143438100, +411567064, 813777482, 1872782163, 1294613046, 2101012247, 31439236, +1637792947, 1993562032, 1395888579, 958434755, 1292930952, 687519459, +701710960, 30124557, 1905935225, 1510749004, 1306496601, 264466552, +1378680660, 1670701482, 1310930850, 136564095, 2007626089, 1547390501, +810810644, 1168805588, 898359224, 629482809, 2120956570, 1069280196, +1511095111, 2087090462, 225047305, 1637362290, 308575013, 1352330332, +734850344, 670808293, 178357535, 594394980, 1139434567, 883284580, +1397948317, 28912352, 1446748190, 617861994, 815347173, 1963980261, +214445682, 907035403, 1143999893, 2062970592, 1984051944, 1774362025, +512798853, 702140750, 1001106098, 46214571, 1156971972, 1201543040, +1503090317, 1780990882, 835930457, 884260311, 901771492, 422424056, +1503069960, 705444497, 578874916, 1062852456, 894989764, 899631711, +370578589, 1202931154, 383520217, 1327620695, 1831710089, 1086004548, +1255965593, 840271333, 115928733, 577490500, 78584127, 727056064, +1752936049, 964887523, 1154711175, 1071664748, 1480358451, 203805324, +1469054064, 1290874799, 269418577, 1171314433, 215271957, 370094284, +968856636, 1657607566, 1042793512, 2015382843, 383027214, 1758820919, +344860887, 647079493, 876643877, 2101300674, 987426396, 16729551, +1784043767, 1572338717, 843065412, 2067471506, 1502869217, 1799646693, +213285071, 377052203, 1830446282, 982272583, 414733416, 410793732, +873346518, 503246214, 797656459, 628299992, 512241280, 948656140, +1451451600, 345895028, 518757933, 1588415604, 984200527, 1086753412, +544527639, 874200561, 1470690041, 484206177, 909376930, 1486600433, +1937975887, 559677004, 1994302069, 823577794, 1116225413, 1743029005, +1827892021, 1879629231, 423581839, 541026028, 494758223, 1435770877, +1598155535, 1964981539, 329093792, 1832472320, 1087574585, 1101854573, +1378007344, 1228236959, 1945133695, 646893932, 1415173992, 1529640465, +2079401260, 780838700, 1293285469, 391785176, 677753081, 15747793, +1894718671, 1670274714, 1046250815, 448209684, 335857912, 1765225040, +1801777069, 527995858, 1721154109, 749717364, 1565144236, 1819753500, +8884840, 1129870710, 243516099, 2113571701, 1846885628, 940241410, +1962405398, 190731176, 2008927995, 1226017471, 1368340416, 1104933192, +1064493189, 218937022, 297879713, 320860513, 818032854, 1949568466, +314939544, 1795587253, 175992163, 1319391772, 1174222140, 1170802330, +1061966846, 71721662, 762971128, 182330249, 299574656, 469546625, +761501604, 53300548, 188294742, 673141118, 648693521, 382299026, +1870609055, 466728501, 943212212, 1609815508, 262702628, 1507117809, +161574838, 1019440860, 2050064521, 1425857550, 1492014039, 944287347, +1007097370, 1757596940, 2090286765, 1730912181, 1320997748, 1589615122, +1451147491, 1108660228, 2020426077, 892328452, 1655953465, 43749229, +1376485909, 1317737148, 1415607683, 1841115553, 1460021946, 1886464852, +1408187472, 154974876, 1191879427, 77435359, 192555798, 595802156, +920350281, 436095593, 1462774350, 655206373, 1051033499, 752363624, +1787149375, 595615018, 1665287633, 1590146048, 1769673860, 340684559, +1652562876, 1824116798, 475024620, 2086628846, 880062478, 256075702, +340587598, 290281509, 584831433, 2007516777, 1343890550, 349845801, +1336747094, 568610678, 61799944, 236329154, 526799089, 506356879, +1740532421, 1879730506, 1990728978, 1915293831, 938595895, 1825498368, +494032435, 1757730800, 2044538616, 1112573724, 624804594, 1321575931, +1948102067, 1208497950, 698867660, 1730012823 +]; + +printf("init %d\n", 5); +mt_srand_array(array_slice($init, 0, 5)); +for ($i = 0; $i < 1000; ++$i) { + if ($i) echo ($i % 6 == 0 ? "\n" : " "); + printf("%d,", mt_rand()); +} +echo "\n"; + +printf("init %d\n", count($init)); +mt_srand_array($init); +for ($i = 0; $i < 1000; ++$i) { + if ($i) echo ($i % 6 == 0 ? "\n" : " "); + printf("%d,", mt_rand()); +} +echo "\n"; +?> +--EXPECT-- +init 5 +1678085969, 173170251, 1782802870, 937957818, 2049075857, 475493648, +631159003, 265551473, 367318037, 180728820, 882767285, 518593020, +1483604447, 134774193, 964352505, 1672651821, 88387593, 624398452, +768905273, 62945995, 1786727054, 129379898, 1251426231, 120487373, +1588634830, 646438254, 2062420793, 624611897, 380598150, 1999644287, +126446955, 159634314, 1420847270, 727488664, 299098148, 414993981, +987722467, 1753145380, 1045592542, 12767669, 1223761434, 1813465931, +171025115, 335674505, 1777844237, 2046360196, 549508484, 2060432233, +1478591136, 82598413, 1437272609, 188008750, 537318096, 1563000981, +1322768027, 122924280, 989201561, 1838053780, 1524406237, 402767818, +1357934275, 518154174, 1970896318, 1291492803, 1703288044, 1710090268, +1134974040, 1205530280, 1564219437, 1959999115, 2070873944, 1093246373, +1774468942, 1548462422, 1537766937, 2470930, 1730334238, 542124953, +1485726082, 1611191139, 1615506211, 1744134923, 1032166749, 373825211, +1185635659, 2054543400, 1408272743, 222902069, 934971869, 325709765, +1848019873, 1701075729, 390124953, 773120821, 360567826, 1789065666, +1134188761, 235988203, 1649775550, 1866268786, 1865237225, 308439968, +488266067, 671018254, 112438428, 495480977, 1667523297, 584455950, +1606364015, 803240708, 681841472, 1884613027, 879967411, 1244875426, +1958303277, 1169798427, 2067773861, 399232754, 429408626, 1444908741, +1397404058, 438083513, 51005745, 677540897, 1848792993, 2040283834, +73877667, 641558522, 210465773, 670213318, 1962329747, 213848257, +127734689, 1159679712, 309719363, 343863574, 451160292, 363285968, +920300268, 1223618319, 2092752885, 716753896, 253388247, 1033700545, +656469891, 964333406, 626675494, 668764599, 284541113, 716974699, +1552757841, 2122977183, 1961264786, 159796457, 954597579, 76987656, +458685897, 745258981, 1725018277, 222533039, 811460418, 247922055, +421883548, 381762822, 756499932, 942630902, 1560631298, 772857810, +1894117589, 733999678, 793502595, 1322008488, 1614401720, 1495641839, +1158576564, 1823434050, 1664573103, 7566840, 1727024249, 798041803, +582370562, 304218954, 838981650, 314510836, 1828785517, 1104865992, +426047409, 254634264, 1052462887, 654559757, 1110467271, 1368997850, +1332370983, 1298526292, 1717151294, 1299785270, 1205967042, 1945591610, +39245245, 252233892, 1379438881, 1563554062, 55749522, 1281643592, +772214558, 419402223, 2139436058, 1438909276, 116548681, 977950774, +1843696587, 262197124, 1027335544, 99463235, 1377044058, 272767630, +2076200847, 785296613, 1095742480, 1187187832, 476552792, 834384586, +140321133, 1895093493, 1704339120, 1206230228, 672749714, 701573697, +712587138, 559763958, 1833886670, 1246194772, 131970736, 1026960167, +258531498, 533309357, 302809735, 78705794, 180401783, 1438221774, +1171710223, 62233318, 1114313937, 181783356, 1372495881, 1525021015, +1081472076, 863314220, 1154718358, 632560915, 447829343, 172268965, +892950544, 638504668, 1927157561, 48066633, 1048890682, 1639383707, +214700437, 2091128935, 1398268525, 2787833, 404111919, 1496088284, +1568785210, 1237637766, 2024715775, 1070278879, 333332389, 222404898, +530985834, 436107194, 898494426, 2002031102, 1463945304, 1047357225, +877606586, 1779966837, 777777644, 2047233898, 1397786520, 1397326652, +1888920804, 1987775265, 1343238365, 1521274607, 1664471951, 1824675909, +1214837658, 687267230, 1318012059, 1523568963, 1569744542, 2040235203, +1458478110, 813839624, 516195500, 1706443716, 387069934, 826717497, +661029222, 1698099585, 1619086966, 472920484, 397208282, 1546010573, +1459811472, 155769548, 1005470241, 1332622415, 1401701839, 929943807, +17496501, 167865207, 39119769, 1549803902, 1275144214, 402453424, +291332047, 119011701, 424791945, 1635111346, 1008471199, 1235519240, +1964241044, 1171691282, 407274744, 264819878, 2127954766, 936159281, +1125822853, 1147029717, 656833846, 1991402116, 1226342161, 1812321691, +524992088, 1810773922, 2026071844, 1615449650, 2126358431, 270824574, +272446342, 1116242880, 1796886580, 697118066, 1732398470, 134944144, +396856570, 1781884880, 2062414019, 102202061, 614318803, 2073719717, +42103060, 1524008207, 1003551051, 1324347014, 343150315, 121854185, +1749758390, 2086808537, 1267592318, 72062746, 1207296988, 1643045338, +165847348, 965850327, 1630973577, 1485469182, 306799380, 643908446, +735844106, 613194827, 1424491263, 20870783, 1683414788, 814852722, +1645422996, 1591969802, 108681618, 596735742, 581347169, 238372006, +2057427754, 411896601, 179840892, 1171842900, 1243785904, 1160793500, +1168001476, 1701651494, 1573335512, 919745851, 1423498746, 1599105340, +59486933, 1946207583, 255480857, 230755676, 582759138, 1782505704, +1014623654, 93567142, 501546608, 445395111, 1698508681, 2118306626, +2044371843, 1590884942, 1855172077, 2132429415, 693554267, 1540348537, +1524008423, 1598749681, 1162339897, 83169613, 1582659019, 1386408935, +452518407, 399739662, 562081531, 1749652889, 456329004, 1651421807, +417441467, 72768787, 188189810, 938986731, 1267364468, 1263903786, +943353794, 831740732, 573154911, 930464617, 1706902055, 320044701, +1848930605, 759699675, 650016838, 603605656, 1295110101, 1682265851, +548352407, 1646100528, 1470310168, 1395219556, 2057341385, 1454271902, +1152371462, 287938688, 1313390732, 732216538, 1611562077, 2108866735, +1791254179, 1695098182, 860924454, 1071154156, 1595681364, 1110578611, +967111431, 529535867, 1747680551, 1901288299, 1146121481, 1032369048, +1561952783, 281435437, 1575636635, 709983939, 1682585696, 792937343, +706127520, 1356220838, 1323583891, 741089452, 1871351301, 296217876, +1643734231, 206775477, 1705966924, 948141888, 1049519578, 739897487, +125778627, 112303069, 864415289, 542025605, 667129468, 965667788, +2070292383, 631287150, 173144548, 1697432442, 996099145, 604261523, +1447892832, 837818285, 445235679, 1499594811, 876824624, 393233787, +1626380339, 1303856788, 855369858, 188641682, 1681158451, 2094210553, +1781204178, 1135663622, 704285652, 1880224068, 425221731, 327473624, +1039642257, 1565338083, 414946522, 1010064589, 1264913340, 1515349606, +1511659415, 867897001, 424884116, 187908546, 2064028594, 1318843210, +1200326261, 1171921289, 1755282560, 577579416, 1963270104, 108604668, +1465657995, 2134994058, 54063649, 1922385414, 2134814091, 920509373, +1371241837, 179734609, 1753977750, 1881176241, 1160194538, 633203641, +248257266, 160432164, 1174083751, 1869649959, 1265733541, 342753628, +1042343179, 1558817004, 662228230, 426303967, 52599397, 417304543, +563481354, 1959363161, 1012360589, 1480861398, 1091180077, 757484865, +402810392, 22659448, 2104312645, 1393473726, 313079060, 1720345614, +1547286608, 440350497, 1038702504, 1320656001, 139557658, 160814655, +1120448208, 1630894778, 1823854524, 2112880666, 254049795, 769182217, +1988273240, 265535314, 155513257, 910763639, 1494357430, 336664448, +709382536, 1371967891, 460724405, 1851926075, 1543123287, 1951024034, +757250103, 371934696, 1711929196, 1140185691, 1916650934, 763374904, +1270790180, 1862915836, 1428366502, 224431428, 1025831708, 1353196886, +1472340786, 617723365, 1667847487, 2145832122, 499682359, 1225554127, +879776645, 1531037326, 1162895834, 317423246, 1685725841, 726301581, +1445098093, 1518570230, 207578906, 1570892321, 507703530, 1028678219, +1908778501, 251699072, 803730769, 1725031729, 1231638911, 184249436, +1657312598, 182416268, 659889559, 1076854276, 1227109276, 2101310460, +1080262363, 2010944041, 872294238, 296576621, 1639843353, 1055468010, +1221834574, 1640475125, 1586738399, 1885305952, 183220722, 498344677, +444321987, 1643254950, 1707056411, 840347155, 701891000, 1586612615, +2069168262, 146270803, 833420350, 493189987, 773262803, 1653658434, +2052935862, 1732568101, 589336318, 1317029499, 1947842396, 1625044604, +2067190720, 1938660402, 2127461260, 1833473329, 1769289178, 675228003, +1274493809, 2030117365, 2111336557, 889705256, 1313670825, 978867720, +1124383289, 1081615542, 872995886, 1580286787, 1743304828, 2065619306, +141336252, 900473833, 1276311040, 1031012968, 1684506321, 1715923687, +113051291, 2103905761, 1796447328, 1481419947, 1265353271, 463463765, +1181842726, 1864289951, 1391445669, 1561920507, 1690657304, 539450648, +233976639, 1781460989, 102116313, 277501659, 2057695232, 399374154, +253291389, 213054850, 1549165702, 141993661, 609980912, 954361616, +369994966, 1963169244, 1461655693, 1456507482, 559744717, 584737195, +1489543623, 559564535, 140274584, 970099295, 392790864, 54182867, +593868692, 2140733955, 101159131, 2024047281, 1266096579, 606195139, +1602404067, 2060457720, 1761718118, 1836011858, 785892683, 1716308014, +861070048, 1702443877, 941622984, 378366524, 152594682, 167909708, +314963998, 630854539, 1798994002, 1389044097, 985097841, 1157040721, +265075438, 1429980301, 499489890, 623159753, 1172125800, 886466981, +183494643, 564774918, 1898626953, 306976580, 810859339, 291570861, +1487607786, 1852587929, 2013416964, 214002840, 1133515065, 729846310, +2122565116, 1966058439, 1973273434, 906557283, 1982866876, 1725046252, +922159523, 1680009188, 636183905, 492096369, 1065504721, 1658221372, +1915213760, 20704986, 2054518307, 417623390, 338259801, 1772577704, +1164295913, 1487400349, 1198936352, 941802882, 710953151, 41436756, +694551391, 1780791007, 1670172407, 510226143, 1704983228, 1234576800, +2017484910, 1987089499, 877072623, 218656974, 1882899491, 203698556, +1513215802, 1080859235, 722664779, 663232474, 694739582, 37157761, +321239494, 1340305956, 569186972, 1999156701, 1125628319, 2053000467, +931556325, 1339953903, 474370210, 1778883985, 27178352, 1364274459, +2116793083, 1332866977, 451364122, 277350424, 1259803477, 806709477, +710988522, 568129536, 1525314388, 1589055462, 1649655838, 24851681, +1191362823, 652466018, 51507135, 1949811523, 1420215882, 20117642, +1857490136, 612776782, 848703729, 212984899, 488209359, 894858669, +749747098, 1449304251, 1395664211, 1033532758, 2065110276, 1559613251, +265952038, 943542317, 1998024290, 313914991, 1194859837, 389750550, +411229008, 840806755, 292338179, 1161175231, 317219581, 507864395, +606806965, 1325384287, 955404346, 1246677080, 1322281139, 1598537319, +1166023292, 1450778928, 1637022860, 731667986, 2073782484, 1004998191, +102564534, 815125906, 1576098225, 1524965501, 5313864, 1823974573, +1773504912, 1041743912, 881554341, 960776758, 552712693, 408302745, +2114071279, 992220049, 511892365, 1697239197, 1629776795, 1137469311, +576094438, 427212158, 202025744, 1805447936, 542712707, 1212058647, +1131832821, 691738312, 1352812628, 892381556, 715334465, 1341375748, +564271455, 1911559160, 1475034391, 158936189, 2098991028, 1661681153, +988209962, 1208631994, 1931293838, 1520770876, 1957491147, 1319211690, +1839734598, 98025503, 1898820039, 191381922, 1071988827, 346778027, +2076473163, 1923156889, 42870090, 904787726, 371487994, 1174099381, +2065179007, 1990282685, 2063040778, 837926979, 2070802548, 1660082840, +1062920547, 383910317, 240858277, 1821874888, 578052854, 1794193445, +840412869, 1649530704, 327206201, 856874774, 452646903, 256085065, +1309181648, 92993917, 1316491931, 226414572, 1946863354, 2098432716, +590780777, 775622219, 65186292, 312039255, 499083469, 300853689, +85727687, 423103458, 1603448541, 260765600, 654212345, 1927590285, +829298165, 1361679699, 1252981468, 925948379, 1531851382, 1392425081, +1592767896, 2055439648, 726498016, 1752842652, 660098655, 361867427, +1775381738, 660450687, 1118322932, 87583662, 880921452, 25581819, +61209221, 1474069918, 1248142062, 1390035608, 241286489, 2001493941, +1791774504, 709352275, 801736976, 1302784851, 876575406, 827516598, +850464784, 1956581916, 378456154, 2036444036, +init 1000 +1566269010, 1577817406, 983081823, 466847167, 1269997621, 1570102927, +1175203448, 387128547, 1152641261, 1675164555, 708054521, 809195642, +1154980224, 893776526, 1466993235, 1987264596, 1777519094, 1792057342, +1900130956, 212087530, 1214906941, 1386095814, 481453987, 572437858, +685038779, 556063355, 113351045, 1147151342, 1609864850, 1641590377, +440937637, 1789685137, 458387830, 1071903074, 1137640085, 499179440, +1927787531, 91245143, 204426269, 508877080, 625409662, 745281164, +599264206, 22418560, 1714492083, 2145982767, 686507795, 1893975320, +862119871, 199956756, 1333019389, 535957904, 645851752, 714371650, +1604067957, 974054946, 1803085920, 413150636, 709122057, 1006236295, +2072315812, 1641026853, 2116076672, 1963131314, 2015575705, 1754791675, +1596226318, 1376496955, 402027722, 718707965, 1312024918, 157830053, +860495892, 1684103858, 2096376248, 2087857649, 969316396, 344059322, +2098340507, 907491929, 54656404, 1846526534, 572433124, 1476099654, +1952268768, 1336999301, 815101974, 507852672, 623075903, 1602813023, +1112061737, 1788404453, 1706235013, 1830416895, 130726061, 1202957358, +1905013405, 17696991, 803084719, 1542037857, 1753073656, 553315491, +1037031163, 413050390, 1972842238, 490076427, 768679251, 2032313061, +1900005591, 1909296309, 1630406245, 338865021, 258597916, 1567660738, +1886914963, 37364240, 96683127, 815918524, 1278067042, 3952756, +720030699, 1872939470, 2030750901, 417006013, 971097311, 256405565, +454406216, 2143061063, 2080327435, 1110617569, 1518651660, 608778944, +1773476245, 436639808, 412565702, 2122330027, 813463571, 189556107, +42983345, 252282741, 750734589, 1836585880, 1849636644, 1128503777, +1065907346, 1951190421, 1508054477, 354656362, 1337989637, 1014835319, +1561677407, 1435373313, 752380763, 798814388, 1957637951, 179956077, +1406092512, 2032644936, 140940168, 1785330322, 2037803748, 1374413818, +1260471946, 1168813720, 1715740660, 325886497, 1206606207, 1743914311, +730716435, 326437850, 1555942420, 158875311, 1631278570, 537421974, +59088190, 1980156516, 497581730, 172724213, 2055447169, 300797259, +2052359904, 117801240, 376371077, 1568317567, 1497319595, 766659117, +956118239, 1219237068, 661967320, 2042816439, 1534887435, 2104452721, +1709596870, 663362071, 1637569290, 354026836, 1714337378, 498529972, +1779724846, 397501320, 720901087, 976717623, 355776524, 1834092419, +1234705911, 107143663, 13817521, 1411999332, 839549259, 889725526, +1879351433, 1946412586, 1983975745, 1329576496, 919590745, 1074674083, +365349485, 1039061118, 1069820944, 242436950, 641482727, 913581683, +876261540, 1647392872, 1937921206, 1929825879, 881678898, 982329413, +1846389738, 1639187759, 411987811, 1202402139, 1631049557, 1035015103, +2029797068, 1029821435, 1328775232, 857109758, 1991731166, 531949017, +756556826, 486001859, 1454625531, 1763854647, 631675719, 184649092, +893545379, 2050281110, 381164101, 557331191, 1763134224, 614249057, +1410725653, 1379973575, 1511233308, 212582416, 515501642, 2069735867, +746529097, 193611016, 1934357579, 220270635, 847942224, 1886818967, +1340917950, 368977556, 608474695, 576911109, 840222279, 1354234175, +2065802593, 1491578590, 433360840, 484954434, 1540629038, 1413861729, +70406799, 1583455072, 2034279236, 343804889, 1732753268, 481448963, +1677751046, 2071149371, 410272071, 1290290178, 534247187, 542242491, +1509508142, 500727695, 204146588, 1322643382, 1607713322, 830860005, +1251289915, 768663095, 1273968338, 144053432, 2118725784, 1142916899, +449238281, 212592138, 374885348, 494184451, 169912675, 2050022386, +1811877283, 584380257, 1133579912, 595920115, 581582193, 116921249, +1117736860, 88115023, 1172100320, 581947787, 1120270592, 1256745825, +626331590, 1452472680, 1993145721, 1495183160, 982652345, 157025499, +884519486, 1768290640, 213571931, 1557849941, 1684341473, 1230241812, +1091632646, 833725385, 341249065, 2142868457, 1853608709, 1080490176, +568276421, 1376926838, 637735195, 1093522817, 435390514, 1248677273, +1944464367, 1868385292, 964774263, 915984617, 1365167027, 1230848150, +431737586, 1639401166, 399922119, 927370301, 166480471, 529810054, +316432245, 695072575, 1973035081, 1395174978, 482569996, 541373971, +678894176, 1330306190, 590473532, 615541562, 124180112, 2010719946, +2027991127, 644413027, 673982143, 1337556209, 2090219548, 726936465, +803025765, 9941720, 225746830, 1717861759, 405792821, 1990870861, +1739348810, 1266097278, 388545031, 792104156, 1034851507, 235374003, +1957659503, 1548780660, 778628998, 1795062311, 1572515640, 1678158612, +896895521, 151723812, 1307029593, 1928424284, 348559864, 2062382079, +951246024, 2104159840, 1673276881, 1646390749, 2144609983, 545748263, +1825978368, 437523956, 1741371085, 1381271541, 1015120853, 538483106, +2049710079, 1659575013, 705531742, 1735748503, 445555545, 1336307753, +100946396, 260386021, 1723425839, 1922531334, 1270786911, 1803295540, +285720423, 406936151, 2083378228, 1362104072, 506278299, 66281655, +1772530155, 879502602, 72714215, 1106123927, 1940101791, 300477828, +504902151, 54825302, 117215879, 626805023, 686892667, 850679206, +1293075053, 667159655, 1145563618, 2030167690, 1430100049, 1961271371, +702760731, 1945844564, 1461201416, 744192262, 1405238206, 154907952, +1954621046, 1523259518, 1999768623, 1159020794, 625477257, 900800864, +644286390, 1088485681, 299208777, 528457469, 111395140, 1683097597, +1056119046, 4251645, 1652966696, 1582238634, 133176526, 138344746, +285754828, 2128525112, 1719157610, 1623808636, 1850815404, 956821234, +117150474, 1129021313, 780976427, 610504601, 1628878066, 1955252946, +616992500, 1271309286, 1723733416, 1817267056, 1019743602, 193462273, +1051893934, 2037915990, 252861047, 1920878383, 1365707085, 1185753156, +1402699015, 1369745688, 427988387, 1011936546, 136510012, 1258758184, +1548835887, 311827966, 1236178639, 1672407956, 667450528, 400161398, +846383170, 2079881426, 1546079068, 1442325274, 683650858, 1889106145, +289056132, 140354545, 1326110467, 931216875, 624507476, 2011103114, +1880127485, 1673665861, 1662834564, 1981977072, 398222660, 1557275831, +1047937588, 1068084173, 1178431401, 80296864, 1358199527, 1573561785, +580143609, 566615593, 601387710, 1088776573, 2077876630, 2131144638, +914673956, 2048285474, 11059211, 1953683466, 103310197, 382096973, +209634909, 1887166585, 1300166856, 903399251, 206167289, 916703053, +798690300, 1638870085, 727372493, 300208288, 347390601, 432906269, +1924077408, 947187038, 1012670253, 351371782, 732447818, 1569590945, +677103690, 257042870, 1323690614, 150665311, 1612322141, 2128112401, +1596688388, 270507107, 693928176, 1304295702, 1752879041, 649561287, +1572533400, 569542095, 77777366, 170386339, 2021926578, 1463129342, +1479202184, 83014597, 110364816, 2045756296, 1841740845, 126832529, +1834098154, 171638643, 582088843, 1643097176, 1119500020, 1423400004, +1790540275, 877561826, 1793330797, 300372912, 1593487417, 1830479276, +1498911560, 1847121722, 1051725080, 1747802374, 927047373, 941492819, +2055277505, 354162913, 1889442208, 1823866659, 581189589, 2026986798, +1523298334, 625266996, 1573256235, 396671957, 1903012905, 1508597776, +1483060549, 1315331726, 1527729858, 2039849814, 2014154800, 1181753309, +1471586630, 1211076991, 407276916, 1769518037, 1522242524, 1242078816, +1680672623, 1766016978, 1715122078, 1689997128, 239651397, 2128004, +263908936, 947318146, 945100847, 1838061580, 1539318094, 1382027122, +829275567, 1569882046, 705688589, 1407806053, 1813402212, 850675482, +1961073181, 145026907, 86472510, 349519394, 897945788, 863399452, +1065901208, 531434638, 366166351, 1210713321, 545218367, 393073926, +2145548400, 782955693, 1765822321, 2064685344, 491739241, 850350547, +1807891474, 914179880, 2135491260, 1927664009, 652214332, 797260284, +2043815368, 1744175349, 1220786036, 1383649232, 625688720, 36788760, +1146356168, 1727917125, 540113674, 564007062, 1859729499, 445212953, +104049108, 1331380046, 1166188473, 406846492, 27712569, 1779852012, +1744181400, 1033379450, 14700903, 336960325, 1105087089, 1947166654, +233362575, 370018037, 88032338, 7121984, 455108562, 456712611, +515680341, 758082237, 633497608, 4886464, 2002670893, 230767083, +1838406105, 141370929, 306689046, 1419863118, 681924133, 1489140170, +1085660270, 725801642, 1918642751, 2138754657, 435314433, 2121705254, +1985684699, 163116873, 1724867483, 1471730357, 1198173424, 524994508, +1583772194, 2092726628, 625972840, 1363038444, 881234242, 136543603, +812730655, 835472734, 1635357858, 290284274, 1508089326, 398331261, +1053426013, 1483748698, 1285522591, 893844247, 979464340, 1801611536, +424018008, 1347754035, 591529653, 2114332011, 1806546159, 428794870, +1040972676, 2046488098, 153141013, 1240978913, 181969442, 1335605097, +1715089625, 936188331, 1344831690, 244136143, 448170287, 1012075312, +1392491975, 767135763, 848031523, 1174197785, 2066189082, 1889450891, +1438176502, 435239824, 202737780, 106455036, 1824553616, 297201847, +499987415, 1134607425, 608396192, 677251042, 2030155701, 402970258, +569948609, 1742668094, 1010948100, 1977658738, 984749927, 1627112888, +2077086196, 2038466678, 1653833146, 997175011, 19317323, 1225718430, +1469762781, 1337789398, 1557336200, 131097097, 1443283387, 313351869, +331389911, 1870193156, 1828665818, 410101653, 1886158783, 1598060173, +471802754, 1953815303, 1572360883, 211877323, 1889232301, 1857329269, +1006787573, 716565559, 1434164093, 328738024, 1375628013, 372989124, +1713026412, 49575548, 392271740, 463232215, 1962248445, 356458153, +1140606224, 1227379596, 451859963, 1872051058, 1126455819, 1277227524, +1456117912, 720379128, 1274817423, 774192336, 1330206633, 295950373, +608830155, 72015799, 795331808, 2094638698, 1783650852, 1565187482, +1436531223, 1041782516, 1817038608, 1317740161, 975683255, 224013088, +1545876956, 210933809, 1852223567, 596416452, 1067144276, 1067470614, +1486931882, 1992346842, 1504479407, 423872078, 572501910, 1276519857, +1594410049, 364281209, 1305023144, 700962990, 1242120327, 1844730466, +7364502, 533008553, 66898889, 695933977, 74026318, 1505057971, +2061555609, 535848125, 2014391648, 1233678896, 3039898, 425922244, +633593963, 1099905413, 1244196901, 762198604, 664843818, 501129477, +704330228, 358309157, 1575126050, 262431423, 366472858, 1573817300, +186883646, 1797234154, 1576829418, 504867654, 1288982796, 366978291, +1647638799, 490027916, 913283365, 2024351979, 2076484705, 337959169, +1375037894, 1841835564, 1647008925, 1024649771, 1188738330, 129397397, +1666842612, 1922311433, 1685281962, 1591222765, 1039061943, 1068438064, +1901654105, 1245395290, 1457048121, 1560648642, 2131679385, 1929730568, +1058666050, 1060141144, 1032781762, 318505686, 1759205741, 913104929, +240122500, 111664352, 1938328983, 1858305935, 1170071476, 1078589492, +1831305263, 576967257, 1156272103, 1853668432, 1423885235, 1069236445, +373398740, 76799505, 1508478769, 1204810226, 139921540, 25296222, +1775050726, 1070339572, 1538705766, 1710004382, 2036586058, 157021750, +1328896008, 799515396, 105573906, 1648776433, 200274819, 1609618251, +1429957221, 1048386394, 1086086873, 921575972, 1593744128, 1903738620, +20595829, 756026662, 1710504223, 1461767411, 1382851745, 1969238478, +2023915315, 1215868715, 945046162, 877606552, 578901097, 1178110092, +660071002, 1023096368, 157664468, 650644160, 486773073, 184628872, +739444301, 1087773393, 776382171, 1102089934, 1844970880, 739464598, +1416957267, 520482290, 857692367, 617530923, 16042936, 2029902781, +1590953954, 1012080749, 158571029, 602934895, 549207069, 1710425395, +1902800938, 252359401, 16477979, 1659604578, 449255533, 170718306, +802597574, 1208707263, 1717931711, 298439704,