#ifndef lint
#ifdef __GNUC__
#define ATTRIBUTE(attrs) __attribute__(attrs)
#else
#define ATTRIBUTE(attrs)
#endif
static char Rcs_Id[] ATTRIBUTE((used)) =
"$Id: mttest.c,v 1.16 2013-01-05 01:18:52-08 geoff Exp $";
#endif
/*
* Test the Mersenne Twister PRNG
*
* $Log: mttest.c,v $
* Revision 1.16 2013-01-05 01:18:52-08 geoff
* Fix a lot of compiler warnings.
*
* Revision 1.15 2012-12-30 16:24:49-08 geoff
* Use gcc attributes to suppress warnings on Rcs_Id. Add tests for seed
* functions.
*
* Revision 1.14 2010-06-24 01:53:58-07 geoff
* Switch to using types and formats from inttypes.h.
*
* Revision 1.13 2010-06-24 00:29:38-07 geoff
* Define the correct values as being explicitly 32 bits in size.
*
* Revision 1.12 2005-11-11 00:21:48-08 geoff
* When timing, accumulate results in a temporary to make sure that the
* compiler doesn't optimize all the code out of the test loops due to
* inlining and discovering unused variables.
*
* Revision 1.11 2003/09/11 05:55:19 geoff
* Get rid of some minor compiler warnings.
*
* Revision 1.10 2002/10/30 07:39:53 geoff
* Update the correct-value table to reflect M&N's new seeding algorithm,
* and the code to use it.
*
* Revision 1.9 2001/06/18 05:40:11 geoff
* Do 300 million timing loops by default.
*
* Revision 1.8 2001/06/14 10:26:59 geoff
* Test taking pointers to functions.
*
* Revision 1.7 2001/06/14 10:10:38 geoff
* Report RNs generated per second. Add some simple testing of state
* saving and restoration.
*
* Revision 1.6 2001/04/23 09:19:03 geoff
* Expand the validity test to 5000 numbers
*
* Revision 1.5 2001/04/23 08:36:42 geoff
* Fix a misplaced declaration
*
* Revision 1.4 2001/04/09 08:44:59 geoff
* Go from 1000 test values to 5000, and format them slightly more
* neatly. Get rid of a number of warnings.
*
* Revision 1.3 2001/04/07 23:09:38 geoff
* Accept an argument giving the number of millions of PRN's to generate
* in the timing loops (default 10 million).
*
* Revision 1.2 2001/04/07 22:21:41 geoff
* Add timing tests.
*
* Revision 1.1 2001/04/07 09:44:16 geoff
* Initial revision
*
*/
#include "mtwist.h"
#include <inttypes.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <sys/time.h>
int main(int argc, char * argv[]);
static void report_timing(unsigned long loops, struct rusage * then);
static void report_clock_timing(struct timeval * then);
/*
* Base unit for timing loops, so the caller can think in millions.
*/
#define TIMING_LOOP_BASE 1000000
/*
* Default number of timing loops to do
*/
#define TIMING_LOOPS (300 * TIMING_LOOP_BASE)
/*
* The following table contains values that were generated by Matsumoto and
* Nishimura's C program for the Mersenne Twist algorithm, using the
* default seed of 4357. These values are presumed to be correct. The
* test program compares the values generated by this implementation with
* the reference values to ensure that the generator has been implemented
* correctly.
*/
static uint32_t correct_values[] =
{
3499211612u, 581869302u, 3890346734u, 3586334585u, 545404204u,
4161255391u, 3922919429u, 949333985u, 2715962298u, 1323567403u,
418932835u, 2350294565u, 1196140740u, 809094426u, 2348838239u,
4264392720u, 4112460519u, 4279768804u, 4144164697u, 4156218106u,
676943009u, 3117454609u, 4168664243u, 4213834039u, 4111000746u,
471852626u, 2084672536u, 3427838553u, 3437178460u, 1275731771u,
609397212u, 20544909u, 1811450929u, 483031418u, 3933054126u,
2747762695u, 3402504553u, 3772830893u, 4120988587u, 2163214728u,
2816384844u, 3427077306u, 153380495u, 1551745920u, 3646982597u,
910208076u, 4011470445u, 2926416934u, 2915145307u, 1712568902u,
3254469058u, 3181055693u, 3191729660u, 2039073006u, 1684602222u,
1812852786u, 2815256116u, 746745227u, 735241234u, 1296707006u,
3032444839u, 3424291161u, 136721026u, 1359573808u, 1189375152u,
3747053250u, 198304612u, 640439652u, 417177801u, 4269491673u,
3536724425u, 3530047642u, 2984266209u, 537655879u, 1361931891u,
3280281326u, 4081172609u, 2107063880u, 147944788u, 2850164008u,
1884392678u, 540721923u, 1638781099u, 902841100u, 3287869586u,
219972873u, 3415357582u, 156513983u, 802611720u, 1755486969u,
2103522059u, 1967048444u, 1913778154u, 2094092595u, 2775893247u,
3410096536u, 3046698742u, 3955127111u, 3241354600u, 3468319344u,
1185518681u, 3031277329u, 2919300778u, 12105075u, 2813624502u,
3052449900u, 698412071u, 2765791248u, 511091141u, 1958646067u,
2140457296u, 3323948758u, 4122068897u, 2464257528u, 1461945556u,
3765644424u, 2513705832u, 3471087299u, 961264978u, 76338300u,
3226667454u, 3527224675u, 1095625157u, 3525484323u, 2173068963u,
4037587209u, 3002511655u, 1772389185u, 3826400342u, 1817480335u,
4120125281u, 2495189930u, 2350272820u, 678852156u, 595387438u,
3271610651u, 641212874u, 988512770u, 1105989508u, 3477783405u,
3610853094u, 4245667946u, 1092133642u, 1427854500u, 3497326703u,
1287767370u, 1045931779u, 58150106u, 3991156885u, 933029415u,
1503168825u, 3897101788u, 844370145u, 3644141418u, 1078396938u,
4101769245u, 2645891717u, 3345340191u, 2032760103u, 4241106803u,
1510366103u, 290319951u, 3568381791u, 3408475658u, 2513690134u,
2553373352u, 2361044915u, 3147346559u, 3939316793u, 2986002498u,
1227669233u, 2919803768u, 3252150224u, 1685003584u, 3237241796u,
2411870849u, 1634002467u, 893645500u, 2438775379u, 2265043167u,
325791709u, 1736062366u, 231714000u, 1515103006u, 2279758133u,
2546159170u, 3346497776u, 1530490810u, 4011545318u, 4144499009u,
557942923u, 663307952u, 2443079012u, 1696117849u, 2016017442u,
1663423246u, 51119001u, 3122246755u, 1447930741u, 1668894615u,
696567687u, 3983551422u, 3411426125u, 1873110678u, 1336658413u,
3705174600u, 2270032533u, 2664425968u, 711455903u, 513451233u,
2585492744u, 2027039028u, 1129453058u, 1461232481u, 2809248324u,
2275654012u, 2960153730u, 3075629128u, 3213286615u, 4245057188u,
1935061435u, 3094495853u, 360010077u, 3919490483u, 983448591u,
2171099548u, 3922754098u, 2397746050u, 654458600u, 2161184684u,
3546856898u, 1986311591u, 2312163142u, 2347594600u, 4278366025u,
1922360368u, 335761339u, 3669839044u, 1901288696u, 2595154464u,
458070173u, 2141230976u, 4131320786u, 4208748424u, 19903848u,
147391738u, 3328215103u, 4196191786u, 3510290616u, 1559873971u,
3731015357u, 2918514861u, 362649214u, 1487061100u, 1717053387u,
3675955720u, 1116134897u, 193529268u, 3436267940u, 2835191639u,
1852908272u, 3220971953u, 3911201640u, 571213604u, 781027019u,
4219206494u, 1133024903u, 409547355u, 625085180u, 1214072539u,
584409985u, 3445042528u, 3733581611u, 333104904u, 2489812253u,
2694595213u, 2361631596u, 34763086u, 622576118u, 2921810672u,
3663740744u, 2293225236u, 2671706445u, 1884059696u, 1507329019u,
857065948u, 2204390003u, 592711182u, 1725752375u, 1642107460u,
326274448u, 3274574484u, 1030432041u, 173822100u, 529650788u,
1086437636u, 789877945u, 2167974914u, 1030588245u, 3533061365u,
1792148406u, 4216468704u, 213264131u, 3536714075u, 3877136173u,
1296338417u, 4057830103u, 205919137u, 2108245233u, 1064497347u,
2101324080u, 2336703164u, 1450493809u, 3812754708u, 3865701845u,
1476779561u, 1585902852u, 142887412u, 477612192u, 699530444u,
3351157089u, 3768249319u, 1673915577u, 903239649u, 1038056164u,
1171465372u, 1734789440u, 2115022236u, 414269055u, 959581346u,
566820984u, 2105828892u, 4046076449u, 4101450561u, 4106566571u,
2800184123u, 2470502098u, 3253453343u, 256751188u, 1869365987u,
1008372035u, 2374606708u, 1516804538u, 228288551u, 3527001547u,
1385173098u, 66157275u, 1739381798u, 184785808u, 3901692666u,
725806641u, 3475217997u, 2787929747u, 1109372433u, 3142723729u,
557686578u, 2782047723u, 2118822689u, 1936702581u, 1625646963u,
2349385293u, 3085804937u, 1272688179u, 1236112995u, 3198431244u,
2677635414u, 811555596u, 3486972196u, 2949678043u, 1342211552u,
788174404u, 1656614077u, 1582629285u, 1477167035u, 2687011245u,
3503701453u, 3351051324u, 2874557775u, 348432514u, 1629591495u,
3991682351u, 1969229192u, 3331660584u, 1304012077u, 2090754125u,
3910846836u, 1871998370u, 2098597104u, 1918921592u, 3246092887u,
1315760974u, 464122393u, 2184028058u, 1690455542u, 2193747147u,
3737423698u, 3511684278u, 1549884962u, 3413774919u, 3938991454u,
2767325310u, 2335626851u, 1626114941u, 601913200u, 3485711542u,
858447440u, 2288468476u, 4075602213u, 1506361431u, 4252489875u,
4032981007u, 1031118352u, 3762145731u, 70955369u, 2362903502u,
1669089455u, 2673510137u, 3348740333u, 2521337794u, 2047144929u,
892246357u, 2319875070u, 1293843163u, 79245769u, 2022600352u,
3866257397u, 989939126u, 835351312u, 3626278636u, 3805332945u,
836506264u, 1895040349u, 970326679u, 634920763u, 733185481u,
1028655248u, 977810701u, 3434484235u, 1871311609u, 2031584214u,
1336174158u, 385787519u, 3965885375u, 2768323462u, 1847726660u,
2718987737u, 793780050u, 2509902580u, 3886434164u, 3120956802u,
4207987247u, 1523159183u, 1884932179u, 2922324286u, 477253416u,
3037922812u, 1108379444u, 697195677u, 1755438379u, 574393398u,
2555059183u, 1930828628u, 1126190880u, 180621093u, 2589191337u,
3424652760u, 3054648512u, 719646637u, 952394946u, 3570038180u,
504304985u, 1395707758u, 1274213163u, 2816553213u, 1369142370u,
1804702100u, 1821782344u, 3358274235u, 2181234724u, 486158240u,
367287522u, 4267199121u, 1127352639u, 779850007u, 3440331597u,
3276765484u, 125500149u, 1142120513u, 3989398167u, 1048565860u,
3136747194u, 432668526u, 2098559576u, 1478877150u, 2484746208u,
1209580219u, 1019125185u, 4160278734u, 1970740713u, 918146921u,
4136433784u, 2602441845u, 2348512686u, 973030509u, 2238261365u,
815637919u, 994690313u, 1724736366u, 2099799816u, 1775069742u,
2680317667u, 730798472u, 2916864943u, 1284417767u, 1698724919u,
2733611686u, 1578128411u, 651006053u, 4243350375u, 3303874296u,
162087183u, 3796616231u, 3801767645u, 4119825424u, 3922537059u,
77594039u, 3419583692u, 2503306160u, 423966005u, 3293613218u,
1124728190u, 1407880681u, 1440346680u, 554334954u, 2919409323u,
1253962019u, 586491243u, 3638308238u, 3097648541u, 991125519u,
458538714u, 2155963569u, 2807866455u, 6862945u, 2122460897u,
53853750u, 3346001678u, 1230879976u, 3071060893u, 423909157u,
3881450262u, 1652511030u, 3826483009u, 1526211009u, 1435219366u,
3092251623u, 3001090498u, 281084412u, 849586749u, 2207008400u,
131172352u, 1820973075u, 3195774605u, 2962673849u, 2147580010u,
1090677336u, 2061249893u, 1724513375u, 3885752424u, 1135918139u,
2619357288u, 4012575714u, 2652856935u, 2029480458u, 3691276589u,
2623865075u, 3459550738u, 2097670126u, 2477000057u, 2209844713u,
785646024u, 1052349661u, 1030500157u, 1430246618u, 3807539761u,
2157629976u, 123154542u, 2560049331u, 2104110449u, 1332109867u,
721241591u, 4136042859u, 4203401395u, 998151922u, 3060999432u,
3207929139u, 2149509272u, 1385268511u, 2023309182u, 1366796638u,
256061060u, 4090836236u, 2929047008u, 2296609403u, 182240337u,
3744374619u, 306855912u, 4014087816u, 2240468995u, 2865233169u,
415452309u, 1244206523u, 3513921306u, 281425419u, 3511338031u,
995954022u, 3102854413u, 3026765331u, 643667197u, 837979907u,
2832983005u, 1813414171u, 2227348307u, 4020325887u, 4178893912u,
610818241u, 2787397224u, 2762441380u, 3437393657u, 2030369078u,
1949046312u, 1876612561u, 1857107382u, 1049344864u, 3544695775u,
2172907342u, 358500115u, 3895295219u, 571965125u, 328582064u,
744698407u, 3066193991u, 1679065087u, 2650874932u, 3570748805u,
812110431u, 3450423805u, 1705023874u, 259721746u, 1192558045u,
1714799045u, 3685508436u, 2262914445u, 3903852862u, 1790140070u,
2651193482u, 2821191752u, 776610414u, 2697125035u, 2212010032u,
1254062056u, 3541766210u, 1853927671u, 1543286708u, 66516686u,
3505195914u, 4226521519u, 1260092911u, 717982876u, 739240369u,
456195732u, 2116515161u, 1599487648u, 838913496u, 850912042u,
3712172413u, 2103192411u, 877020153u, 1458113119u, 2646869271u,
4087221703u, 3771198399u, 3952796001u, 1685641891u, 226245966u,
4065518354u, 3169076409u, 715963611u, 1155859114u, 4174181651u,
1816065125u, 2422210778u, 2353087594u, 2569974907u, 4049024520u,
563593555u, 1794197249u, 2434290377u, 4222178191u, 2381045132u,
1294739153u, 1333544226u, 3011196239u, 518183212u, 2861903570u,
3168787443u, 2315530531u, 1042490149u, 2998340365u, 3534153126u,
2862715604u, 796613230u, 765073073u, 1342937225u, 549817636u,
3786981820u, 4291017601u, 2895722553u, 734959362u, 3175258828u,
140019477u, 268621172u, 2410334776u, 565052604u, 3787587805u,
386344800u, 2874086067u, 35710270u, 817904650u, 1960697289u,
1584484509u, 2724312018u, 1978802819u, 2275314726u, 4216102886u,
2138332912u, 671754166u, 1442240992u, 3674442465u, 1085868016u,
2769242611u, 1003628378u, 1616076847u, 743729558u, 820011032u,
2559719034u, 1839332599u, 3121982280u, 2070268989u, 3769147733u,
518022934u, 3037227899u, 2531915367u, 1008310588u, 971468687u,
2052976098u, 1651926578u, 78218926u, 2503907441u, 3209763057u,
1081499040u, 2812016370u, 1247433164u, 335294964u, 2650385171u,
2030527826u, 1139372809u, 4279827824u, 3540669095u, 2285341455u,
4220507154u, 3863048231u, 3136394663u, 3319584205u, 1476940506u,
875141230u, 2508558662u, 3896001866u, 462864388u, 1609807693u,
3892563868u, 3642514037u, 3778083990u, 1403162576u, 3512254868u,
1403323269u, 1119818229u, 2831288053u, 2552740643u, 2520136409u,
96690857u, 210381252u, 1826474872u, 3306977352u, 1343117402u,
2112059492u, 693571694u, 2096734379u, 767794921u, 1843084587u,
1816280216u, 1695342628u, 404711915u, 3334843684u, 2570639553u,
4186538211u, 2022604264u, 3214805180u, 2989079529u, 2725165355u,
3005995436u, 310011850u, 2742468706u, 2720274646u, 144327376u,
2271696819u, 295519962u, 1272030376u, 1372670420u, 1397272558u,
2280044719u, 2710639434u, 2810822904u, 4271368265u, 1750711132u,
2216408539u, 3521792518u, 3111505866u, 3085328191u, 1054735512u,
4160317205u, 1427385632u, 2282061755u, 3215251668u, 1396490078u,
2933318719u, 453673969u, 2926038256u, 2624047458u, 338625410u,
3344930154u, 1971116345u, 1818716442u, 2998517928u, 390083048u,
291563131u, 1144486353u, 296954266u, 659950561u, 2263631666u,
1206908601u, 1125491020u, 1890151284u, 2076080514u, 2264060846u,
561805191u, 1964622705u, 405620012u, 3759692386u, 517035386u,
2225016848u, 4165419081u, 4052828294u, 3248204933u, 2738939733u,
1151808775u, 4113264137u, 3113447491u, 1033828852u, 1785686386u,
2903923175u, 2038900010u, 1241522880u, 238119113u, 2885394101u,
2636011022u, 2985605703u, 2107193353u, 292026696u, 3884689974u,
1094315383u, 4016714705u, 962244585u, 3943968050u, 2868319718u,
1304919603u, 3626636694u, 3393461291u, 1479454799u, 971639318u,
3352306399u, 1928233566u, 2900529135u, 2190901098u, 28842068u,
990556577u, 2586302532u, 3057504668u, 1661169605u, 4228191763u,
3934152427u, 2814119472u, 4943754u, 1171095774u, 1986204006u,
2014406505u, 1822565279u, 12890078u, 1979620724u, 1917376192u,
3307810835u, 4170173371u, 1385005883u, 1308519769u, 3370429606u,
923886311u, 2024463563u, 1063369787u, 153599761u, 3463680785u,
755374878u, 2088947962u, 3099927142u, 1750207400u, 2033606872u,
926120766u, 655932557u, 2320365045u, 1465119024u, 3105365454u,
2608716819u, 1218456091u, 823539591u, 2331574954u, 3171519129u,
3246671799u, 1043031086u, 1425831588u, 3940307546u, 3443545749u,
1155610704u, 3681098065u, 3287797558u, 63959365u, 810297004u,
3800799806u, 1234795257u, 2547289014u, 391329364u, 370300179u,
2474800443u, 3972311925u, 2935022755u, 3924395679u, 2347599539u,
4212318274u, 1828491430u, 3865565525u, 2767860661u, 4078993078u,
2781496513u, 4013741232u, 2916354756u, 35752471u, 2730683119u,
3340599926u, 4059491907u, 111492530u, 897368671u, 2524912702u,
3046341697u, 2790787159u, 1014602604u, 1409764839u, 512802978u,
477082227u, 2608350570u, 533747000u, 1933326657u, 4182933327u,
1970210993u, 2290203137u, 2843031053u, 2844558050u, 3308351089u,
3041943368u, 1504174920u, 295229952u, 2843309586u, 884572473u,
1787387521u, 1861566286u, 3616058184u, 48071792u, 3577350513u,
297480282u, 1101405687u, 1473439254u, 2634793792u, 1341017984u,
2500741117u, 4263797064u, 2322457777u, 1155622524u, 3736368257u,
3681071476u, 1137217259u, 1527337250u, 1366117744u, 3207345339u,
512022531u, 3628630048u, 4036536846u, 932603285u, 2772624172u,
4144438051u, 2059278872u, 3058844153u, 2745845437u, 4220526355u,
2339537870u, 3263741374u, 2780181639u, 830046989u, 2335972292u,
1514360419u, 3096871669u, 843103547u, 2244100243u, 3573704535u,
4267928843u, 4091363370u, 939208984u, 3295829276u, 454400120u,
3702127846u, 471147023u, 1957060850u, 273122868u, 1428866210u,
1737657854u, 3600299128u, 1925746977u, 2380738123u, 1571168523u,
519113682u, 3279227474u, 911322179u, 2696794428u, 2109856536u,
3315630517u, 1759453958u, 4006575573u, 3262077008u, 4177890150u,
1533579172u, 824755459u, 3314795869u, 596460132u, 4215683940u,
2990441121u, 3634236923u, 402953931u, 3584672586u, 2256594729u,
1577088289u, 2277811099u, 217436774u, 3698567316u, 4190005167u,
2082429185u, 3618893459u, 1689882188u, 3734303933u, 2883774800u,
324263298u, 3183678634u, 139054154u, 2233608349u, 2636817029u,
1493414555u, 3159722767u, 644233309u, 2643671789u, 2517246253u,
2845974520u, 1125905547u, 4085649601u, 190928872u, 1141978180u,
3242413680u, 3948731627u, 1042755180u, 508509300u, 1900103462u,
1344606968u, 2954061670u, 3745707120u, 1542873415u, 1003492034u,
3162556541u, 3470584807u, 1695255693u, 2390285737u, 2935248785u,
4052698114u, 3023860703u, 2163389899u, 1899687290u, 2862238469u,
84085276u, 656982819u, 1421023770u, 4179985759u, 1822395411u,
2722008140u, 1160802626u, 767294975u, 846339630u, 318440919u,
3529265600u, 2125900493u, 1846498371u, 3375757997u, 3812947227u,
1995784281u, 1680118162u, 3792592105u, 3303321146u, 2780428251u,
1704206566u, 3879390424u, 3472541629u, 25656479u, 3243031424u,
2978825284u, 1620901527u, 2512940888u, 927794181u, 452523305u,
3394773138u, 4253391568u, 4077229251u, 987808226u, 1406882831u,
1429828258u, 2883058504u, 2960876800u, 1883965824u, 4129270661u,
3579857811u, 973235694u, 3302203860u, 3969586611u, 718348498u,
3763448734u, 3702177983u, 1854328632u, 4251468518u, 2022446019u,
2209431908u, 2414211768u, 3797958050u, 3597530801u, 2525552689u,
636981785u, 664656278u, 2745678888u, 858404277u, 4276042326u,
1747857698u, 2746176763u, 3215666565u, 1887716830u, 3545855489u,
121927034u, 3392865382u, 357130402u, 1368051231u, 2277909715u,
2293787949u, 3358670926u, 386335223u, 3163867151u, 479772539u,
816735136u, 585372041u, 1124539534u, 2914789461u, 1942376489u,
2126769104u, 1975800425u, 814799998u, 2893249499u, 2126033825u,
760007658u, 633972488u, 806727295u, 236112176u, 414407704u,
3653783114u, 1391030845u, 2407584835u, 731546725u, 3992639691u,
106232033u, 2992162823u, 3567584453u, 2503068146u, 1051529903u,
3502104364u, 610035711u, 3775335972u, 667618167u, 4247343049u,
1301421152u, 2243584u, 144192006u, 3717030438u, 1757884509u,
2630952942u, 3363490445u, 4251803751u, 1904267860u, 2266368667u,
75111294u, 2059537251u, 1227434503u, 3441761728u, 4086217716u,
978577973u, 735792426u, 2139298718u, 404370445u, 3869131990u,
1176441999u, 2468151139u, 864851519u, 3630012660u, 3234610115u,
3172435896u, 3439750920u, 2516795165u, 2517212416u, 1059716705u,
2134575208u, 2862235859u, 2538210759u, 358555951u, 2442940989u,
2688476819u, 794989882u, 2838735245u, 3872585781u, 3134260357u,
105064119u, 3825751229u, 1135488310u, 4218960221u, 3360877465u,
3302954754u, 2575700988u, 2497293657u, 2388927109u, 3987074240u,
414604988u, 2491469147u, 3980520027u, 72941163u, 1711077678u,
519087922u, 171381824u, 3705314333u, 2513057424u, 2080037686u,
1774744635u, 3628627514u, 556341778u, 899387995u, 2615372983u,
2372073252u, 237968744u, 2705328516u, 3643402537u, 137400382u,
1941599746u, 2640174030u, 2083120893u, 1556545397u, 289682033u,
212740831u, 949213043u, 2102687076u, 2767525426u, 826825825u,
4191165775u, 528640652u, 4077394318u, 882590735u, 3163125263u,
629276741u, 1807552501u, 812058805u, 2945204393u, 183190693u,
2947275637u, 2728154303u, 993281047u, 1210608922u, 4272525031u,
2313255113u, 1870857999u, 2985702525u, 3194565035u, 2143686960u,
1451916006u, 2301248018u, 1558711357u, 1912047123u, 4251516193u,
532285070u, 3114187491u, 2106068513u, 3597063679u, 3663599168u,
1709549131u, 3753489627u, 3658005357u, 1160905342u, 737028908u,
895334719u, 4069027351u, 2426568775u, 1507089618u, 2750118357u,
1653041143u, 1791125727u, 1716827395u, 884658094u, 3085360311u,
4071341754u, 3590238451u, 352493133u, 4083973780u, 454018536u,
274798275u, 610061980u, 2854116038u, 714942167u, 757252280u,
2666997071u, 1593252771u, 2464064684u, 723272092u, 223672858u,
486201858u, 3999479492u, 655297946u, 3129578082u, 1698731657u,
3169005768u, 1702847708u, 272320271u, 120106603u, 3695564069u,
1932873871u, 4013239442u, 423242330u, 4227958558u, 3934266541u,
3689114116u, 2002816339u, 3373950165u, 3217483675u, 2204939216u,
3132445400u, 762796738u, 3162414255u, 1711928854u, 2819853427u,
575230348u, 926867967u, 132669602u, 221159232u, 4033582912u,
252108313u, 1294099693u, 1809928527u, 1269308130u, 3480686231u,
1429950454u, 1360727790u, 2006042568u, 3797144724u, 2783990950u,
1757106005u, 108354209u, 865723626u, 3617249860u, 109520212u,
2401026515u, 285359527u, 3668331347u, 2905102117u, 1494129763u,
348216553u, 1915669884u, 1414811767u, 232956812u, 1587333052u,
760671069u, 3422476798u, 2846738947u, 757998238u, 1420899728u,
398188339u, 3858968607u, 256042460u, 507472720u, 1232254610u,
4245222671u, 3075136024u, 2319205464u, 2119746088u, 3036187191u,
3887480239u, 4292783817u, 1737542162u, 1236303522u, 289379017u,
1780360736u, 1610718605u, 1996472339u, 3644617197u, 3281170667u,
1566409334u, 3514159615u, 612510353u, 430448254u, 1811185798u,
765006468u, 3732165767u, 1544620190u, 4282260204u, 243544799u,
2292191785u, 2241481909u, 1694649590u, 1442460355u, 1427073089u,
754492744u, 184820092u, 897419112u, 3678705335u, 3887604945u,
776070980u, 2900783033u, 1431582005u, 2012055595u, 1852695797u,
3917579167u, 1406433072u, 446726308u, 1084867033u, 3202096017u,
565067593u, 3162244645u, 388787811u, 2413176429u, 4089423644u,
791107632u, 1200634140u, 2565003219u, 2483173661u, 1288219555u,
1516166336u, 576053616u, 1361342997u, 913116636u, 3336073388u,
3843745245u, 1589908914u, 306887506u, 822428140u, 1041471861u,
47350214u, 230873349u, 1684806060u, 1897181775u, 3894132289u,
57050902u, 4240348943u, 3853407495u, 3044803004u, 844640504u,
2739986313u, 401023306u, 2667408852u, 1320130763u, 3973251787u,
1958752748u, 3782783511u, 436666731u, 83547082u, 4275166304u,
3094116720u, 1426327861u, 2538655628u, 1277094853u, 242713550u,
266482191u, 2743531761u, 1280948101u, 1273335605u, 199077170u,
1995269917u, 2170797334u, 4071342218u, 3270299293u, 2370531852u,
2710424997u, 2162130831u, 386081723u, 572675806u, 347301455u,
3062850063u, 3338222668u, 3973274791u, 3887524097u, 3880712621u,
2292533076u, 2732854883u, 468813770u, 1468745823u, 3546822021u,
2850369516u, 1452118653u, 2833005065u, 1262604654u, 1161523326u,
3205391754u, 2758572095u, 44395426u, 1843630982u, 208079731u,
3445477275u, 2868677914u, 1426717537u, 2591875243u, 3051602711u,
2259592887u, 2810102394u, 3134078220u, 1033606524u, 3037630581u,
3947578497u, 3355988886u, 2593461472u, 1236851705u, 1646026810u,
2974402225u, 3350613492u, 2390878749u, 2126029173u, 1703043827u,
3801306369u, 264529892u, 1709343735u, 3350828389u, 1193733634u,
1449911677u, 1041642862u, 2610764215u, 6405054u, 3183661914u,
1696457265u, 450169463u, 867572082u, 549276402u, 3316035838u,
2360256790u, 2613301818u, 2084044430u, 3346024089u, 3824563931u,
2144873191u, 3431508285u, 1651463044u, 3153970916u, 3567962109u,
220468773u, 549571972u, 313039992u, 1072303166u, 380222551u,
2161023965u, 3428890854u, 550663883u, 4050189100u, 4203427051u,
2936536013u, 3121879936u, 567291980u, 959491494u, 3104078241u,
2931645971u, 473964590u, 1927186295u, 504627954u, 2886471106u,
2751862512u, 3905695311u, 1412246296u, 3602455955u, 2808101279u,
910058066u, 3217495121u, 4084815289u, 2504763616u, 3770515788u,
3178414637u, 3045433914u, 1008573896u, 4169182346u, 3156618604u,
1816382062u, 4168688896u, 3596074775u, 3723437259u, 400803335u,
370374482u, 2892345381u, 1573833307u, 422498541u, 1585696786u,
2995703619u, 2942174909u, 927503844u, 2568139773u, 3340754484u,
3390292334u, 346761085u, 1579057249u, 1740755247u, 884882916u,
891164653u, 372229989u, 365212537u, 3315430932u, 2229872005u,
883365323u, 4202570990u, 1667613977u, 713352031u, 2369870728u,
3944817852u, 983346721u, 1308899441u, 2757113982u, 2494900868u,
2080827335u, 3624427103u, 652171563u, 1666757625u, 3358372252u,
25827967u, 432100882u, 42605297u, 1263005308u, 852004783u,
1019509360u, 1689563162u, 2280078981u, 844049518u, 392984060u,
3587407155u, 1740816471u, 3348953483u, 450311223u, 331586083u,
482255964u, 1251638867u, 3369092147u, 1183178495u, 1252284967u,
2670206902u, 2592156382u, 3956400143u, 4142163820u, 968164509u,
1857508915u, 1223187601u, 2983937972u, 363499219u, 3256011603u,
1407877715u, 1858184655u, 223762808u, 2815342624u, 2623728343u,
471394359u, 2338922152u, 4010468018u, 1494235404u, 805138023u,
2263304220u, 1143229406u, 4294371569u, 3426654861u, 3673268051u,
2094242240u, 3878198506u, 3302650596u, 553215323u, 1700836024u,
2644918481u, 1172263171u, 3566289616u, 159921530u, 4242701100u,
2891779620u, 2772910690u, 1844965307u, 3222652689u, 1940205226u,
3252887615u, 2619316586u, 2863214944u, 255135220u, 2319400461u,
1356399792u, 3136420082u, 3318816270u, 3348965492u, 2991156919u,
2098723029u, 538297620u, 2550174061u, 558996197u, 4153977074u,
396650285u, 336629528u, 33587922u, 151050341u, 1817240964u,
1598635540u, 2815665370u, 334635542u, 3104928583u, 3368059279u,
2281526556u, 2049214434u, 467369481u, 1892587657u, 2713415926u,
1210292261u, 543312793u, 2219660615u, 576828305u, 1579949228u,
423458407u, 506340086u, 610002369u, 2571074778u, 722633826u,
71222137u, 842882706u, 2009087692u, 1363565258u, 457448717u,
1359052209u, 1454830478u, 934427297u, 373198223u, 1078216524u,
881146725u, 3835072521u, 2223843980u, 3020320737u, 2047751094u,
2386876295u, 151140833u, 792136558u, 3664204416u, 910665524u,
4082855445u, 332202002u, 3663329916u, 3924742864u, 4210357809u,
3035318721u, 3703582172u, 2395685358u, 3527486801u, 1346167233u,
3945460735u, 713838878u, 2569385804u, 2673605345u, 3550969220u,
4243147364u, 2309000764u, 731999942u, 3921900019u, 1107209281u,
720619514u, 1704240103u, 81125990u, 317805114u, 3678640075u,
2938170218u, 3613685474u, 1728244724u, 3385237271u, 4221245045u,
3133258246u, 1727367040u, 3154857385u, 2665765720u, 2518841063u,
663013272u, 2419053996u, 1637865178u, 3969548484u, 692065125u,
2599473883u, 3256068101u, 435175331u, 3741393791u, 2658647268u,
1506574630u, 3151733449u, 2944353448u, 1249681632u, 1263358766u,
1368483368u, 2279035519u, 2464850890u, 3575231217u, 2754206804u,
2566200848u, 238034272u, 1440151198u, 4208701947u, 1285161672u,
3403832724u, 1943870151u, 2745258239u, 1815249255u, 1392971118u,
1544497359u, 4177624680u, 2397962695u, 2169967634u, 3189208041u,
3957569271u, 1822504027u, 2446464090u, 1844069058u, 1917044074u,
536324405u, 4142347706u, 104943297u, 516241068u, 1246336192u,
4230215670u, 1363740512u, 987712840u, 2807577755u, 2564077993u,
4110008491u, 2449624894u, 4018933476u, 3284119631u, 1966606846u,
1770310834u, 1032846869u, 240023392u, 3280916673u, 2173260788u,
3261286273u, 738911634u, 3181059220u, 2272149255u, 3194117094u,
2295733216u, 454924713u, 2932109539u, 2927279746u, 2029061725u,
1989689036u, 1420837132u, 911234017u, 1608529501u, 423134779u,
592387170u, 3537225433u, 3132705035u, 751661097u, 1414330162u,
702527398u, 2836854972u, 2860393334u, 273776580u, 3841373097u,
3897191802u, 2218600621u, 449503320u, 3018083450u, 426281553u,
659665656u, 1685861555u, 4095066912u, 2859028254u, 2323079437u,
2128578931u, 2919434878u, 1985959120u, 157036961u, 907467960u,
3475504086u, 1758801206u, 3215293590u, 462673225u, 516199313u,
2101618132u, 2255051833u, 480276182u, 1399444775u, 1540169926u,
2346982492u, 1248385475u, 1713179789u, 1407905589u, 1782812514u,
1112519953u, 776262767u, 2341647152u, 1096877715u, 299066250u,
88200511u, 74481227u, 3967156568u, 579473510u, 2807619625u,
3850609488u, 4005544769u, 3188251219u, 702280284u, 2592713719u,
3956082585u, 4092611494u, 3413029630u, 3926299537u, 2479889188u,
1040891653u, 1889938488u, 3874351210u, 1106442576u, 1903244241u,
3229585166u, 2416701998u, 982127964u, 1508122208u, 275681456u,
157531183u, 3295655144u, 2421430989u, 2882791436u, 1491165734u,
3071814346u, 3314520194u, 2757630249u, 2706643074u, 1799798708u,
3833725166u, 1678310352u, 3702234087u, 3505295054u, 1450032842u,
1363342287u, 2850921603u, 3498421664u, 2939309820u, 3389044949u,
1718335002u, 3660445557u, 78993494u, 2171692745u, 17549235u,
2730144888u, 1676319386u, 4084060395u, 4294716373u, 1906811545u,
859270623u, 257778878u, 2697422981u, 3722662433u, 3949147603u,
2710934973u, 3662672644u, 1525029711u, 3555554520u, 4282096432u,
3966879769u, 962809256u, 1184851100u, 2802256012u, 2770295670u,
2598415034u, 1796104491u, 1663206446u, 4260805312u, 610689191u,
2021836756u, 107953943u, 2900545767u, 1808663339u, 4008622457u,
790704710u, 2452868627u, 3117181052u, 1882665914u, 1590695627u,
1374587697u, 3614473030u, 3931887505u, 3153492485u, 4218122191u,
2452537456u, 1201324194u, 759586707u, 84942475u, 4111933087u,
1444391735u, 1139549443u, 3805974531u, 3971044720u, 477880684u,
961086587u, 1340362124u, 1604444345u, 2254105549u, 375811159u,
512712169u, 2749279630u, 3267939599u, 775743625u, 1342835433u,
193493042u, 1241189548u, 3106006437u, 1399344769u, 1492233317u,
1768053880u, 2837327654u, 1131098881u, 1648703102u, 2089150983u,
2694432705u, 973706044u, 92985242u, 3999906913u, 3910868338u,
191327779u, 3438373242u, 4193928044u, 3203390558u, 3362940567u,
3492292949u, 1934984940u, 1646288108u, 918962490u, 2651194120u,
442802528u, 2471731585u, 2340716146u, 2276554727u, 2302476915u,
1181415588u, 2868758587u, 1067853265u, 347176489u, 1939773730u,
2777887450u, 978019153u, 625959233u, 3455084654u, 1731268224u,
4235285461u, 3944667737u, 128814437u, 1818688919u, 2300660171u,
2758723882u, 373993792u, 2644214523u, 3444956489u, 3434458008u,
4248345024u, 1901574406u, 287531999u, 3007537762u, 4034685229u,
3517853408u, 78071904u, 1139716314u, 2937064484u, 239252817u,
3366122534u, 3038632949u, 2294103376u, 3438832446u, 3802589858u,
4154544779u, 3861196633u, 4260830112u, 2688381633u, 181409553u,
592142795u, 3965383578u, 935450750u, 269811790u, 782289952u,
1638485324u, 179614966u, 548548887u, 459310932u, 1886180225u,
2647604623u, 36947705u, 4035813282u, 3753815615u, 1522375757u,
3809696647u, 1763638499u, 2226920609u, 4227748553u, 1313305235u,
4061231705u, 1702505565u, 2906166764u, 1729326608u, 4244725906u,
966149927u, 3293515724u, 2367813487u, 1446112345u, 1227910659u,
2844908425u, 1594427357u, 1048681939u, 212427838u, 1269193978u,
3496717749u, 2921343850u, 2668456969u, 2267084882u, 1334928840u,
1767780686u, 983963396u, 2588311435u, 1850331400u, 3223459079u,
3111775696u, 2506255888u, 3702554614u, 2369930792u, 2929647161u,
2506416716u, 2479117917u, 2198249807u, 3444428083u, 354733066u,
717644749u, 3090530204u, 2738017268u, 4278457915u, 4258807760u,
1522713227u, 3905745313u, 4171524857u, 2035336180u, 1487986097u,
2620568311u, 3807676884u, 3856083492u, 1952899566u, 3060080941u,
1775656683u, 1827822866u, 935152116u, 2266271948u, 539682350u,
981783224u, 1326778049u, 3842197721u, 3118594795u, 467228000u,
3362409922u, 4079824256u, 2979795106u, 1709741046u, 42100360u,
120392511u, 3621573700u, 1920136592u, 3961385783u, 884407395u,
3311223137u, 3826235090u, 183222673u, 4039028327u, 1624297109u,
326318752u, 3025115648u, 594985212u, 3133234670u, 2207588835u,
963262671u, 3724108540u, 1155581262u, 3462905334u, 2890646829u,
3607969926u, 2050813368u, 3936879051u, 2678841578u, 3541348965u,
1015523243u, 2818254642u, 760740720u, 3880905941u, 3563291220u,
1196395351u, 3293903482u, 3540091169u, 4013553601u, 2934740932u,
463379296u, 3078765390u, 782661164u, 3353858244u, 425610981u,
2844388125u, 2103519494u, 3224691896u, 829982391u, 868188911u,
3847825001u, 2442903745u, 425586795u, 2785754810u, 189689674u,
2997051076u, 2393564453u, 2738132518u, 3317841037u, 3475188031u,
1339772322u, 3390183362u, 768723894u, 3115470760u, 1455803558u,
116426970u, 902568622u, 4093525619u, 2191088390u, 585691733u,
3892805143u, 897281696u, 2701207772u, 561461717u, 436084723u,
3742605163u, 1678708375u, 3817938705u, 234576607u, 27356943u,
2152993718u, 2986534572u, 1854228316u, 3521019125u, 4284489069u,
2810677824u, 3485806537u, 1976235678u, 2085858020u, 3148717547u,
3841623852u, 2435052650u, 590758137u, 1905986752u, 1675058364u,
2257780991u, 3982964645u, 2430544059u, 3940605995u, 2752661619u,
3064777055u, 2559949677u, 2655738818u, 3295104124u, 1474410264u,
2912446382u, 4020206781u, 576447599u, 535900431u, 1077310659u,
3137840249u, 1423157467u, 2776599449u, 787981617u, 3578360533u,
2556456226u, 1710609124u, 3325599781u, 3220461886u, 1478864177u,
3587244773u, 1268625412u, 1384956853u, 3882391248u, 2371945596u,
2045842833u, 4205327602u, 2464830712u, 2359262182u, 1171364609u,
1419158616u, 682715999u, 2660610073u, 2991823783u, 1548922277u,
831618797u, 3249183760u, 597636688u, 1777690202u, 458256856u,
2114606129u, 1299095260u, 2983899478u, 1264581214u, 4177860236u,
17273196u, 1407696854u, 593370470u, 3598337265u, 3195346021u,
3174291042u, 741107679u, 4098148086u, 2795583024u, 137106654u,
3452336576u, 1532740620u, 2229449622u, 2846076572u, 380183779u,
1209039979u, 2995172882u, 989487735u, 3715237075u, 3054273866u,
1955734715u, 2682520233u, 3818975284u, 2536644837u, 2284983225u,
2836559461u, 1389069601u, 204245791u, 777929392u, 1498019328u,
2401467298u, 1938493040u, 1071806041u, 1034679075u, 1620524703u,
3071094964u, 439558162u, 3677274935u, 4238774239u, 1209066361u,
1088039431u, 3139839398u, 1795448587u, 591687111u, 1875516399u,
3593696961u, 3145148511u, 595289847u, 1648586281u, 2526340071u,
1268107314u, 1572631480u, 3645616041u, 3465005871u, 544293197u,
2163721987u, 2048400380u, 2102791667u, 3372026220u, 3766895552u,
4286553780u, 1516732531u, 3412212465u, 1930345401u, 117250582u,
4138331062u, 4120218221u, 181667649u, 1440931813u, 4178824234u,
201952914u, 812637199u, 2602482807u, 2865259846u, 4183543706u,
2518738954u, 2969539593u, 2899585754u, 2896888904u, 1550577888u,
862479326u, 2664075557u, 897196313u, 3483866497u, 3708057157u,
82710238u, 3717454735u, 360233959u, 3097186829u, 4186741298u,
86621536u, 2797524946u, 1609114124u, 993158854u, 1345445936u,
1732981263u, 2140204917u, 524074125u, 3131818693u, 1152935964u,
3070648776u, 1107440887u, 541231638u, 1424491339u, 3438607874u,
653840126u, 1420721291u, 1494681525u, 1776801700u, 522519102u,
1413795107u, 3797408458u, 2643175199u, 404922594u, 1348222327u,
3994494069u, 3366587261u, 1713777698u, 2879553944u, 203587743u,
2308248086u, 1470483001u, 3099400086u, 3160950562u, 3134392672u,
3413133866u, 2746553770u, 2340353022u, 2732453903u, 2947307338u,
438129945u, 3838123218u, 492730903u, 235328936u, 2388344531u,
1304215689u, 2005591534u, 198391212u, 3193756469u, 839566305u,
393940610u, 3093088558u, 3423367095u, 3099906696u, 2343498361u,
3770118303u, 4168129773u, 2501530535u, 883925372u, 303586901u,
3868847116u, 3963157752u, 3157301259u, 3437571950u, 3392902953u,
1228132404u, 1707178093u, 2335015782u, 3904565878u, 4229581755u,
492138180u, 3073813901u, 640665822u, 3603346999u, 922161726u,
1860839953u, 560459819u, 2021317766u, 297881981u, 2408245790u,
384530297u, 1155739363u, 2562994192u, 3217009820u, 4110041205u,
2164181515u, 519027455u, 2778026350u, 3674648725u, 1321757186u,
3531453112u, 595817782u, 2027376578u, 2042570202u, 2888809226u,
1556750754u, 704400727u, 3384921396u, 3289703113u, 3351345046u,
1037627351u, 2871238084u, 2307943700u, 573394694u, 3105141941u,
92581831u, 882519770u, 2404497529u, 2508795700u, 1292007850u,
620527306u, 4034734001u, 1963769227u, 4212949030u, 1791638453u,
1231025186u, 1700222598u, 3439496951u, 1936785558u, 3848768958u,
2681320752u, 2566357103u, 2405639388u, 3796822945u, 3362218643u,
4053296118u, 1293805338u, 2358616019u, 3463138327u, 3128397576u,
3015879164u, 2477158023u, 1475962738u, 111057009u, 88496518u,
1917835954u, 1662174364u, 2775845786u, 1363900744u, 2238549646u,
578031776u, 1599070698u, 1870290001u, 4024962733u, 3205774627u,
3562816366u, 40250330u, 3646794336u, 4283270024u, 1600022383u,
1209132687u, 2547708346u, 4168140719u, 3747584726u, 3382580702u,
4009358868u, 4201204527u, 2871032209u, 661220876u, 888098135u,
1666178348u, 2808266895u, 3943189777u, 309459048u, 2163423368u,
1746878799u, 1974582532u, 2864449124u, 509670988u, 4010321183u,
2575074271u, 3483003844u, 3644480339u, 2081118997u, 652915824u,
3250213093u, 2752162620u, 1791205177u, 3047448045u, 4173789058u,
348953149u, 4243319035u, 3095301674u, 3711485381u, 14525930u,
1670243072u, 3689494100u, 1953101249u, 4234735905u, 1059513456u,
831806169u, 3369071539u, 1444988928u, 3791758648u, 2638473230u,
3924361789u, 3909317902u, 2397815488u, 108384758u, 2572118926u,
525129562u, 639420665u, 669144050u, 3864239974u, 3201253704u,
1934425697u, 433412542u, 883355992u, 495200818u, 3863971557u,
4033311018u, 3275279952u, 2148897016u, 3790249833u, 731766156u,
1223851860u, 3678193481u, 2891483608u, 1426705768u, 2853060454u,
2263653682u, 527486390u, 1913529154u, 1749419299u, 1353895017u,
1182348463u, 659872483u, 3078073095u, 1352634951u, 1217126631u,
3663266877u, 3849144771u, 1728881200u, 3550129307u, 4033329575u,
1675151111u, 1759466246u, 2138476840u, 3303545893u, 2984165585u,
1559521459u, 3583587581u, 2754204271u, 2618339581u, 3734997486u,
2468477297u, 3982798873u, 1400340476u, 1775731536u, 1960328724u,
3992723360u, 3065728698u, 1881136493u, 3798490745u, 3473259209u,
3096051547u, 1515970810u, 79941263u, 1441182150u, 2898142851u,
1399408592u, 1883381057u, 416509126u, 1880423351u, 3093448915u,
502669317u, 27468357u, 3499031203u, 1762592447u, 1395243464u,
3871613901u, 1057541701u, 267568056u, 1471942076u, 3842828346u,
1613585440u, 1973730051u, 2347430656u, 1449022602u, 2413428676u,
1816723564u, 1700043520u, 935486730u, 1709959123u, 418061874u,
2213485346u, 1066247998u, 2824072173u, 1935834272u, 4084149685u,
1854534142u, 3102463245u, 1791912859u, 1718329419u, 1895590262u,
3572860213u, 657834953u, 576978784u, 43442786u, 259702811u,
3218038282u, 361838311u, 4090401236u, 703937918u, 3905131145u,
1392513962u, 318722468u, 1295906647u, 2204048009u, 50169489u,
387845619u, 2318874730u, 137969335u, 409622605u, 505726246u,
629276521u, 643912174u, 2710730823u, 3662425714u, 3690753083u,
1056548235u, 4184250032u, 3922653458u, 2451732360u, 3394781897u,
4281439047u, 4108402885u, 2377442948u, 1495144293u, 2213877196u,
2950896548u, 1420268666u, 2523549781u, 1846843665u, 1787890598u,
2112291765u, 4187105389u, 305101977u, 28097139u, 3812810910u,
2427959932u, 277599151u, 3192572462u, 1873400110u, 3204284336u,
3550346696u, 1186049286u, 1694513554u, 4015601921u, 2634854552u,
3468396689u, 3516035178u, 2194659629u, 3806350498u, 1790891005u,
3999094007u, 668799895u, 819413823u, 4265177898u, 1110602326u,
1230733198u, 3856303761u, 1152893805u, 2548469791u, 3362430037u,
2163976689u, 261211212u, 2631997142u, 3049954710u, 3519391742u,
2684474998u, 2284446581u, 3767319453u, 867905936u, 1477946054u,
1949457599u, 3082436333u, 1837863418u, 1909772278u, 4149164990u,
777712915u, 2663116186u, 2580037763u, 2986677112u, 1805877811u,
3093083469u, 47479577u, 1489903495u, 1265001771u, 2220456937u,
2751664031u, 2390985243u, 2999864559u, 672141846u, 3231315389u,
2414012330u, 1906819045u, 2984157392u, 3741192015u, 1831612599u,
412535655u, 3591754091u, 3679838215u, 3141283535u, 1326459140u,
1546321559u, 2053959246u, 1950827292u, 2489596315u, 1659531982u,
1336558483u, 3330981825u, 97580289u, 3153670395u, 2324499306u,
1848029250u, 3326835115u, 2979644611u, 1264461714u, 4059661017u,
3104006826u, 3368253358u, 2397455377u, 3030408045u, 3174369033u,
469586980u, 951616564u, 1674739403u, 3784254295u, 2537916485u,
1629754480u, 1973022275u, 1402612676u, 216208581u, 2781646564u,
982205675u, 4075937534u, 3582814745u, 2136790623u, 67193454u,
468091581u, 3709609904u, 4109050590u, 335304015u, 3973380988u,
2873516039u, 1614829131u, 2148391288u, 1996647808u, 936276241u,
1659295594u, 2455070843u, 4092282313u, 524798420u, 958595957u,
2882637010u, 3874299566u, 2575200323u, 45864893u, 240415769u,
2863710934u, 241991393u, 4026751870u, 654985261u, 73118816u,
84271844u, 9504786u, 1869064740u, 105677904u, 3574364025u,
2599606066u, 2651670594u, 438506082u, 2233938841u, 1670640089u,
3710285779u, 745377473u, 419609375u, 2602573397u, 3900054502u,
2650521038u, 463928187u, 1172984423u, 2220484190u, 1095807452u,
614850457u, 144205315u, 2402478324u, 1451658947u, 19669332u,
3097977779u, 3292874081u, 4095144717u, 3645178392u, 463290186u,
3937717357u, 3760375802u, 4238996472u, 1930769438u, 2169530151u,
1121118212u, 1165746984u, 3261547512u, 432720133u, 3457041397u,
2181194120u, 1036791209u, 2515172049u, 1493671637u, 3276575128u,
3151035990u, 356321858u, 1170285938u, 2841534012u, 3818274169u,
2220407942u, 3339536836u, 734645661u, 1250564386u, 4031075337u,
632013612u, 2536105946u, 1968372804u, 1892511539u, 3134146239u,
4045511005u, 3378295560u, 2817128396u, 3086852652u, 1941092040u,
1186603069u, 3606472960u, 70669832u, 2287600530u, 1638569324u,
2378926845u, 2315380185u, 2920859214u, 1455582985u, 1577068627u,
3591589856u, 1027745331u, 2126182285u, 2486457443u, 3623598128u,
3723251533u, 3911666366u, 1747092880u, 2402125269u, 483678340u,
1575314013u, 1906303350u, 3383365516u, 1289282189u, 1339901439u,
1723943420u, 2439753462u, 3579269267u, 363627112u, 1733571930u,
314184313u, 1675792864u, 4020770502u, 1548116196u, 2273911152u,
602392177u, 2838838375u, 1117250656u, 2740063266u, 372868020u,
2552512122u, 1844247494u, 4264502803u, 1105021132u, 3544737911u,
1277990640u, 2641105602u, 1824752961u, 3181211334u, 511991294u,
2236096341u, 2126296232u, 3094295258u, 3033995959u, 527724412u,
1046139663u, 2931463347u, 3371850311u, 3083598147u, 318212288u,
2898050586u, 1691716442u, 2861896595u, 14577642u, 2030754905u,
947800038u, 246325017u, 5585911u, 1615345507u, 812520481u,
2683069823u, 611964371u, 490907220u, 1151377635u, 2292093180u,
751155690u, 2811469882u, 595492796u, 4108972367u, 2572194110u,
4103704225u, 3870014217u, 3853331788u, 4034605360u, 3891903368u,
949980031u, 623024259u, 2073057785u, 1616375580u, 1614955440u,
2929877158u, 2249618123u, 2290570578u, 1137619107u, 3073303314u,
293592020u, 3539009164u, 1874010544u, 18293765u, 746693114u,
2924999677u, 112129180u, 3183436706u, 4100311944u, 3942948478u,
1849397958u, 2492102702u, 4129862629u, 89745884u, 3274545262u,
3595635232u, 31562271u, 2564379334u, 2920743717u, 1180122591u,
3032035420u, 1353651248u, 2770807059u, 25081401u, 2372152730u,
2069576326u, 936769856u, 723606552u, 3317287620u, 1611064790u,
979374201u, 2204611921u, 1592851823u, 4191754721u, 3826510149u,
720641424u, 3678110796u, 3723533932u, 1728438917u, 3122163332u,
1365881714u, 1765132094u, 2614069276u, 2921135690u, 3909258731u,
1560697876u, 3904546998u, 1269385037u, 2540878633u, 1980234534u,
1428383314u, 2964988624u, 3663880395u, 652791181u, 1900084498u,
326298089u, 3884177206u, 2537320201u, 142504470u, 2075689920u,
2286754314u, 3471190679u, 3077332658u, 4148280726u, 770095561u,
446553822u, 1445397914u, 2998794260u, 806220989u, 2035613576u,
1382666746u, 464938132u, 1734551383u, 940041372u, 2356074312u,
1821789369u, 209330661u, 812406143u, 2373966445u, 463302805u,
1180306011u, 1656902011u, 1037242088u, 359039185u, 1044300592u,
2379839739u, 662109823u, 74469949u, 4107776963u, 4280041364u,
4018634993u, 4291500862u, 3516351734u, 2761187869u, 3127860814u,
2593569870u, 755105602u, 3113400158u, 1547781563u, 3331942386u,
810846783u, 846702952u, 5147099u, 434277085u, 1359011478u,
979453305u, 3004832082u, 1651070055u, 2685450541u, 3023061945u,
2332434296u, 1449076389u, 1885650424u, 4063755770u, 1234490702u,
3464987032u, 2154609442u, 2310908165u, 3270815960u, 3468813887u,
3274517632u, 503947210u, 2474141277u, 1287887592u, 3211187438u,
1624803533u, 2772549594u, 3171469972u, 529223794u, 3413509397u,
2166372317u, 3391791557u, 1491475969u, 1785826673u, 395771269u,
3844001065u, 635008637u, 2943484153u, 851132384u, 152778962u,
2887378673u, 3751896912u, 1853326403u, 2472544967u, 2982442106u,
310002530u, 1102881285u, 2867283667u, 41913069u, 3504408015u,
2286138391u, 1935548655u, 1199979353u, 3426129152u, 4064027578u,
1591439016u, 3893144160u, 3401059997u, 1686567419u, 2610861827u,
106752445u, 66861635u, 2883799100u, 1424012493u, 3595620492u,
2699922466u, 4172559189u, 888884433u, 244524878u, 2283218712u,
1934126058u, 40293409u, 2501690904u, 2261381514u, 2949086966u,
1806374300u, 3089940133u, 2157022662u, 2791903748u, 3568420276u,
3122074238u, 2034253194u, 1605663501u, 1405079440u, 2497876014u,
3669352834u, 498725211u, 4140305918u, 247623610u, 1595801470u,
4208059585u, 1440824281u, 1223308576u, 2146301246u, 2555395148u,
2596810779u, 4132450170u, 2372835596u, 797911580u, 1831738774u,
829099694u, 2207504167u, 1467350244u, 2190713264u, 4006765973u,
140374436u, 1677904306u, 722287139u, 1173456818u, 3433373317u,
652607730u, 3578901879u, 1705569489u, 2756232453u, 1609420758u,
621700234u, 563133390u, 372364134u, 1868485656u, 3193050428u,
393046075u, 1655111696u, 2639802682u, 3745421913u, 47154834u,
3533792021u, 2462134617u, 833305539u, 3391863910u, 1193916378u,
1010892576u, 2314992090u, 1924230043u, 173327386u, 2445374764u,
3344539005u, 263717207u, 344458992u, 2131544513u, 2844286976u,
2758722915u, 1914807185u, 950329081u, 2499332236u, 3595130050u,
1404646615u, 4170736375u, 1208124202u, 3635143895u, 115864937u,
2173251121u, 1455416724u, 1197761604u, 3962211850u, 3206696551u,
856644982u, 1017608232u, 3649849172u, 4111766657u, 2621815082u,
2663996565u, 3485608353u, 2578106283u, 1608204161u, 741330692u,
230735732u, 388036276u, 3976257312u, 1096342811u, 3792877416u,
3687532372u, 143297888u, 3913003182u, 4134793368u, 3004904148u,
2873860186u, 3114634496u, 330405231u, 987353207u, 872230598u,
2474130781u, 489623837u, 3481621200u, 2178025230u, 1734494073u,
1599344169u, 4245314329u, 3047428366u, 386541963u, 2019633251u,
1378431249u, 961885261u, 2196484647u, 3638700902u, 260302352u,
3535293420u, 3116805903u, 1440364029u, 2390388754u, 332129148u,
2273583462u, 1740904163u, 3564747422u, 1320315490u, 3688341980u,
1943868361u, 3388853410u, 1775902309u, 1365082575u, 1522292425u,
1942216237u, 123405003u, 3230794558u, 335674543u, 471852445u,
2319546878u, 471339877u, 1623550474u, 1159141530u, 716060172u,
2253300242u, 2246457388u, 4177504571u, 2957827037u, 3051182067u,
2961392703u, 1339428272u, 1253728860u, 1251798837u, 2071393845u,
3652256935u, 3481290805u, 3915495864u, 4240793738u, 2745670169u,
223281082u, 1096807079u, 810830859u, 380816886u, 2578459915u,
3600280332u, 1900744475u, 2511347346u, 2563321948u, 4072096018u,
1553950434u, 262117258u, 938413725u, 2511015293u, 1852340894u,
1224529889u, 2111115142u, 3555082594u, 3061142695u, 820280543u,
640858393u, 1900651720u, 424329571u, 1689689543u, 2378182011u,
3550108203u, 2108998782u, 2907139217u, 1332214261u, 891648241u,
2578642005u, 1366249405u, 2619717552u, 574713818u, 1872350222u,
2883911152u, 1984517103u, 2452387999u, 3680102565u, 729143999u,
3828109877u, 634176716u, 4017428396u, 2044746818u, 570105749u,
3900270178u, 579273057u, 2371573676u, 2337057693u, 141475767u,
2428598393u, 231339503u, 2618261398u, 3457720245u, 1861956654u,
1938640241u, 2038507192u, 1643453033u, 2402192723u, 3391493865u,
3602341588u, 1564600188u, 4142473852u, 2286425538u, 3335048275u,
3056542298u, 827939153u, 3742963152u, 1076978789u, 1411711112u,
3847641540u, 2792235659u, 1291651070u, 4186889356u, 4111150675u,
326277337u, 2727536313u, 2521228115u, 3858177828u, 1777628964u,
1636457523u, 1327730835u, 3446030271u, 1133158582u, 2674837390u,
3258876318u, 782159572u, 4274420083u, 3678751963u, 801318243u,
1470311112u, 3354993392u, 776040423u, 840945944u, 688891617u,
4262149326u, 3180950192u, 3445687209u, 667765797u, 1822039854u,
687782533u, 3130446468u, 1679964477u, 2140412333u, 2521023888u,
3474586730u, 2738336824u, 1531194236u, 272855576u, 314578174u,
1581144125u, 2538288986u, 1693951845u, 3909226960u, 2978902193u,
832218336u, 3075520766u, 1857005512u, 2749313732u, 3217616529u,
3198048780u, 168296081u, 3310066596u, 4064434880u, 349245502u,
3279951952u, 1874146182u, 2400115994u, 2787873697u, 789599428u,
1353028316u, 2138673876u, 2629101256u, 2224129914u, 3943684346u,
4270241199u, 4159779981u, 3671560018u, 2926618313u, 4133493471u,
886437031u, 2916029412u, 2881600983u, 1733025272u, 2792441416u,
4015704600u, 2896243818u, 2059370462u, 1399747019u, 995537401u,
2091141688u, 1702053663u, 3365267716u, 3028284675u, 3322651442u,
2398992773u, 2459257550u, 3249704119u, 2616019886u, 4275558572u,
4064420660u, 4133611408u, 1932472852u, 2298095725u, 837597033u,
4139790660u, 4002343555u, 496609365u, 3443323042u, 220968740u,
115259491u, 1307168777u, 10893775u, 2491904934u, 2785586805u,
2280474953u, 1896693783u, 3870659286u, 2796532337u, 2321646396u,
4019162589u, 1855342622u, 555064786u, 2330736969u, 490959045u,
3059798279u, 2691359011u, 71617365u, 368895618u, 3439928998u,
419018537u, 612072889u, 3479288324u, 2055032196u, 2830468787u,
1103099434u, 3041119163u, 1585236715u, 3855831726u, 2842258668u,
609983082u, 728464288u, 2536667505u, 1197368241u, 3547774719u,
851356113u, 3864312376u, 837825852u, 4273019476u, 1403765610u,
93856629u, 3781022335u, 2115174301u, 2023367080u, 4204671851u,
1735035239u, 1350209486u, 769793322u, 2369278308u, 4161501167u,
2513836932u, 1750009075u, 1668300176u, 3627045746u, 2923342051u,
2642801157u, 2226004008u, 1617532275u, 1001520657u, 3767466920u,
1885880162u, 3370915495u, 2599368591u, 1996963441u, 2277814872u,
3496004282u, 3274173931u, 3858788183u, 3552951969u, 1843565531u,
115543966u, 1435933937u, 452057997u, 2562579798u, 3334697064u,
3874021024u, 92244728u, 3015352427u, 3170041258u, 1621157335u,
953309163u, 3156611667u, 2110349192u, 4097840272u, 1196730082u,
2331364547u, 3304400427u, 2319736876u, 3001421795u, 1336205705u,
4237191249u, 305950166u, 1712705041u, 781600154u, 3624113458u,
399384395u, 2120599518u, 1990671162u, 3380471556u, 40082822u,
2409046702u, 3930006359u, 4012814795u, 2760554721u, 3939403736u,
6094787u, 3297788831u, 130503754u, 1026191227u, 895372775u,
3125416230u, 1954064714u, 1284624943u, 546603443u, 3626978360u,
37141541u, 83539007u, 3122783124u, 606885410u, 1520918647u,
2239843287u, 3351989811u, 3057238962u, 1875425985u, 1530721995u,
1874988534u, 161234343u, 211369000u, 1095654062u, 213167395u,
250191778u, 391272265u, 2423828544u, 2551369610u, 3042101804u,
1035448140u, 609081370u, 3613652780u, 1185846656u, 3681700798u,
2614952462u, 4138682884u, 1223079049u, 2099808600u, 2225489336u,
946224690u, 660451857u, 971558712u, 3554881734u, 2305486057u,
2318507706u, 3273236262u, 2822055016u, 1492789566u, 1119554775u,
1980975322u, 3551807758u, 2745874641u, 3516761755u, 3939928313u,
934855953u, 693948913u, 3327192365u, 3073630675u, 101876780u,
2481369570u, 1459509195u, 1861004954u, 1141309060u, 3797793840u,
1224681030u, 1688144430u, 2547349531u, 768692429u, 1521051682u,
2720147032u, 930600186u, 2680061978u, 2879962111u, 1408498461u,
268182619u, 3448709763u, 1592216145u, 4292724704u, 1599508620u,
4213269118u, 4200181833u, 545619507u, 3236090571u, 997463821u,
3184203691u, 101500669u, 4217240112u, 2608903190u, 3784923509u,
475922416u, 1479115092u, 1750025272u, 1715568033u, 3797080982u,
1579103843u, 2354212356u, 151342425u, 1584856153u, 2496419603u,
894839189u, 1937607745u, 1893836937u, 3229688482u, 4106831221u,
289431749u, 532687253u, 3202403809u, 2021912759u, 1229083658u,
3680341718u, 1058577411u, 186360648u, 2192860281u, 2970507375u,
2648231048u, 4204710567u, 352803166u, 1216626353u, 3225302463u,
574582876u, 3263983952u, 2943253852u, 1230198514u, 3906077570u,
824346422u, 2623662301u, 3956313178u, 3865396696u, 757224614u,
830791623u, 3022714332u, 3240228920u, 1179843786u, 1487178451u,
2948056279u, 1797982458u, 4255319781u, 668811578u, 3585348844u,
3517580725u, 2599889368u, 2684026125u, 349060894u, 3172092854u,
3347081959u, 3457931495u, 3830541864u, 288719121u, 1581629673u,
4083613336u, 368413676u, 2137076974u, 3970376737u, 3243326972u,
2737649035u, 3188605479u, 3616098576u, 3569674338u, 1397648422u,
672170313u, 1282546981u, 1964125989u, 2005736712u, 2654721419u,
1122965097u, 4003697003u, 4268477949u, 3586676653u, 2818808298u,
3845814717u, 4128499149u, 2501897997u, 3860552691u, 2502878480u,
1499525956u, 3671878952u, 587611744u, 149747060u, 195690614u,
3802850345u, 2325782175u, 1751190503u, 583241465u, 156259644u,
2004610888u, 3204681020u, 2689211891u, 664984504u, 3604535295u,
618081556u, 3929972522u, 2602574315u, 1710016283u, 1092986901u,
3041253464u, 1392231705u, 3940751328u, 1725678863u, 534546529u,
1745360123u, 3943952830u, 1658678333u, 821965910u, 2619078892u,
1399242525u, 716790203u, 2665205988u, 807849282u, 3088407631u,
406427894u, 3934651902u, 1388074483u, 1077200174u, 3305393652u,
1386026765u, 1005529155u, 1606082383u, 3179845493u, 956152124u,
2975632437u, 1808432395u, 3539388960u, 2114561910u, 3556136492u,
2063776030u, 1260005679u, 2450967374u, 1328730778u, 3569386647u,
2246395892u, 958560479u, 1397148536u, 2977661875u, 3572736354u,
3484318978u, 3480189603u, 3538510658u, 2392289338u, 553042652u,
1129421929u, 657031522u, 2923009585u, 1833485762u, 1003532627u,
1380103857u, 1960332028u, 1889542857u, 1651702217u, 3630760968u,
2313275557u, 1716182045u, 4259335064u, 1188243733u, 3243646919u,
1943239771u, 4211021527u, 1276150468u, 1008383770u, 2592475956u,
2270143981u, 4206016496u, 220916187u, 1061014409u, 3250755412u,
405813977u, 2585483415u, 2282646335u, 3681511559u, 2796349024u,
4244618003u, 1140587439u, 3992105438u, 430549136u, 1758853233u,
4072612623u, 1466574u, 1215975886u, 2323054716u, 2601488966u,
892196231u, 516847440u, 941815809u, 4267193699u, 1399327243u,
1513367522u, 412099598u, 3006457623u, 3210632622u, 2929320506u,
3214821475u, 2787332623u, 2333453280u, 2286517530u, 1452267238u,
1233666122u, 3574845880u, 2697674u, 2373279437u, 1248356043u,
4112616366u, 2665803324u, 3834689917u, 2583683474u, 1531171380u,
2210054590u, 2346778254u, 2801479353u, 1488986759u, 4262756833u,
2674917603u, 2380821100u, 3421476965u, 1420809174u, 3203508306u,
2821835379u, 539174012u, 3238947696u, 3532155363u, 463909612u,
108020580u, 686311412u, 1779958481u, 3501283419u, 3141371161u,
2549322549u, 3355975804u, 151660038u, 1577481000u, 237654147u,
3199183092u, 1395812589u, 3832258389u, 3321416658u, 1041973628u,
1338155692u, 556614774u, 2802833609u, 966659181u, 3371464856u,
1503298306u, 4194717924u, 1233019036u, 2234408174u, 3983530663u,
304386537u, 220390885u, 3672604251u, 2545484329u, 1481477612u,
699645452u, 1206554024u, 3600925349u, 2351947411u, 719668723u,
1522666126u, 2156935220u, 2578961309u, 4292087425u, 851501823u,
1526462106u, 1538145242u, 202197234u, 923797659u, 917665233u,
1280176282u, 1708706026u, 1488528898u, 1433093941u, 328725394u,
986135364u, 789495949u, 4020605538u, 1543114480u, 2934273484u,
2050902067u, 4132247293u, 3175607941u, 1881080451u, 3551141606u,
4038715194u, 1337862187u, 25058210u, 3386659863u, 2621248714u,
4116323910u, 3440594177u, 239971622u, 1000648070u, 346758228u,
4004922487u, 486542737u, 3278188663u, 2457877853u, 3549573731u,
2257175936u, 2463007358u, 4094271342u, 3404112349u, 913435793u,
1413221177u, 3109328087u, 959761872u, 3135335463u, 1341689139u,
361014125u, 2510509240u, 1077003967u, 3564454102u, 1902586361u,
1247526901u, 2940736338u, 1728957925u, 3861749142u, 3702507913u,
6506179u, 2640286243u, 3185951192u, 4257119115u, 4170283151u,
874880000u, 960224933u, 3552835960u, 4133901877u, 2902803543u,
4029723476u, 1069229844u, 1097566470u, 2043483688u, 3492749477u,
1714015065u, 997956638u, 2574567667u, 3733818679u, 3438219097u,
3601196803u, 451266934u, 3291888764u, 3528067348u, 4204683957u,
3612438284u, 1162023843u, 1522592715u, 2943081924u, 1847134284u,
663478404u, 2457748727u, 3297874754u, 3010019326u, 387951882u,
3188883299u, 3829156090u, 3255087638u, 3365242650u, 1671295327u,
2343810092u, 1843840147u, 693346359u, 4107469050u, 492532155u,
2460893290u, 532996711u, 3649528417u, 2356748197u, 1186894091u,
2134551200u, 2672859557u, 3034429947u, 2526994202u, 2366878138u,
4138065547u, 2062701434u, 368949266u, 2351844505u, 2149626396u,
419191055u, 2240210598u, 1407993071u, 387260016u, 4097232872u,
3885512949u, 2155071777u, 3798421539u, 4274030102u, 1885446249u,
2981237059u, 3357473073u, 137290838u, 637652444u, 287471442u,
2662089150u, 2298526392u, 1119370200u, 478113897u, 1914078872u,
723733797u, 3624950286u, 3707741573u, 842693726u, 1780406925u,
1305032792u, 1968510495u, 2075734367u, 3590755543u, 1450891707u,
83344440u, 3429470524u, 3773462330u, 4241226826u, 3307743815u,
683104062u, 1884612196u, 1017390927u, 1347475469u, 3016083386u,
1524948889u, 1612638509u, 2128788363u, 4182030709u, 3347916223u,
4176020545u, 2603962123u, 2764662049u, 3055322347u, 3694096552u,
458347065u, 1726076036u, 2583701940u, 2714122091u, 4113553423u,
4231559144u, 1222406883u, 2402937181u, 1283962072u, 4009746733u,
3536942113u, 3093850505u, 2103058130u, 2078929575u, 4256494377u,
2744617663u, 1636520641u, 3812371327u, 1841438767u, 853567863u,
293694107u, 1698085228u, 77712651u, 4261360454u, 3773698328u,
1728087008u, 3789317723u, 2829767026u, 4156170415u, 3871260724u,
905192820u, 4275132168u, 2305686413u, 2805314924u, 2583657764u,
465730905u, 4205645334u, 155108597u, 696964616u, 2654681637u,
3442801575u, 2435866492u, 3014889847u, 4131606733u, 3379831463u,
3204498570u, 4096439241u, 2845484976u, 2127645355u, 2247613591u,
2703254578u, 1116237411u, 4213484460u, 4131731766u, 3202543611u,
2320158681u, 2454537032u, 130009356u, 2406857045u, 2990647864u,
1084825589u, 2232163876u, 3955791431u, 253534309u, 274296365u,
3822676536u, 264436337u, 1418207815u, 3310289547u, 986559116u,
3853187406u, 489405686u, 3596088854u, 1335402887u, 787430740u,
981109357u, 1197534756u, 2800306525u, 1916853569u, 284155565u,
2610413878u, 1182968776u, 106675122u, 1210408692u, 4251329608u,
3779855792u, 3736145590u, 1908384358u, 970818599u, 3246626431u,
3742565154u, 2591138191u, 3747660557u, 3364101596u, 2311379507u,
489328382u, 2031550691u, 4202899902u, 1584951024u, 3644694974u,
3312357739u, 217525025u, 3644269603u, 2002321607u, 3954860816u,
1398670148u, 2917504255u, 2706710400u, 220857550u, 989127374u,
2244289149u, 2490586984u, 2642071963u, 2590536648u, 4115793618u,
2576461102u, 1363138228u, 1925983082u, 1189640964u, 152142597u,
1764120035u, 2206817911u, 3313705895u, 1751187711u, 4081059871u,
464054176u, 2379176226u, 1975150787u, 340197618u, 1936526659u,
3404850845u, 2367129719u, 2924126064u, 3459185214u, 2363113359u,
3010128150u, 1881108460u, 3746222960u, 2651248795u, 224163596u,
508682106u, 943524043u, 2151289167u, 1974147403u, 1247690780u,
4116870452u, 2079216305u, 3393218954u, 3567954541u, 1940786677u,
1574417861u, 1432063148u, 2739922267u, 253812427u, 2591454480u,
3182164041u, 1793274063u, 2176665906u, 2497827999u, 858673115u,
3096781115u, 1834782321u, 3629534222u, 724519201u, 4056372476u,
3228503710u, 577268130u, 1582054841u, 301959526u, 4045076624u,
2865028790u, 73755492u, 1825462177u, 3560768027u, 1981121873u,
2691187765u, 188128347u, 2313898662u, 997804738u, 2793909018u,
3725300670u, 3120850068u, 3968046994u, 405825309u, 1595162944u,
3769151350u, 2640525979u, 61684932u, 1415789469u, 1264020135u,
3950226460u, 772728513u, 971672615u, 3978403595u, 588202301u,
292832750u, 1395744634u, 2495776388u, 3271786154u, 2736543666u,
2060545333u, 2797180204u, 141652380u, 3713523292u, 433967869u,
240314286u, 1601436731u, 3508366246u, 2271914741u, 2271704699u,
3087042934u, 2982212958u, 2930329007u, 912272095u, 2555606130u,
2333369619u, 230283885u, 3017301575u, 3446194064u, 4107855164u,
1100310667u, 1909294076u, 434149393u, 366780871u, 3555380811u,
246274064u, 1400899690u, 2703469266u, 570232921u, 3419563051u,
1660365526u, 2968644183u, 1329342932u, 1483085977u, 3122684163u,
4066546606u, 3861009980u, 2234200415u, 2739937896u, 4096595764u,
768251542u, 316090862u, 124090419u, 889195424u, 2979770918u,
3328719122u, 1415047028u, 3926406796u, 1428546568u, 3361029438u,
4211665632u, 1269309700u, 1527101308u, 652172402u, 3674640971u,
3641747964u, 3660382256u, 3370924808u, 115498466u, 1163212438u,
3820703862u, 978439546u, 921271064u, 1378784223u, 3577406236u,
3562940814u, 2671627138u, 3531245640u, 693194205u, 2451064185u,
2578017243u, 2455989585u, 2481212951u, 1228439114u, 3012282683u,
3002755761u, 3856715509u, 3419901832u, 211338799u, 1896610556u,
3548852272u, 1916481449u, 2574085613u, 2000004829u, 2000481307u,
1198464170u, 3173831883u, 2900714882u, 3372201736u, 3881209586u,
2588621608u, 3902089006u, 4177227927u, 3209186455u, 900943443u,
1118888408u, 2571008108u, 2961971973u, 161380270u, 566208408u,
1721643267u, 530432053u, 515707945u, 819921504u, 992966575u,
625914594u, 1250102554u, 2512743175u, 3531636148u, 315086074u,
1566977546u, 3531864233u, 930010731u, 3104844610u, 2733910504u,
3976529992u, 1345375192u, 2115866656u, 1763704995u, 2812700617u,
3160963817u, 3823051215u, 3657060267u, 2312949751u, 322667309u,
1212061965u, 72459214u, 4191705628u, 2896389243u, 156446385u,
4016046429u, 1401209769u, 1582631648u, 4179061694u, 3916756276u,
1567803172u, 2638882606u, 1327787509u, 1976869919u, 519314732u,
2342793709u, 3933183772u, 758814231u, 581874432u, 4123546062u,
1426435462u, 3733828360u, 3854646810u, 359046114u, 2145975155u,
3266914361u, 2642642879u, 4016733328u, 2504537053u, 424148936u,
2998977786u, 2572729225u, 125981442u, 1724033108u, 2267238861u,
4289876504u, 137751831u, 2478124794u, 3552549223u, 1304521882u,
1460229647u, 796181928u, 3636595890u, 745804678u, 1056860767u,
974631484u, 2497485889u, 3198571182u, 4027291544u, 1320904721u,
205244833u, 3484057229u, 231832262u, 3335419183u, 88553761u,
2986770319u, 2926927914u, 3677485767u, 2571089926u, 3267182695u,
489755279u, 671960175u, 3419847717u, 3886885702u, 2653648091u,
211741983u, 301564791u, 2853589419u, 297550915u, 1272390376u,
584147277u, 2971264785u, 3388262418u, 2419292619u, 396848377u,
400462790u, 1021638674u, 3544744847u, 1046459817u, 1131154364u,
450207978u, 974999278u, 3686597032u, 1290348400u, 2998745183u,
1317492534u, 3151398478u, 276900107u, 2794007767u, 1755609205u,
2217365206u, 1595486548u, 1401826344u, 4027763770u, 2842307113u,
2474293622u, 504939907u, 1018556149u, 634870958u, 2105780331u,
84888587u, 1118262728u, 4141601466u, 730125637u, 4167719882u,
949159370u, 531976824u, 3685828907u, 2007510762u, 3599556892u,
2820479277u, 492851583u, 1246337526u, 1940706935u, 3240710205u,
2042152385u, 2397098757u, 3475438049u, 1837355219u, 986711571u,
1147589739u, 1298991474u, 3237271788u, 1639728592u, 3858496958u,
993191411u, 3128643299u, 914694463u, 1747322140u, 1525827943u,
4030035866u, 967493702u, 1097052573u, 2880094426u, 2289918684u,
3468759489u, 4100640951u, 2142548389u, 1149966939u, 79830251u,
1074105259u, 2505154460u, 3984323976u, 3599632907u, 294558951u,
17254381u, 1285914862u, 2776786651u, 2540831914u, 3765303330u,
873163177u, 1692514385u, 2731097567u, 979124410u, 3428974151u,
467084174u, 2154789608u, 1647267729u, 2795216860u, 1039042602u,
3418600624u, 3228166887u, 1002332673u, 3974411194u, 2580583607u,
904733688u, 483022231u, 3917358149u, 2215196638u, 654516857u,
3598498336u, 4099774739u, 3954763417u, 1118670512u, 2139872644u,
3082249575u, 1192330715u, 420290154u, 2802551881u, 2603975185u,
3939768357u, 1474219045u, 2189743776u, 410209795u, 4184120550u,
2546630001u, 847306611u, 1677378142u, 477535865u, 3916441108u,
1277126944u, 2864665523u, 1702604657u, 773876494u, 1807131889u,
3702786021u, 1337776463u, 3572687626u, 2980033697u, 4255621298u,
394586502u, 3130582261u, 1726957441u, 3873244108u, 1267791874u,
3719934631u, 1316393651u, 1375414654u, 453381607u, 568651816u,
2550470125u, 3901112416u, 1214305419u, 3751458762u, 666671791u,
1284096272u, 2828953u, 3723372638u, 1218033032u, 2368557457u,
2365714712u, 848058200u, 3740496416u, 1949250944u, 181477083u,
3214116591u, 3885751315u, 3539347299u, 562529426u, 1283372361u,
3580838576u, 794172702u, 3437985472u, 2640564784u, 3942264960u,
2252660330u, 589714749u, 355166505u, 2167808774u, 3911578180u,
1739283430u, 582727528u, 745486761u, 709694981u, 2470394812u,
2784288873u, 2603686201u, 2503004545u, 921037450u, 248723197u,
2233092030u, 4241673838u, 4248520683u, 4035718652u, 2104169607u,
51010521u, 2984457723u, 2807166639u, 1767043292u, 3958216011u,
149364986u, 186549740u, 1257701956u, 553198631u, 3442166049u,
725301812u, 1488214709u, 3955036524u, 357839254u, 3523734991u,
2195185139u, 3754986293u, 1575537478u, 2389854207u, 3176040305u,
208578128u, 2253741825u, 2553968314u, 3455390865u, 1293117228u,
3508606804u, 1846102791u, 813773800u, 3404247876u, 531259344u,
3216075103u, 3526153030u, 456016676u, 2739749423u, 1093250703u,
69234044u, 792168263u, 3848095809u, 2202850158u, 2213519030u,
1007229102u, 2338703931u, 1765185701u, 2604649447u, 1522222943u,
3266048702u, 1921662655u, 3673686829u, 3415463996u, 1644407479u,
1107992188u, 363565489u, 3321072547u, 3151961821u, 3445798495u,
1425883319u, 4059119275u, 3606696770u, 2834384682u, 1596539449u,
3636233163u, 3557157499u, 3602705437u, 758141738u, 1412595934u,
556283557u, 2057068993u, 3779071200u, 1445808087u, 189318428u,
2040772438u, 2949440024u, 2802944456u, 3151530650u, 722184665u,
1877641340u, 1164797906u, 1631395717u, 1861106618u, 4207596651u,
3412368205u, 1713663690u, 2877098665u, 1890588414u, 2270170721u,
673484753u, 1712353108u, 1400306575u, 3682940464u, 1348885721u,
2224151036u, 3841851095u, 3451954494u, 1060960786u, 437589053u,
1334356198u, 2804921297u, 1756078580u, 3810757529u, 3040883626u,
2579239042u, 616918759u, 2853014080u, 3742299785u, 565628891u,
357151864u, 2285145814u, 1983148904u, 2565821297u, 130519865u,
3057750354u, 3234971651u, 981709724u, 3006660375u, 2608421078u,
921323098u, 1324171014u, 2920168401u, 633540935u, 2393553830u,
1860716086u, 3653638057u, 2418826530u, 2399020543u, 1069386495u,
3873088393u, 1540601308u, 1801814819u, 379787626u, 1538149557u,
3623779521u, 2100185394u, 2590016350u, 1099349030u, 83020443u,
3990751639u, 908730558u, 2004705277u, 566260495u, 1090955400u,
2559442672u, 1852069143u, 1139673340u, 3017343395u, 4132204778u,
1727993619u, 3383152526u, 780997206u, 935658414u, 3677570543u,
1746642030u, 2509125172u, 223854197u, 1604508661u, 1891081055u,
952170820u, 1620251131u, 940572554u, 3971328146u, 2242971249u,
4255333609u, 1861536355u, 3727697922u, 3183876408u, 286776617u,
302578855u, 2532118292u, 3639269404u, 2970666689u, 2920063380u,
1694233198u, 586913821u, 3422958506u, 3686809331u, 1981091823u,
858281024u, 814684694u, 2608505099u, 1816299992u, 2332360436u,
3899354093u, 697179254u, 1558653496u, 24279715u, 4124089548u,
3313503461u, 2741421184u, 3284737548u, 873011879u, 1808479090u,
3455057368u, 244010779u, 303799249u, 2515764191u, 3793164333u,
747991075u, 975903908u, 3129358949u, 1966190241u, 2294762589u,
3495328008u, 1086902846u, 3177987384u, 3938728764u, 867407692u,
3256420714u, 689048646u, 3809767992u, 2344280344u, 295485905u,
928125706u, 788247606u, 1836899313u, 3165702953u, 298675190u,
2992367488u, 2519000176u, 3337159108u, 2044324637u, 2155658777u,
2552272156u, 1827494965u, 2257947328u, 2625243482u, 4130751842u,
};
int main(
int argc,
char * argv[])
{
unsigned long i;
uint32_t (*funcptr)(void);
uint32_t random_value;
uint64_t longlong_value;
double double_value;
volatile uint32_t dummy_long; /* Avoids optimization; see below */
volatile uint64_t dummy_longlong;
volatile double dummy_double;
uint32_t goodseedresult;
FILE* savefile;
uint32_t seedresult;
static mt_state state;
struct rusage then;
struct timeval timeofday;
static unsigned long
timing_loops = TIMING_LOOPS;
setbuf(stdout, (char *) NULL);
/*
* If the user has given a number of timing loops, reset the loop count.
*/
if (argc > 1)
timing_loops = atol(argv[1]) * TIMING_LOOP_BASE;
/*
* Compare the generated values against corresponding numbers from
* Matsumoto and Nishimura's own generator, to make sure we're
* doing the calculation correctly.
*/
(void) printf ("Validity test...");
mt_seed32new(5489);
savefile = fopen("mtsave", "w");
mt_savestate(savefile);
fclose(savefile);
mt_seed32new(1);
savefile = fopen("mtsave", "r");
mt_loadstate(savefile);
fclose(savefile);
unlink("mtsave");
for (i = 0; i < sizeof correct_values / sizeof correct_values[0]; i++)
{
random_value = mt_lrand();
if (random_value != correct_values[i])
{
(void) fprintf (stderr,
"Failure at value %ld: expected %" PRIu32 ", got %" PRIu32 "\n",
i, correct_values[i], random_value);
return 1;
}
}
(void) printf ("passed.\n");
/*
* Make sure we can take a pointer to the inlined functions.
*/
funcptr = &mt_lrand;
random_value = (*funcptr)();
/*
* Timing tests. Each test sums up the random numbers, not
* because we care about the sum, but because the PRNG functions
* are inlined. If we don't sum up the numbers (and then assign
* them to a volatile), the compiler will optimize the RNG code
* right out of existence.
*/
(void) printf ("%ld default longs took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
random_value += mt_lrand();
report_timing(timing_loops, &then);
(void) printf ("%ld state-based longs took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
random_value += mts_lrand(&state);
report_timing(timing_loops, &then);
dummy_long = random_value;
(void)dummy_long; /* Silence compiler warning */
longlong_value = 0;
/*
* In the case of long longs, there aren't enough registers to
* store them on a 32-bit x86, so they wind up on the stack. We'd
* get faster timing if we just stored directly into
* dummy_longlong. However, this would produce worse results on
* more sensibly designed machines. Rather than tune our code to
* a broken architecture, we'll stick with the generalized
* version.
*/
(void) printf ("%ld default long longs took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
longlong_value += mt_llrand();
report_timing(timing_loops, &then);
(void) printf ("%ld state-based long longs took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
longlong_value += mts_llrand(&state);
report_timing(timing_loops, &then);
dummy_longlong = longlong_value;
(void)dummy_longlong; /* Silence compiler warning */
double_value = 0.0;
/*
* Similarly, the x86 winds up storing the double-precision sum on
* the stack. Again, we'll tolerate that inefficiency.
*/
(void) printf ("%ld default fast doubles took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
double_value += mt_drand();
report_timing(timing_loops, &then);
(void) printf ("%ld state-based fast doubles took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
double_value += mts_drand(&state);
report_timing(timing_loops, &then);
(void) printf ("%ld default long doubles took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
double_value += mt_ldrand();
report_timing(timing_loops, &then);
(void) printf ("%ld state-based long doubles took ", timing_loops);
getrusage(RUSAGE_SELF, &then);
for (i = 0; i < timing_loops; i++)
double_value += mts_ldrand(&state);
report_timing(timing_loops, &then);
dummy_double = double_value;
(void)dummy_double; /* Silence compiler warning */
/*
* Test seed timing.
*/
(void) printf ("Initializing from mt_seed took ");
gettimeofday(&timeofday, NULL);
seedresult = mt_seed();
report_clock_timing(&timeofday);
if (seedresult == 0)
(void) printf ("OOPS! Got zero seed from mt_seed!\n");
(void) printf ("Initializing from mt_goodseed took ");
gettimeofday(&timeofday, NULL);
goodseedresult = mt_goodseed();
report_clock_timing(&timeofday);
if (goodseedresult == 0)
(void) printf ("OOPS! Got zero seed from mt_goodseed!\n");
if (seedresult == goodseedresult)
(void) printf ("OOPS! mt_seed and mt_goodseed both returned 0x%x!\n",
seedresult);
(void) printf ("Initializing from mt_bestseed took ");
gettimeofday(&timeofday, NULL);
mt_bestseed();
report_clock_timing(&timeofday);
return 0;
}
static void report_timing(
unsigned long loops, /* Number of loops that were done */
struct rusage * then) /* Time test started */
{
long diff; /* Difference in times */
long microdiff; /* Microsecond part of difference */
struct rusage now; /* Time test ended */
double secs; /* Actual seconds needed */
getrusage(RUSAGE_SELF, &now);
diff = now.ru_utime.tv_sec - then->ru_utime.tv_sec;
microdiff = now.ru_utime.tv_usec - then->ru_utime.tv_usec;
if (microdiff < 0)
{
diff--;
microdiff += 1000000;
}
secs = diff + (microdiff / 1000000.0);
(void) printf ("%3ld.%6.6ld seconds (%ld/sec).\n", diff, microdiff,
(long)(loops / secs));
}
static void report_clock_timing(
struct timeval * then) /* Time test started */
{
long diff; /* Difference in times */
long microdiff; /* Microsecond part of difference */
struct timeval now; /* Time test ended */
double secs; /* Actual seconds needed */
gettimeofday(&now, NULL);
diff = now.tv_sec - then->tv_sec;
microdiff = now.tv_usec - then->tv_usec;
if (microdiff < 0)
{
diff--;
microdiff += 1000000;
}
secs = diff + (microdiff / 1000000.0);
(void) printf ("%3ld.%6.6ld seconds.\n", diff, microdiff);
}