#ifndef lint
#ifdef __GNUC__
#define ATTRIBUTE(attrs) __attribute__(attrs)
#else
#define ATTRIBUTE(attrs)
#endif
static char Rcs_Id[] ATTRIBUTE((used)) =
"$Id: mtcctest.cc,v 1.7 2012-12-30 16:24:49-08 geoff Exp $";
#endif
/*
* Test the C++ version of the Mersenne Twister PRNG
*
* $Log: mtcctest.cc,v $
* Revision 1.7 2012-12-30 16:24:49-08 geoff
* Use gcc attributes to suppress warnings on Rcs_Id.
*
* Revision 1.6 2010-06-24 01:45:46-07 geoff
* Move volatile declarations to the top of the function to ensure they
* are effective.
*
* Revision 1.5 2007-10-26 00:21:06-07 geoff
* Don't throw away random values in the timing tests, since then the
* compiler would optimize the entire loop away.
*
* Revision 1.4 2003/09/11 05:50:53 geoff
* Use the standard namespace. Get rid of a troublesome setbuf call that
* I'm too lazy to figure out how to get to work.
*
* Revision 1.3 2001/06/19 00:41:16 geoff
* Put a newline after the saved data, now that the type doesn't.
*
* Revision 1.2 2001/06/18 05:40:11 geoff
* Do 300 million timing loops by default.
*
* Revision 1.1 2001/06/14 10:52:29 geoff
* Initial revision
*
*/
#include "mtwist.h"
#include <fstream>
#include <iomanip>
#include <iostream>
#include <unistd.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <sys/time.h>
using namespace std;
int main (int argc, char * argv[]);
static void report_timing(long loops, struct rusage * 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 unsigned long correct_values[] =
{
3510405877u, 4290933890u, 2191955339u, 564929546u, 152112058u,
4262624192u, 2687398418u, 268830360u, 1763988213u, 578848526u,
4212814465u, 3596577449u, 4146913070u, 950422373u, 1908844540u,
1452005258u, 3029421110u, 142578355u, 1583761762u, 1816660702u,
2530498888u, 1339965000u, 3874409922u, 3044234909u, 1962617717u,
2324289180u, 310281170u, 981016607u, 908202274u, 3371937721u,
2244849493u, 675678546u, 3196822098u, 1040470160u, 3059612017u,
3055400130u, 2826830282u, 2884538137u, 3090587696u, 2262235068u,
3506294894u, 2080537739u, 1636797501u, 4292933080u, 2037904983u,
2465694618u, 1249751105u, 30084166u, 112252926u, 1333718913u,
880414402u, 334691897u, 3337628481u, 17084333u, 1070118630u,
2111543209u, 1129029736u, 2769716594u, 198749844u, 2123740404u,
3372116884u, 667945179u, 1235233343u, 1413475797u, 2355129622u,
3131889314u, 1361507145u, 3419810344u, 3753862504u, 2643520359u,
854777807u, 2823672895u, 1563137348u, 2778071293u, 3360232580u,
1294979669u, 2667002587u, 4095439979u, 806669383u, 3717814038u,
1071953403u, 3630859637u, 771361748u, 1131385020u, 3697612515u,
4264844916u, 1364828348u, 2863894246u, 1109863328u, 3066937191u,
2778683115u, 3989613953u, 859474495u, 167522376u, 1094225558u,
1963711766u, 1257324636u, 1729949323u, 125753755u, 1068698284u,
1761594045u, 2106609220u, 1033190229u, 946183933u, 1100436279u,
489306665u, 2385045156u, 658699819u, 3308017340u, 2385997510u,
105622857u, 1976233741u, 1535497010u, 314176889u, 1247500738u,
2138106664u, 2757078771u, 2433460811u, 3970906471u, 1944201130u,
2366336502u, 2541539915u, 4284982935u, 224898482u, 1457988276u,
2188154237u, 3655119144u, 979144237u, 1279857832u, 2711710163u,
4093937260u, 2299893420u, 2121869254u, 2505459837u, 1847263294u,
2974457633u, 3439803738u, 1672773492u, 225684598u, 2496857387u,
611619631u, 3993022877u, 3508398016u, 1663733971u, 758566080u,
1653863133u, 1701066037u, 3782883361u, 3343813716u, 2602577666u,
629577870u, 3724093470u, 361301181u, 2674434977u, 1443899064u,
4104796692u, 140754167u, 4230942998u, 447458027u, 743917836u,
2818315151u, 1332110941u, 266033703u, 308176090u, 130356650u,
3074197472u, 3093392044u, 1602712035u, 1856287253u, 3375970245u,
3114872063u, 370413632u, 1435286098u, 645351481u, 908917276u,
2440368438u, 1599412846u, 2500100729u, 790131292u, 3684521490u,
4052663936u, 1566488352u, 295035953u, 4163443199u, 2997925650u,
678068969u, 3667661122u, 1273385972u, 3555794914u, 762012623u,
1091375739u, 1765680277u, 4238179361u, 3406590822u, 3797246256u,
388618876u, 2160693563u, 349961032u, 1392360403u, 3579025090u,
604490212u, 3577823930u, 2321462651u, 3790422055u, 3185735941u,
2229660586u, 1128575466u, 884862908u, 3330757128u, 3194168238u,
681073659u, 800341641u, 2006864675u, 2619636221u, 1577889182u,
3575155952u, 2260116784u, 3689141878u, 1657848984u, 2642380231u,
2878484564u, 3099953080u, 468844464u, 4134363631u, 4110639840u,
1904558184u, 1937194892u, 3137602491u, 3643695698u, 820242909u,
3068372731u, 3388748923u, 4235603065u, 2615115373u, 1555770904u,
1520951990u, 1047053830u, 1663094463u, 3948465044u, 1077597088u,
2996944317u, 3230974609u, 2019388652u, 865275198u, 2046271241u,
3163620630u, 269072378u, 2253440754u, 277763586u, 1114595358u,
2679817222u, 988885471u, 922982460u, 477046426u, 1161679484u,
2950091998u, 2088879880u, 3516906501u, 1403601752u, 1184069822u,
3531029460u, 3041313352u, 3359174170u, 2117925252u, 1529768389u,
1253051929u, 1829668776u, 2678766355u, 2138924913u, 3147299808u,
447212163u, 1069119222u, 3791704659u, 804904386u, 3580345412u,
1700215583u, 904016717u, 74539975u, 1288558083u, 1746888271u,
437611701u, 781576281u, 1166365552u, 2566333668u, 4292856916u,
4076802480u, 3968908047u, 3057346051u, 2074623641u, 3653637364u,
586217310u, 3211306229u, 2604443978u, 3303224219u, 50953535u,
2118693299u, 460196852u, 3355264342u, 500727351u, 1681849672u,
113995187u, 1200937601u, 3092561862u, 312936130u, 3916083024u,
2561711416u, 3713941700u, 2240434908u, 637144400u, 1946468041u,
3224254139u, 2242555323u, 2524984519u, 945834669u, 2805199117u,
1879274691u, 3792160120u, 37879558u, 1205870756u, 3508020184u,
2705733735u, 3134213377u, 3170077556u, 9055729u, 2147895752u,
3788046325u, 2422273092u, 1228026268u, 1275162816u, 1385450594u,
128490357u, 678715088u, 2466464403u, 2715463741u, 420067866u,
396072989u, 1729810791u, 4146068843u, 389936193u, 1010939382u,
794725144u, 633726173u, 3567793282u, 248988111u, 1254549356u,
1989964616u, 1425389196u, 2202358947u, 2830413406u, 3798927382u,
3442966168u, 269966252u, 2807646342u, 1794971636u, 1602977220u,
1360381486u, 1805272988u, 554730358u, 4259897540u, 2168740091u,
442942697u, 3744617621u, 3567326073u, 1232342342u, 3720210842u,
303505483u, 3533762586u, 2136482547u, 2813945830u, 3051833277u,
2830164695u, 3157472512u, 3186113013u, 1063305342u, 4133844231u,
2026873438u, 94687021u, 42670911u, 2205451721u, 200274097u,
3184342380u, 1216199867u, 1941807482u, 1902652464u, 4140258655u,
1934749011u, 2626251395u, 1041046135u, 3256560316u, 2005577300u,
367040511u, 2562291571u, 4179257085u, 394550850u, 3714400922u,
3096861476u, 3729796880u, 3528309113u, 1483426196u, 821348673u,
2057501468u, 3141389956u, 631596202u, 2325651773u, 3568751628u,
2300178836u, 257777076u, 3455675689u, 2853908813u, 223950412u,
2320715588u, 250378269u, 3557833937u, 927098460u, 315421373u,
1957400381u, 725633141u, 3345409284u, 1114863797u, 1830809043u,
1922707457u, 3785762071u, 3404751487u, 2434832700u, 1359584120u,
860423718u, 2979956529u, 888063953u, 641814761u, 180527770u,
3316862637u, 4012959929u, 28566252u, 1045558574u, 4131606737u,
215968520u, 362234156u, 2248115936u, 3069089212u, 3403600809u,
1812984601u, 1768934064u, 4007586160u, 1240758160u, 13887765u,
3514615109u, 3827374039u, 3341198715u, 1982839159u, 2033151304u,
4283902822u, 3744190534u, 726223056u, 3905246635u, 1875803225u,
2030522753u, 2822074688u, 3325482280u, 1691268105u, 3033866845u,
1716543028u, 1555574049u, 2661093496u, 1979855811u, 2251933935u,
1276056752u, 3341241268u, 1892612984u, 2194846054u, 486586963u,
2492823590u, 593230942u, 775986230u, 1255789287u, 2318099602u,
3056263080u, 158332807u, 2451929550u, 3374135491u, 372847709u,
1128359579u, 373993639u, 2419119952u, 829613207u, 2948211163u,
2324165819u, 160722663u, 1444930279u, 765460462u, 3780495422u,
592264489u, 316670611u, 2342138965u, 1439591408u, 3362218290u,
2860902653u, 1116562887u, 3033679152u, 1381679779u, 1291533463u,
1962666710u, 2222373514u, 1215751045u, 3569236064u, 1611254503u,
1171727980u, 3057484484u, 3263787664u, 3065712276u, 781477153u,
1881176626u, 3769042770u, 1193467712u, 2843905090u, 3437666358u,
2160717604u, 419274206u, 2767079897u, 4007363510u, 1325555048u,
4187736634u, 4066907010u, 3299749742u, 154249616u, 1941800223u,
1157563946u, 705258893u, 860757803u, 1310317854u, 1898329708u,
3491229573u, 312822728u, 3407001878u, 1029352733u, 3463910352u,
2741163037u, 2705583812u, 2644345635u, 683012156u, 948328240u,
2656867161u, 1644147624u, 2853875853u, 822059867u, 753937406u,
1604103884u, 1756360543u, 3400647193u, 2802766030u, 2268191056u,
3784643944u, 3009927237u, 394432056u, 1840177440u, 2651765924u,
1205254585u, 3551482241u, 2857937506u, 2522509113u, 3675764066u,
1234994787u, 3459183960u, 186529857u, 1329960799u, 2322397450u,
1078548606u, 113242357u, 2421327506u, 3306100881u, 211880652u,
847202265u, 1034020264u, 2374075486u, 755993425u, 2474409905u,
1885945103u, 3588026819u, 3326201431u, 747273957u, 3172561912u,
4064603659u, 2036147813u, 3539583488u, 2861164857u, 3303878586u,
2385840167u, 734771685u, 804646316u, 1158163327u, 2080435695u,
2455811362u, 2060318701u, 1223319334u, 2573853731u, 3341336861u,
3207344772u, 1654544724u, 1227774824u, 1779567885u, 4241425455u,
3942578957u, 2787959909u, 90390016u, 1235487669u, 2405269696u,
4096898260u, 2121644059u, 2432007152u, 2649006803u, 355642145u,
3998121079u, 3524581383u, 919279000u, 789586853u, 2465492036u,
220701650u, 2947224279u, 1329892616u, 3729919501u, 1219039514u,
3006882189u, 281458735u, 3800499491u, 730882493u, 2222118351u,
4107301035u, 2687550208u, 3260886108u, 3701859392u, 3862191362u,
1412535194u, 1694757183u, 772470279u, 689128388u, 2265554314u,
3499902942u, 2845535450u, 2570802968u, 1947307958u, 4027367903u,
1910806179u, 3858889779u, 4021735452u, 4078787932u, 3413032217u,
2980053565u, 2148809521u, 1497338125u, 2040525958u, 3112062074u,
2201881275u, 3672285015u, 3003099464u, 3809697025u, 3709177038u,
3264926503u, 1707537043u, 1104985157u, 3691862420u, 1898692192u,
2323051094u, 736562662u, 2300313916u, 3100486674u, 302436891u,
1288467611u, 1981059467u, 3645778636u, 1609399619u, 3418162375u,
3667843152u, 536318325u, 3040655354u, 2544467931u, 424476355u,
1601741596u, 246832728u, 2677287644u, 2835422307u, 1127786001u,
850991343u, 2067806155u, 3766212150u, 1001927094u, 3801068881u,
3242308737u, 1560596676u, 1681618985u, 2562998394u, 3484825522u,
2655391996u, 1746361319u, 3550836123u, 4038742826u, 735255465u,
3954076606u, 4101370050u, 3167012089u, 1966689481u, 1576556523u,
207036082u, 2337346669u, 3404885158u, 3372194402u, 2313772874u,
1511011541u, 3934253759u, 152017013u, 2305096656u, 1003233114u,
3788182044u, 2738083629u, 2667318735u, 4075851512u, 3919952624u,
3934687504u, 955697805u, 3721361893u, 1892740917u, 1925356403u,
3530645689u, 57355987u, 500963211u, 3812263275u, 3120702996u,
3348394440u, 2648242605u, 2950965560u, 2906248872u, 4195607563u,
1976120064u, 569029796u, 3204894397u, 836657553u, 4253104557u,
4029524248u, 1167446730u, 3164256694u, 1225943621u, 978942573u,
3887954057u, 4029693733u, 3371611138u, 2648127182u, 341670719u,
780349063u, 1249088385u, 2825987206u, 1409751402u, 3493141543u,
2454446995u, 3001899542u, 894695004u, 4113594037u, 2748119359u,
3811278462u, 337072564u, 3551268535u, 4210316453u, 2857304716u,
1656016234u, 3055850193u, 4074141119u, 2702683976u, 3903520288u,
2708109896u, 1303194166u, 676764765u, 1073839u, 3417024471u,
530027902u, 664548902u, 3934189521u, 1118172394u, 1598501076u,
1353136139u, 3556356767u, 3851436279u, 787984702u, 3614996657u,
2653843342u, 350845053u, 2540767452u, 341795141u, 4131579558u,
2852231303u, 347703279u, 304754275u, 3637218358u, 1191420956u,
4250273882u, 2217329477u, 3619012484u, 2320390083u, 1618600250u,
100602741u, 3962829626u, 3325838530u, 3310041575u, 2202357234u,
2410265700u, 1855854724u, 1586666379u, 1893433651u, 4212894970u,
3078470962u, 3005791950u, 3645097109u, 2729330720u, 178175659u,
1878759843u, 3613064024u, 2235022317u, 1229007963u, 1217716121u,
3424643385u, 2025817426u, 2541310454u, 3491127040u, 834075061u,
1476080952u, 527792572u, 3142617040u, 990164480u, 3538861805u,
1101804820u, 254185979u, 2139277356u, 3053978085u, 3636278570u,
1588526078u, 3265686058u, 3200724466u, 3305433961u, 1714292212u,
2894641386u, 286242900u, 2390694965u, 1104137642u, 1729447649u,
2603147116u, 1739535876u, 2332325654u, 3923517970u, 975963350u,
3046750553u, 4287139816u, 2887426453u, 3205373337u, 2829120066u,
3989557087u, 1090404329u, 2762938959u, 2016187695u, 188074317u,
562585328u, 1185556641u, 3980179851u, 2922039667u, 3215853289u,
946979886u, 2822925104u, 803185936u, 1852384677u, 2297156223u,
2799487985u, 1756284627u, 2317738144u, 1335401093u, 674337096u,
2899555797u, 3996541014u, 3014749938u, 283034558u, 3481962136u,
3810308241u, 2725662577u, 744192370u, 3665583468u, 571653166u,
3181462357u, 1782231829u, 563269281u, 1274600369u, 2386970918u,
363976120u, 2931953430u, 614822572u, 1661454733u, 449226294u,
3506516244u, 3427050773u, 2620464687u, 505585754u, 3256549852u,
321182353u, 3890429063u, 2030404657u, 1191957414u, 3469037079u,
947528907u, 578915297u, 2155016115u, 557136361u, 374100253u,
1716551606u, 1064892772u, 2282836509u, 2205887435u, 735861059u,
2088833463u, 3884993958u, 1520195389u, 3349226581u, 4116948321u,
3654190067u, 3585109483u, 2170692034u, 4104050396u, 1431760441u,
871040163u, 3131221596u, 4039637966u, 3255680597u, 1537348827u,
4274038615u, 2766931218u, 3080056590u, 2427576150u, 1698622741u,
491269657u, 2957152254u, 4003327323u, 1665870563u, 2898998885u,
350910601u, 3377912239u, 56558544u, 2757732126u, 3003019578u,
3020476484u, 1103562767u, 266867533u, 3238470691u, 101050052u,
2174141449u, 4261294044u, 3377977245u, 4283033233u, 1649319944u,
2407542500u, 1186270608u, 506638155u, 853299114u, 528018288u,
3370360190u, 3432726533u, 33304936u, 746516661u, 864441540u,
877624554u, 549536499u, 2512486873u, 1718378202u, 1877264374u,
3907125156u, 3480301523u, 1222420918u, 2962412787u, 1897386667u,
565602854u, 870635873u, 1837265416u, 2093005006u, 2069832336u,
421542850u, 546177829u, 3737295211u, 2022730805u, 114777545u,
1045010491u, 1474827040u, 7636789u, 3926378049u, 825140914u,
3894878768u, 2235348820u, 4209167372u, 1363271078u, 1633012431u,
2604598105u, 1475584955u, 363136592u, 2939993958u, 3395026321u,
2769982499u, 2579982422u, 3377853512u, 1926697291u, 1309179303u,
198769522u, 525328917u, 2939632387u, 3839345362u, 857890368u,
1404166316u, 1175685399u, 3359187637u, 2911320684u, 3331860351u,
150684895u, 1830720677u, 3549325302u, 1721173678u, 1541682359u,
3727128665u, 1378619663u, 3657645799u, 427125659u, 87651116u,
816648775u, 1111028388u, 3408906806u, 1198529401u, 4082457652u,
2373720194u, 1279364663u, 2697296422u, 4274091187u, 3991008751u,
2750937690u, 745247050u, 3020601003u, 3207637609u, 1522623855u,
3440826157u, 1459824707u, 275982735u, 1366156119u, 2084141301u,
3371738706u, 3652235981u, 3414352861u, 3867568134u, 4143632352u,
2508301197u, 2694712076u, 663648113u, 4084805516u, 2045731357u,
103690742u, 3579296438u, 3853685199u, 4040332527u, 3433047383u,
2160986205u, 3880533570u, 2124079194u, 898702193u, 1377522152u,
2510928900u, 524137274u, 2676839533u, 1147766985u, 2659663351u,
1441686856u, 2336342795u, 2323419808u, 2616909909u, 367789898u,
2802090548u, 3912305190u, 3394874017u, 4182826382u, 378652856u,
2456117771u, 3644581920u, 650421961u, 1356327939u, 1270283631u,
1353114655u, 1186775090u, 2229315614u, 60977715u, 255049167u,
1393113108u, 91557822u, 3460789587u, 4255756627u, 2680883563u,
1961238627u, 2706826361u, 86694213u, 3568183186u, 1174931951u,
3101787400u, 3245440880u, 1012545275u, 4023587262u, 25415056u,
3884392715u, 2033651573u, 1517048548u, 2157890606u, 1607160396u,
1733385865u, 4000967569u, 702762527u, 4219828471u, 2839214666u,
3612303148u, 2417079479u, 561191037u, 2668684575u, 1049452531u,
3056008028u, 752063538u, 1442500991u, 2201174758u, 1248774154u,
165187750u, 2945670372u, 435357616u, 3927358478u, 535926151u,
3753175365u, 256444691u, 2255485820u, 1023308722u, 4229846989u,
2519054772u, 651526182u, 4180758060u, 2654793384u, 2610214273u,
610288969u, 1979520346u, 1745042640u, 2256795625u, 954259986u,
1077808451u, 2678875090u, 955102447u, 2059446553u, 3293602562u,
1583006223u, 2748412790u, 4129522985u, 1799912684u, 461379416u,
3072251629u, 2023808855u, 3368588935u, 1852160624u, 3234147626u,
2398022056u, 3965955751u, 2934088597u, 2993217622u, 750328728u,
783088312u, 3770678320u, 3156679282u, 36274327u, 1466406645u,
4053852068u, 438490559u, 2718496037u, 3313180021u, 2382533773u,
3930250216u, 3894526091u, 3389067170u, 2754596462u, 2355173790u,
2384382760u, 2238960674u, 1652306376u, 4043138340u, 2268422975u,
702886942u, 2158419984u, 313074687u, 3916694140u, 2872536179u,
4110613033u, 3497889789u, 3345443240u, 3438724296u, 3831640476u,
1721511461u, 3181187841u, 293747726u, 1016981259u, 319715874u,
2604613639u, 3866375162u, 1129514664u, 4090305697u, 1415656234u,
3904058353u, 3454231580u, 1137421991u, 2313708721u, 3189903818u,
2359396326u, 4140811458u, 2619162542u, 4018716781u, 2943094968u,
4275110940u, 3753225546u, 393641299u, 793819538u, 3807603495u,
3584270096u, 583337815u, 3204343682u, 2704728429u, 1260285383u,
2070005280u, 1290966975u, 3841613013u, 3748951459u, 1996539050u,
15255144u, 3555533616u, 1896042895u, 457790456u, 2103229914u,
3549835684u, 2608881213u, 3750997458u, 1284886852u, 3983637798u,
2754133138u, 1375874601u, 3702999536u, 4047595327u, 1757722874u,
205211433u, 1550020058u, 2625086805u, 888856283u, 260526089u,
3603211830u, 3874949683u, 3705639611u, 1244107692u, 2576564054u,
1798606541u, 1538798258u, 1914115295u, 3465780481u, 2191768384u,
1053339258u, 482479463u, 1590615673u, 1678894824u, 2583029443u,
3312998864u, 2348965967u, 3592411649u, 2586886059u, 1193775683u,
3166643410u, 2848176518u, 4244785412u, 3263141460u, 2534433066u,
3857841146u, 4030264873u, 2160049808u, 2568607774u, 3962849448u,
1063016183u, 752325873u, 3916513901u, 3666512065u, 3742123864u,
240316886u, 273053100u, 1974725783u, 103853041u, 498343646u,
2849277012u, 1531820781u, 2800822870u, 2172374911u, 2608056220u,
2938222996u, 2495640435u, 2050031019u, 1581664696u, 1192708798u,
3958663429u, 3409883558u, 1261646904u, 2262137662u, 1495935118u,
3549216229u, 819898291u, 616300818u, 920698111u, 531434903u,
1750605108u, 2331202523u, 2604625024u, 311416415u, 3413350776u,
4091626041u, 3339815970u, 2156981844u, 1053778854u, 3946541364u,
757561673u, 2794628342u, 2560288402u, 3516100843u, 1078950707u,
1096405570u, 2565723989u, 3166139486u, 665944531u, 3426830504u,
1316229722u, 3470576224u, 174450923u, 1756691252u, 1809953431u,
2120869441u, 744710690u, 638114562u, 3462360879u, 662650689u,
654132881u, 2029278034u, 4053373589u, 659248560u, 1754023002u,
3683623866u, 684016545u, 2635610107u, 3319934252u, 877308702u,
32003886u, 3136239345u, 2204537667u, 617587244u, 3444132147u,
3394465910u, 707665795u, 3673280986u, 2732829120u, 2865909493u,
3553125825u, 2860898385u, 2982421098u, 1193861977u, 1034606365u,
1752852792u, 1621071619u, 2528057870u, 2138762952u, 2308749354u,
906867989u, 779669216u, 2232060698u, 480996617u, 2925606018u,
303678891u, 3851015553u, 3348999586u, 1213516375u, 3489393664u,
2606497132u, 4155605153u, 3740915058u, 3037706031u, 2239177712u,
3123401220u, 1990275519u, 3162603957u, 1918939652u, 776035672u,
2865857149u, 571764668u, 151622100u, 2353602509u, 2112275436u,
3057460223u, 1545579966u, 257397390u, 19209971u, 2138790032u,
3753848035u, 1085255822u, 4235734180u, 875019346u, 3217942945u,
1091459686u, 3587756657u, 3077984076u, 1491592709u, 3017547658u,
2252844554u, 1985555588u, 3040031536u, 558425569u, 1123411656u,
173859531u, 3673271296u, 495041198u, 1342690724u, 2894423806u,
673054854u, 3159268470u, 3113987190u, 2436187367u, 1936640302u,
1360880324u, 1912925050u, 1245740864u, 1374924892u, 3948122288u,
3665262872u, 1730168177u, 1418975463u, 1724598953u, 1518264520u,
155679217u, 2777491364u, 2127704373u, 479136316u, 467963358u,
2038497471u, 4009847343u, 3214679953u, 316320711u, 43436245u,
2439770433u, 3061525191u, 325285125u, 3418463477u, 265361904u,
3317034447u, 2046949609u, 2398727149u, 3035501454u, 3766818899u,
1907069371u, 3915369678u, 825294741u, 3960827812u, 2822610696u,
435348151u, 2960342732u, 2841517289u, 1245939424u, 501966471u,
1523054284u, 2986922068u, 3643707400u, 1960129231u, 605842596u,
498475817u, 2091802075u, 1546806085u, 4249712391u, 719048827u,
1236161870u, 1455705076u, 611924837u, 1606154038u, 3804768796u,
2147049065u, 3141135911u, 2326016873u, 1938285117u, 2106616699u,
3649256942u, 2518864732u, 3041005008u, 25486255u, 317223081u,
859651472u, 3423179818u, 3316420743u, 1720381191u, 2949551625u,
4153784543u, 2375654557u, 4245912914u, 3055577422u, 426826876u,
3371315320u, 393263103u, 1674632271u, 2001097492u, 3810913408u,
926582509u, 2004092737u, 1225977080u, 704646682u, 507362042u,
115002871u, 772062004u, 2509172666u, 671380383u, 741064994u,
1087280005u, 2458813622u, 3555270161u, 432569830u, 1768785658u,
2788242172u, 3626575210u, 3924321291u, 1056700312u, 807145567u,
2457173701u, 4163083585u, 2389340792u, 2527897320u, 148652138u,
809466003u, 1310067162u, 147554547u, 3006884242u, 1648641905u,
2507398430u, 286276539u, 1285247198u, 1497575669u, 4272381767u,
1630690228u, 528903131u, 3782308744u, 3328620223u, 2544636753u,
3716824890u, 3359475073u, 1715425081u, 493809452u, 1482469337u,
2880570645u, 4246120078u, 2462260788u, 4005994348u, 3376710207u,
3055770626u, 1224220146u, 706700781u, 146623188u, 1905647200u,
1835596148u, 114826369u, 1833749674u, 534781147u, 233967048u,
942256881u, 3699192716u, 188293730u, 3910438208u, 2394758371u,
3662527011u, 97504699u, 3543922236u, 4206828553u, 3734565571u,
3586763714u, 403958048u, 2063667481u, 2730205743u, 589502476u,
1149905623u, 4095869863u, 2805195184u, 4223446468u, 3102461252u,
423688803u, 4256209713u, 1518355137u, 4269931685u, 4174808463u,
2019550169u, 1704760048u, 1718939701u, 602013714u, 3655037789u,
1997992275u, 782052616u, 2168800816u, 284956141u, 3975978923u,
644864581u, 3042712626u, 2180684793u, 1466664828u, 1267605484u,
2784735889u, 1428685493u, 2544323949u, 889906898u, 4235848255u,
4186602195u, 855556210u, 2342896146u, 3307519234u, 2197566638u,
2509561763u, 20519604u, 2319402891u, 3907092227u, 805926263u,
1545081676u, 946901149u, 174874593u, 2904667651u, 1004586041u,
1671610396u, 2507164708u, 565710128u, 2195671193u, 2148970716u,
64150785u, 3111996478u, 3853037378u, 3929028523u, 992899482u,
698318534u, 1024524470u, 4196904510u, 3557517929u, 4285406934u,
94205271u, 3530304939u, 2305824750u, 1531731847u, 2100892683u,
4141695457u, 717968711u, 1020961798u, 1435297145u, 1174399738u,
3484051255u, 401988634u, 18353084u, 2476579762u, 3884197419u,
2161379550u, 3488516503u, 4291859194u, 429223686u, 2634560425u,
1960550128u, 3018314044u, 3956111413u, 3586019740u, 271458754u,
995152322u, 2784808343u, 2699155930u, 718003490u, 88374071u,
2116640876u, 2418838888u, 2473871392u, 3887260803u, 291756441u,
317239670u, 1991643081u, 1067021559u, 52172441u, 3466077380u,
2808782519u, 506095445u, 2721138411u, 3170096146u, 2636465745u,
3084352426u, 1216338971u, 1227230645u, 3998968120u, 2009459829u,
2474360224u, 345636082u, 601138538u, 1362885697u, 3578651252u,
698241090u, 1118227414u, 5507337u, 2780083822u, 703266438u,
864120870u, 1698678511u, 172897137u, 144366506u, 1820854951u,
2113926171u, 3294417442u, 3001580140u, 3365898069u, 2414288823u,
2191315816u, 2041923551u, 1374216245u, 1792102283u, 966439255u,
3142541052u, 3926566349u, 4034829900u, 2276773096u, 381471573u,
1895081823u, 1362996393u, 2592249580u, 2898726226u, 4223177326u,
3400414171u, 2052800787u, 3853885905u, 1028196740u, 3183947606u,
2486531127u, 3167268159u, 1866096562u, 2950293380u, 994523562u,
3023614567u, 4104267478u, 1191097596u, 3529256093u, 3418504368u,
3894797255u, 3908535736u, 3298561721u, 3288395583u, 912501104u,
831862193u, 858008061u, 3583526686u, 3604044732u, 11642333u,
532352558u, 2447342506u, 49917723u, 2465972387u, 49071225u,
189297954u, 3406843807u, 2379895567u, 2252069007u, 3118935217u,
2612642690u, 489772543u, 3046688150u, 1991370098u, 1491676633u,
2171172062u, 2631485941u, 111539597u, 1754135798u, 104108364u,
3801121441u, 961805875u, 3244343746u, 3927144143u, 1042956596u,
2171259252u, 1546798356u, 2949756312u, 1677484392u, 3916024040u,
2117087490u, 3806450987u, 3716708844u, 3052844593u, 1098132833u,
1944120348u, 1211978277u, 1373013705u, 1417003306u, 1935792551u,
2645561211u, 4148953952u, 530900685u, 4282117874u, 1246946090u,
3856432168u, 239949635u, 140665127u, 3955560396u, 1458503553u,
141173732u, 3283724848u, 2719866813u, 1750621676u, 550663579u,
491600368u, 3263446369u, 1961062013u, 1243373458u, 3444793917u,
3899300498u, 718538962u, 3064564239u, 101084001u, 4001046471u,
690719870u, 2544332192u, 2973901205u, 3510440400u, 2221840969u,
3581406537u, 2687583608u, 45358658u, 1597859661u, 314280821u,
3494340276u, 3133266884u, 1787593645u, 87373007u, 3037573439u,
3752761966u, 1788735812u, 2276942058u, 3166047868u, 1996038283u,
3602485091u, 493959987u, 2734283831u, 1597766558u, 1319887499u,
3957554749u, 967477137u, 1871108451u, 366543865u, 3417930960u,
3465456271u, 683117185u, 2140844389u, 1633256418u, 3595239200u,
272311865u, 3868727953u, 516898363u, 2749883233u, 3669048734u,
2889507150u, 343253656u, 1307200448u, 2276582436u, 1455456255u,
3095475925u, 3167968348u, 753145196u, 1720643028u, 1964199342u,
3245346896u, 2501510517u, 2401288980u, 3190253603u, 3392954261u,
927482091u, 2739586668u, 656503075u, 3631723682u, 2774039073u,
3581048448u, 2109905006u, 2654627331u, 625449654u, 3921753764u,
533200192u, 1708723687u, 3105862488u, 1938982508u, 284773522u,
3014100134u, 2332799199u, 3899421698u, 4054778144u, 1855118412u,
2423445164u, 2085429129u, 2525269691u, 1050404537u, 2665308718u,
2195447044u, 1546419073u, 6271311u, 848651525u, 2114666412u,
2361256342u, 1968111351u, 2378425902u, 2399819062u, 2046693061u,
2184541122u, 606566810u, 1184406086u, 3849119084u, 1782109246u,
1711162988u, 3725213412u, 1978982002u, 2084076307u, 4226808472u,
1381220175u, 2756022796u, 1155923374u, 1310996083u, 3892088705u,
2900168226u, 2172331364u, 1976800812u, 3446717919u, 3018115416u,
772796339u, 3119675141u, 3399966733u, 2483366635u, 2251157986u,
3721643942u, 92354950u, 2276558847u, 3199161030u, 391156337u,
516105765u, 3031568469u, 3056187358u, 327152205u, 2268820210u,
154728704u, 2498616329u, 2687795551u, 1661550221u, 3058059426u,
2011392238u, 3213116060u, 4232673760u, 188451691u, 2316494518u,
139654414u, 2820632408u, 741805800u, 3398953290u, 3029114036u,
4228239470u, 1294389995u, 220293836u, 832710216u, 3520956438u,
3326239211u, 2002353592u, 2910456568u, 1116726602u, 3947894185u,
2269194026u, 331201566u, 23448299u, 2501636454u, 1481063438u,
531225803u, 3374157189u, 1250339898u, 2807211779u, 3509443222u,
3149299112u, 2512315800u, 2156034521u, 3927375017u, 3009858040u,
3815089086u, 2493949982u, 3668001592u, 1185949870u, 2768980234u,
3004703555u, 1411869256u, 2625868727u, 3108166073u, 3689645521u,
4191339889u, 1933496174u, 1218198213u, 3716194408u, 1148391246u,
1345939134u, 3517135224u, 3320201329u, 4292973312u, 3428972922u,
1172742736u, 275920387u, 617064233u, 3754308093u, 842677508u,
529120787u, 1121641339u, 3300737790u, 3072286611u, 763885092u,
237936516u, 214735112u, 1071670392u, 2640290649u, 2253339066u,
406563643u, 857883160u, 1943298024u, 482572274u, 1387459037u,
3227802952u, 3719718158u, 254239224u, 2056147900u, 1907664448u,
3028647233u, 1385596859u, 2691640069u, 4156402531u, 2727923167u,
2529722889u, 3095622616u, 1958102896u, 576816725u, 1327262146u,
614269765u, 1721856728u, 1312650621u, 2437977684u, 1733921636u,
2123749922u, 3790190001u, 3934886640u, 2878714597u, 2564557568u,
157082304u, 2081155532u, 1874993431u, 29873796u, 1575628456u,
4088191944u, 2658510623u, 1984791300u, 3812698918u, 3787281972u,
4231096806u, 3785648472u, 2977746737u, 671867256u, 898437006u,
1316824526u, 2640443682u, 1404000060u, 3276358491u, 4161289148u,
1102117255u, 1256660265u, 209840788u, 385024522u, 2368673317u,
323107512u, 3455934026u, 3731694261u, 3391583476u, 2939001717u,
1103408741u, 1083361420u, 1698019267u, 1565815683u, 3463127127u,
3731607982u, 697017152u, 734146234u, 3016440987u, 2640822923u,
468448749u, 400190664u, 1063137237u, 1360374355u, 4071057687u,
3077992194u, 1418755066u, 2114340252u, 507520129u, 2219575806u,
2032764621u, 2022031889u, 4206268338u, 3431678471u, 2027400693u,
2669084807u, 831934007u, 2741455826u, 2363266155u, 246856212u,
632436514u, 3515740889u, 2195525760u, 971767468u, 1276384569u,
3850605480u, 249929275u, 4103572387u, 173516974u, 1665191261u,
3656906633u, 323924265u, 2631672499u, 1675859583u, 3734620872u,
1388796197u, 4080779261u, 2337389174u, 2655227505u, 2543838574u,
3971410265u, 420679752u, 496026352u, 186764349u, 165231151u,
1627667691u, 2166211449u, 1762978544u, 1450698279u, 244833631u,
3701624698u, 3546129192u, 432955709u, 2578973523u, 1268347370u,
3585006787u, 3065734222u, 3840890096u, 2730792797u, 1190210715u,
1229058459u, 2004508211u, 2236271394u, 1163898177u, 317061964u,
4104512475u, 3981785820u, 2724518087u, 2447324937u, 612066133u,
3833016990u, 581709676u, 709654776u, 2295002741u, 1137254807u,
3385935788u, 1271908877u, 1575381586u, 3541074184u, 2662027818u,
578812846u, 695633467u, 3826065625u, 2352553817u, 1189926887u,
3949219588u, 1149364385u, 1140956216u, 2758597267u, 2208280441u,
2004286835u, 23811599u, 101605991u, 1718702543u, 2565308531u,
3504199076u, 1093913647u, 2943472056u, 208957281u, 93183733u,
26200246u, 2515020035u, 3147530638u, 1167877885u, 4173286473u,
3769999835u, 1316803433u, 2676177653u, 2249893478u, 2728386872u,
1289080741u, 108414488u, 911939596u, 3631792077u, 1201915048u,
443256488u, 695071951u, 2382437614u, 2026588982u, 2632432926u,
3752320434u, 2522821802u, 645589903u, 2852069592u, 1507054019u,
3446656352u, 352137468u, 3660766493u, 659827898u, 2694662642u,
2414681487u, 981423112u, 2969509231u, 1181913590u, 3283845787u,
1579289584u, 1736014821u, 1868176940u, 944873323u, 1817775084u,
2530710862u, 1627730672u, 66245778u, 675589177u, 926873064u,
1555989601u, 3241218062u, 2208111558u, 2091107069u, 2186880097u,
1922662991u, 3262102331u, 407680084u, 3225806537u, 1728234429u,
2815516280u, 1467728810u, 4113584515u, 2523822574u, 3907401252u,
1890262741u, 2857922946u, 9312338u, 1743264483u, 1703482351u,
1125583605u, 3170904314u, 738854734u, 1759558300u, 3184633114u,
1178715144u, 1960548124u, 1037689637u, 2750727957u, 3611858166u,
2361354361u, 467381126u, 2712884168u, 3111383860u, 3607434155u,
2140986302u, 1659435938u, 2870614947u, 483402068u, 3327353724u,
173441805u, 2892921505u, 322459867u, 342084856u, 476285132u,
2067116357u, 2987638716u, 3139221121u, 3648371306u, 2249325349u,
616697281u, 3744830951u, 1842700074u, 2971192596u, 3726408523u,
109869626u, 1487813247u, 885160389u, 1639902238u, 2438016503u,
2809256484u, 467766414u, 2269768842u, 3533241669u, 1626201598u,
3396738581u, 3323794334u, 1684642258u, 630214583u, 683085617u,
1860535308u, 1692841768u, 213970453u, 1620501115u, 2950013140u,
2600979684u, 3101788642u, 3940886529u, 1051539558u, 3444502811u,
686778540u, 2040757101u, 453012501u, 2726351009u, 2450885997u,
3954218997u, 2161221709u, 4273602338u, 315911737u, 3837424460u,
3983366596u, 1961106069u, 3092378093u, 3794692952u, 3936554087u,
3931909059u, 403814402u, 494561694u, 735241236u, 1852073032u,
1338882628u, 253049925u, 831176075u, 2962932411u, 2624182132u,
276217644u, 2654594797u, 3505958190u, 2643143479u, 2909381563u,
2812077621u, 2561795171u, 2649734514u, 1600038684u, 572123377u,
2903239907u, 3676987477u, 1946232532u, 4192788977u, 3352250323u,
2072925788u, 3243132465u, 2710328260u, 559282756u, 2496495841u,
1663691009u, 289654448u, 3463704651u, 892590470u, 1840421798u,
3271090533u, 4143706049u, 617178688u, 134482073u, 2269042691u,
3230232400u, 1073622572u, 1292832927u, 1514583707u, 343422799u,
2568797335u, 1703121731u, 4246032950u, 1125492680u, 840571992u,
2904558028u, 373108020u, 4002658231u, 3705499974u, 3080886235u,
381031087u, 516747576u, 1882498794u, 2655103969u, 1722338904u,
3506481279u, 954136253u, 2194640986u, 458904938u, 2230909876u,
1232295042u, 4026050644u, 4268594314u, 386790887u, 4165330488u,
2512717163u, 2939124594u, 2996196263u, 751292327u, 4220296919u,
1806647125u, 3424044432u, 529412756u, 2785560848u, 1277215461u,
1255562273u, 3182925185u, 2338361557u, 1825211939u, 3677840444u,
1711411618u, 1758593657u, 3511837694u, 1349462441u, 3428028389u,
830423639u, 916445791u, 1046053695u, 1356825518u, 2206311325u,
4024885318u, 761804059u, 1750908698u, 633217941u, 1238957827u,
4111074188u, 2364254471u, 4075930521u, 3987296879u, 3614538834u,
1681622248u, 233233044u, 1350971022u, 703752965u, 742511090u,
1319273373u, 1551556057u, 801526694u, 2261637738u, 3429584111u,
2522240856u, 4033776321u, 993802642u, 276019073u, 1802442104u,
1624529825u, 3688548619u, 1428574037u, 2759605887u, 714112429u,
2464378249u, 790901819u, 1071757684u, 2328808137u, 745645834u,
549566994u, 812008863u, 1682615503u, 1156655121u, 601964903u,
2388185358u, 2263159343u, 2449211150u, 1437661351u, 12615427u,
215564646u, 2484119735u, 2932155371u, 1762139369u, 158159499u,
2365521282u, 2277660798u, 3067589594u, 1443309319u, 3875571875u,
3148481662u, 4251148624u, 899549959u, 2383987797u, 4054743020u,
1617718571u, 764855974u, 3623170507u, 1294195985u, 2092418947u,
1392907274u, 259338315u, 2169056952u, 486370816u, 2608182505u,
58281361u, 2489916780u, 2571322701u, 3789374714u, 451393610u,
1906658293u, 1412587058u, 4038584782u, 3111791370u, 614696571u,
3167192919u, 3717660107u, 3195921972u, 3815660283u, 3041128023u,
570765305u, 3981085879u, 1107446894u, 51726088u, 293239046u,
4206823928u, 2266071917u, 1624419600u, 3390262152u, 177263260u,
2064461558u, 1929086034u, 1656019088u, 501074449u, 1715323410u,
3733759909u, 2474982900u, 2025499441u, 969019452u, 659526089u,
840640563u, 2500391789u, 2464587729u, 3777665909u, 3610207335u,
4206950686u, 663950423u, 3911031610u, 374291529u, 3602165615u,
3828747911u, 1422398845u, 2633015130u, 911010235u, 1250039282u,
3668786465u, 2146176295u, 2998145602u, 3953806681u, 861918991u,
3533426566u, 1195908145u, 1897435392u, 3160397475u, 4038157920u,
3159042522u, 1607720526u, 2381657876u, 3862186850u, 3469342849u,
3639212634u, 112769417u, 452688082u, 1414408784u, 1229308228u,
507438193u, 1310342177u, 3867043376u, 3493923869u, 4076344759u,
1432407149u, 3844851205u, 292787671u, 889906511u, 858447165u,
4280160501u, 1754833546u, 1022797317u, 141082305u, 1717313637u,
341442863u, 2982165294u, 2660069911u, 2284313116u, 3729297709u,
3404076394u, 3170976459u, 594201128u, 2041497718u, 1243196847u,
1266663238u, 2859272421u, 3185066266u, 3090105225u, 126778336u,
2792308627u, 2668313630u, 1239558284u, 3271595203u, 3721632713u,
408692953u, 136209149u, 1308802615u, 2102270171u, 3155640269u,
326440485u, 295730848u, 523452312u, 3849023707u, 3647301u,
591283519u, 3240559410u, 3618341580u, 1257535485u, 749043246u,
214257867u, 2969963854u, 2265255083u, 2433422659u, 3703613001u,
1868981396u, 219206218u, 1921827284u, 827842542u, 1269673531u,
1710834839u, 1027401811u, 3163026058u, 1902411060u, 3815930641u,
621420248u, 2054777317u, 4124947909u, 2353234036u, 1977996769u,
2808784096u, 3225046473u, 2931747545u, 3142843391u, 1659837986u,
1888420283u, 4259740486u, 2350930487u, 3413152075u, 56968219u,
192969628u, 1423057188u, 1444249660u, 171197140u, 937248230u,
4099400349u, 2399265778u, 1578088554u, 775063037u, 3858403452u,
4225434954u, 478205274u, 1845362180u, 308036862u, 2216561886u,
2390053622u, 1312984120u, 465471307u, 3916802888u, 1751063625u,
3071743500u, 3294521276u, 4183444410u, 3328792670u, 4051235372u,
938291851u, 3776732923u, 519625569u, 2466919130u, 979838570u,
2725879728u, 1317420913u, 1463872356u, 637221019u, 3745811724u,
1494600622u, 893750819u, 930858754u, 650342654u, 2192050103u,
3365807907u, 873848167u, 2720924319u, 1145370623u, 2760666947u,
2161896752u, 1105360170u, 2076071521u, 2063127636u, 3903444955u,
4210510508u, 1867287227u, 3901733700u, 1228642505u, 1554715107u,
1256194637u, 3463194748u, 2108350785u, 3137801541u, 1377619644u,
2043599410u, 3670507577u, 2409694355u, 578584004u, 1915114417u,
2964200468u, 3084637701u, 487846941u, 3464913449u, 851931544u,
4091230055u, 3804622813u, 4062654036u, 1956958041u, 3982899036u,
3060878573u, 1850342510u, 3229380710u, 2199978100u, 3449841444u,
3404506672u, 4172579909u, 2858341611u, 4201756291u, 866708640u,
2147611665u, 2927066921u, 981820178u, 4145753222u, 2926114981u,
3142973742u, 3211993392u, 665956u, 186208327u, 2578776459u,
1544585027u, 4147670018u, 3264346428u, 3529968586u, 2309075249u,
3880526621u, 2125072657u, 481117536u, 2544413573u, 2202704127u,
1672537106u, 1318470792u, 3554362612u, 3127591861u, 3015316471u,
2945509163u, 291484478u, 2591981327u, 3245148648u, 739576946u,
515232136u, 2261837125u, 1917651136u, 579070195u, 3597260689u,
49188367u, 267006895u, 4276877494u, 3617401212u, 2853129749u,
935399421u, 1080878326u, 3188786708u, 3498791570u, 2384965785u,
1857094951u, 3407819412u, 704533477u, 4082950861u, 2567290570u,
395265201u, 2047624633u, 2518905836u, 3372367611u, 801791416u,
1901227854u, 38637635u, 3474202199u, 2474398228u, 1480879307u,
2850068007u, 692791272u, 1196752290u, 1921623773u, 740690709u,
3711563566u, 3014897166u, 1153198973u, 2587583270u, 3871261165u,
1304143030u, 1562173300u, 2399579836u, 3387085571u, 3066436323u,
273753460u, 548762751u, 4066258498u, 509964679u, 3892230842u,
2594454158u, 2641210074u, 4000290307u, 197544729u, 1226784640u,
2052493941u, 2015636260u, 619774998u, 610310685u, 3315794687u,
2524554198u, 109352219u, 3966261588u, 2482511907u, 3321871424u,
2144425402u, 3701574588u, 2168304673u, 382053842u, 4264336703u,
1620184274u, 2591819932u, 4150402746u, 765308994u, 2759980202u,
4277805943u, 1345011665u, 27080389u, 350826709u, 2183825604u,
4075076920u, 3445501223u, 4190013503u, 587180938u, 214271696u,
2154236153u, 1586367270u, 815350360u, 1444414461u, 3464262453u,
3976631943u, 2834310035u, 447344574u, 3456943467u, 1857849941u,
3288069997u, 3622828139u, 3766385238u, 1019699309u, 3574414672u,
664756051u, 1488760916u, 3602182757u, 501971136u, 361544844u,
638366795u, 2663513669u, 2577492878u, 288332466u, 1438600995u,
1325679288u, 3124931681u, 317950919u, 2003481973u, 1680270394u,
3336913304u, 4046786960u, 3928470606u, 379294149u, 258217508u,
137055764u, 1536935606u, 2068904415u, 245653279u, 3279034418u,
2000767513u, 1483858296u, 661632107u, 2388498781u, 2717721443u,
3490673092u, 408205055u, 3671951051u, 422302660u, 3750077128u,
3487755911u, 2475111658u, 225226079u, 3266015962u, 4163085962u,
160505654u, 826502426u, 3108568799u, 235837591u, 1843748945u,
3398011821u, 488014602u, 1703998678u, 2501340486u, 2457941993u,
1583675704u, 3998234784u, 1823676750u, 1727161627u, 3026833773u,
906959134u, 2137574027u, 3944299473u, 3781089529u, 724146943u,
358776094u, 3525324801u, 185536569u, 1029340467u, 4177714978u,
1881106148u, 2149519719u, 3090610550u, 1595510459u, 4026033108u,
1758720811u, 3443479698u, 579449978u, 166684833u, 1954913591u,
2436559945u, 3713643208u, 2787556827u, 80124672u, 668793893u,
984001090u, 4172095298u, 1237562645u, 4246985448u, 2944124287u,
4066835174u, 1203297508u, 3814830417u, 1041598911u, 2553744546u,
1696041541u, 2537753781u, 3964937529u, 1275077003u, 396554334u,
1508985930u, 257718692u, 3339554426u, 2816402520u, 120951742u,
475928291u, 3224192115u, 2290598180u, 3010053799u, 232875814u,
340483867u, 518492981u, 1202103710u, 2360369545u, 2906122107u,
4156373681u, 475597219u, 1589253586u, 146259718u, 1926066295u,
479682976u, 1340900563u, 827889393u, 1244772727u, 1312527732u,
4198626021u, 3996441052u, 10644110u, 3247648552u, 1281332215u,
3860750678u, 3285923885u, 186872129u, 3865515020u, 3302355353u,
2477862790u, 3310744082u, 3841112686u, 677846076u, 2053589237u,
1932534256u, 559147278u, 1877030045u, 385124408u, 254461835u,
508013400u, 4278960989u, 316600986u, 3139554192u, 118560138u,
1206070571u, 946801128u, 1202200929u, 3533120670u, 2072176200u,
3754732210u, 2202753449u, 2497549341u, 1824188449u, 4096170263u,
1778678071u, 2755925781u, 1162425729u, 3525283794u, 2549672156u,
186047547u, 949616424u, 514250452u, 428000582u, 1402456747u,
3275087661u, 1662527311u, 1062266134u, 2896808207u, 546372435u,
426202384u, 2470040092u, 3679462914u, 2850980138u, 4246129126u,
15470179u, 414350056u, 3096151869u, 389632407u, 2047499061u,
378474270u, 4081137159u, 536430886u, 1728154601u, 698697206u,
1062097602u, 836724005u, 1142685433u, 3332408589u, 3512314929u,
2582057314u, 14591221u, 3331171678u, 1926729414u, 1869132451u,
2013918714u, 871594890u, 3319674255u, 1404734878u, 2348955092u,
2795656019u, 1375503625u, 1259278002u, 257464350u, 813387295u,
895153179u, 844238198u, 1634630496u, 3998472331u, 3344820330u,
602607720u, 3622762973u, 1362293693u, 3720441663u, 769877944u,
3615743708u, 2648039718u, 970534205u, 2056260250u, 2135791038u,
451217943u, 1814422094u, 2393651123u, 1701892116u, 909762509u,
1408803141u, 4126742002u, 1074833343u, 2157239058u, 3166377133u,
4238930216u, 563692261u, 934622773u, 1780917021u, 3698369962u,
2567120916u, 4099632335u, 278317364u, 699067013u, 1433276974u,
3412965834u, 776182569u, 2945101563u, 1901527490u, 3590591554u,
1104453414u, 1815882203u, 3901802352u, 2083417226u, 3151899284u,
244057543u, 3209024595u, 147951658u, 756739207u, 1235768209u,
3156017009u, 3193645212u, 1880049815u, 1295819147u, 1168515246u,
974065603u, 3058698171u, 5709523u, 1911494647u, 3913099549u,
3609249161u, 3867419584u, 1950266164u, 1036231561u, 2487793992u,
2691309339u, 2942155942u, 2965968254u, 1746424309u, 253966721u,
4244463819u, 2067463969u, 1950849308u, 1246571141u, 4097566328u,
346406741u, 2506944995u, 2759023005u, 4117530649u, 2724202928u,
2058774036u, 162803051u, 4227611518u, 3088016137u, 1658512262u,
1416465784u, 2137055388u, 878100347u, 2277478293u, 525092662u,
1741194555u, 1309123261u, 460520284u, 119434317u, 2016523652u,
1640172061u, 3804988800u, 540190186u, 790962267u, 1460908145u,
3688753525u, 3461703962u, 3039026826u, 578931852u, 1006670859u,
3481601471u, 1918534958u, 1859686764u, 4023948837u, 3920621011u,
2540003721u, 67137340u, 2043405341u, 3268848308u, 1306808385u,
3605706053u, 1623313713u, 660869119u, 2853351111u, 3475175842u,
2821734805u, 3814658188u, 3654921032u, 2472577430u, 754344802u,
4088246401u, 88411392u, 700117482u, 703548004u, 2245532518u,
2639673532u, 3977880118u, 50148058u, 931630340u, 4041558803u,
3949109103u, 2965310022u, 1968230113u, 1448979683u, 2858564441u,
1523429339u, 1452231187u, 2696376206u, 3594274238u, 1221549017u,
2397200653u, 1488063947u, 2905130063u, 199399599u, 4073133774u,
4237311111u, 3055565669u, 3367773316u, 3162354197u, 297828300u,
4122926713u, 2903038630u, 2506015605u, 2493069266u, 396227382u,
3064295038u, 389390920u, 1684789502u, 2022004674u, 1546447938u,
2342558675u, 3323380043u, 593016737u, 3277745628u, 2071469665u,
3550721728u, 2172088092u, 1279295579u, 4216165077u, 1510998944u,
4075672776u, 2930025022u, 2136492188u, 182691603u, 4038078968u,
1396096227u, 3273166256u, 2094934945u, 4099357359u, 1007544560u,
3699672923u, 2300884465u, 2980210279u, 4244552370u, 589833589u,
714003734u, 4002387247u, 3389813967u, 845344855u, 3827405748u,
1095009851u, 1096246435u, 195059445u, 390829018u, 45983343u,
2942709471u, 2338891311u, 1314753483u, 1040822690u, 3615731833u,
2047806006u, 203722163u, 439422620u, 2262897255u, 2481399711u,
2730149622u, 268361952u, 351807012u, 1796447121u, 3551647148u,
3863815581u, 3930491804u, 3040825682u, 3498148643u, 3103447131u,
292250033u, 226867327u, 3034518570u, 3275929931u, 3242711804u,
3226789931u, 2600170516u, 3264262736u, 497730864u, 3847393656u,
2138081132u, 156554468u, 2050395814u, 3341597363u, 3771202984u,
3623479970u, 3811066097u, 4180581721u, 2728037769u, 2759868955u,
121442518u, 3472315639u, 205237287u, 2850789567u, 2312554204u,
1182211478u, 38967328u, 3702438304u, 375884310u, 3165268977u,
983625816u, 2735905787u, 2508035244u, 3513180306u, 10812940u,
2299525101u, 1370593040u, 2901849677u, 1637452236u, 1505988434u,
1234543967u, 197861388u, 1930286607u, 1561122202u, 1215392833u,
3981188336u, 3849737971u, 868629879u, 2183787208u, 3332599237u,
966010177u, 1084918212u, 82969797u, 3808821963u, 1864232486u,
3366209990u, 751714288u, 2695039573u, 1097849769u, 3022976865u,
587638393u, 2744414517u, 63322775u, 770817695u, 2209918549u,
1635742189u, 2095921391u, 495753095u, 2352947823u, 882910281u,
3059789361u, 2202887209u, 2519930578u, 1983703178u, 525620646u,
3007446873u, 3466043628u, 969502396u, 2222572818u, 3631038137u,
3440085912u, 3544306054u, 2279011116u, 1361979741u, 247624876u,
1609426453u, 633820846u, 457170537u, 3189982065u, 313104052u,
1671772203u, 3987982914u, 3878607460u, 442784563u, 239669768u,
1186013783u, 1469875483u, 2717949819u, 720088221u, 3130619991u,
627890744u, 2164497000u, 2241323725u, 1539052750u, 4116364762u,
3447090944u, 2435636794u, 1034457706u, 2225396704u, 2039700441u,
2193560651u, 2759784453u, 2838663578u, 3925342473u, 4229223551u,
3059096898u, 3615459818u, 1983004688u, 907253649u, 1326210552u,
3579190630u, 3272911913u, 4131935105u, 1327722125u, 2908147995u,
4092513009u, 746274712u, 736869831u, 1497858220u, 487961967u,
2386169970u, 1439014353u, 2738069928u, 1944184985u, 3492078389u,
2809697569u, 3555856753u, 74229530u, 1188033126u, 1042117947u,
1505471861u, 1978689067u, 4284088321u, 1879582610u, 197373605u,
1581803397u, 2542952419u, 2458103082u, 2609274498u, 1208734497u,
3053599284u, 3356619347u, 2786163035u, 294958267u, 62146935u,
2950201268u, 382600974u, 2796353027u, 480450472u, 1731575026u,
4086256647u, 797880888u, 2653010568u, 2663080685u, 3860407534u,
2658068184u, 807060335u, 674881738u, 51791346u, 2375548938u,
2339108673u, 2765711021u, 2074225046u, 1909060248u, 20753244u,
2726236940u, 2902081023u, 2864855158u, 2811409260u, 845253867u,
3292451361u, 3033695434u, 3775963086u, 3602564352u, 4196643721u,
3060262852u, 1753216383u, 2691205345u, 21535303u, 3469036080u,
2125167827u, 3818146091u, 2837019400u, 2727529820u, 3494652317u,
1112114299u, 2598168998u, 1146515049u, 108198915u, 3736718166u,
2342983819u, 1756214915u, 39732867u, 1665876672u, 2145382992u,
821052743u, 2839251707u, 649422276u, 2893622878u, 3782158454u,
1964100944u, 553504817u, 921832272u, 2790668159u, 2937271603u,
296629342u, 3972341743u, 4122628545u, 564370865u, 595711954u,
1004248294u, 1452078904u, 4220574292u, 1346997234u, 1135155980u,
2436887773u, 3222929103u, 2962393409u, 2323344035u, 3165484739u,
1084131787u, 2525794560u, 1899607021u, 695377600u, 1997857469u,
88053015u, 3734708914u, 2495304031u, 1581633088u, 2043722547u,
4094560820u, 4226819750u, 3423672780u, 3994550009u, 3250795980u,
2099028017u, 985784650u, 535968328u, 3219077037u, 2978028186u,
292695848u, 3814517741u, 3820167765u, 200283462u, 2302587436u,
4179722693u, 2429319487u, 2443111044u, 3933774850u, 3981281444u,
847952093u, 411105399u, 125762624u, 299104240u, 191979292u,
4260457698u, 1517829698u, 3157507235u, 2949795084u, 4045869099u,
442379810u, 670507780u, 342615858u, 60683203u, 2084538822u,
417237724u, 2900476740u, 490611202u, 2335306135u, 3861053900u,
894868909u, 2241567518u, 109806941u, 1561361784u, 1267909589u,
3504175937u, 2873638693u, 2322187772u, 918019581u, 90375045u,
1322819651u, 4275087498u, 4210332957u, 3544888221u, 1627085930u,
740314301u, 312214225u, 2148631325u, 3839821879u, 1647939052u,
4048129244u, 4267208914u, 1216066417u, 3131565549u, 875267714u,
515920142u, 402925233u, 2985339508u, 1088037711u, 2396879732u,
2985692501u, 594266515u, 1245163848u, 3795178832u, 4101911396u,
633610523u, 2036387890u, 1643319818u, 2737035221u, 4186394095u,
299255052u, 2124154322u, 2903433416u, 2427607473u, 3406501268u,
1153584787u, 3808804282u, 3574542198u, 3691414869u, 1247035742u,
1840699692u, 1894792930u, 1111698354u, 4163650221u, 878895484u,
4275109574u, 3605165959u, 2769656456u, 1792478603u, 653761709u,
2922494638u, 3535305080u, 1050649815u, 1969236932u, 3145103665u,
3434066363u, 2651068462u, 2685752418u, 710376912u, 1840537674u,
3316779381u, 1484595551u, 51421505u, 2391514678u, 667590861u,
17876313u, 3534564971u, 3837535426u, 1602866621u, 1174807010u,
1015036918u, 3927229866u, 803183846u, 3496648295u, 4082962459u,
918191827u, 183989530u, 17394283u, 2479064643u, 1243428848u,
1373442572u, 353721777u, 1830492352u, 183135121u, 1501139126u,
4013748963u, 3859067783u, 2918339539u, 3932596121u, 3504272451u,
4175022285u, 1267953507u, 1659009980u, 1433962594u, 1519724836u,
1659795277u, 3631005750u, 4207376111u, 1604931964u, 3717646468u,
569940483u, 3230062768u, 2708673706u, 773344531u, 2911040214u,
1867341976u, 863824450u, 3947365482u, 1273604501u, 1420223013u,
2630908838u, 337462969u, 2093655521u, 678151284u, 3709558257u,
2045368751u, 2930065301u, 3599726355u, 474927981u, 2317150878u,
3736594619u, 2753555624u, 195271580u, 94274512u, 1709600363u,
1794400717u, 885551916u, 2795594734u, 3607248528u, 1835059061u,
2747843334u, 2328234907u, 1001035435u, 1693652345u, 235805936u,
2638138829u, 547153028u, 3599697801u, 991695015u, 2877234179u,
3383722389u, 3059481083u, 2627013253u, 3567440638u, 498287328u,
3600036397u, 2959299970u, 2755364832u, 199929461u, 2562732425u,
3937982401u, 861395241u, 2412532711u, 3435590095u, 2920201743u,
3661847978u, 3022949305u, 3219949338u, 2562973337u, 3773797507u,
2145098192u, 935077289u, 3667892744u, 124435112u, 2733153171u,
2336633071u, 3049114028u, 296015014u, 2751679747u, 2396349832u,
1496705403u, 3603954500u, 518868682u, 2578755152u, 736840699u,
1805957349u, 666330774u, 608986249u, 2472363853u, 3800278416u,
40896582u, 1680781511u, 2082409749u, 2249181642u, 2210280556u,
357432911u, 2329972169u, 2886165767u, 2427904608u, 956912295u,
971928712u, 3095355668u, 2911246641u, 482262902u, 60312911u,
1312365275u, 2013765306u, 1783734131u, 2522610297u, 3690325440u,
2709933595u, 1909940033u, 1442425499u, 1704357789u, 899484502u,
2742977966u, 1497525367u, 1583123174u, 1318029612u, 2564838921u,
3763856450u, 2514174710u, 198316421u, 265990530u, 1768395667u,
2314710286u, 1683671620u, 221036278u, 571751506u, 2779207683u,
1555945911u, 423155030u, 2047935335u, 1434018760u, 787022731u,
3056004199u, 2284689631u, 4137760392u, 2701080567u, 1756642125u,
3912131294u, 1201533467u, 3956594108u, 3526202936u, 519557376u,
3159661834u, 3756697023u, 1583510448u, 1886607524u, 709938394u,
2280781434u, 1612256833u, 53104508u, 2131060933u, 281397192u,
1455261348u, 244810324u, 2671976612u, 2156407609u, 3899123681u,
2484549899u, 4017599516u, 3837959347u, 2804179735u, 3994219050u,
2424320044u, 3037372381u, 1925993718u, 332392405u, 1177246587u,
4177876254u, 2845483154u, 1390491309u, 2938496931u, 1463164366u,
707836749u, 2768827532u, 568741807u, 869407265u, 1280965775u,
1172620039u, 478972532u, 2987000536u, 3805122215u, 1468413102u,
543917782u, 3394277116u, 4044202117u, 1025405644u, 1707224750u,
1864686183u, 2240605571u, 1290357116u, 4101884836u, 1991992160u,
1996968929u, 3463552824u, 1219717543u, 502934926u, 3633464291u,
1725958720u, 870640282u, 41924200u, 2386735502u, 3737713709u,
2920533520u, 416930056u, 3319442073u, 3325200926u, 600730999u,
2558036132u, 3509898830u, 601814492u, 3250106394u, 768972570u,
1825868704u, 100617135u, 3218264529u, 1463864280u, 2589827818u,
2671592874u, 2112587743u, 1139666942u, 1054938100u, 3705456107u,
3529994423u, 2120736180u, 547125328u, 658109267u, 2980455600u,
636600577u, 2182547042u, 1783330846u, 2735761548u, 299718758u,
2517033811u, 3090526543u, 4228910553u, 1659076526u, 1860771466u,
2936600089u, 3509421045u, 2979075421u, 3031364810u, 3195690080u,
3566117579u, 1405740019u, 2816510332u, 3007319793u, 643248787u,
4020853943u, 171580820u, 300129979u, 3969161736u, 4289646346u,
3745142316u, 3090885346u, 584557670u, 634680948u, 3799101749u,
2430972807u, 2748166655u, 15868433u, 735399278u, 2677365711u,
3115162351u, 2206458278u, 1126454368u, 3266341386u, 1132674226u,
2751051383u, 553029961u, 2593118860u, 1053466729u, 3597461159u,
3933828494u, 663458002u, 2447294939u, 2927798739u, 492877382u,
4236233329u, 2763528638u, 195002750u, 986046518u, 639830937u,
1030191024u, 3193064705u, 1947250508u, 370040359u, 3154891784u,
1054651402u, 929718775u, 3784950826u, 4235202677u, 3848447182u,
1300324412u, 1614380154u, 793587525u, 1275759162u, 1938255782u,
3962698057u, 3322334872u, 4097609677u, 2040562167u, 3963663159u,
824929530u, 2196910585u, 3023064302u, 2785667685u, 27701234u,
3002859705u, 3296503982u, 317114949u, 1695591138u, 2139548806u,
965321175u, 3726861363u, 3331730566u, 1879689475u, 3480440163u,
1300921036u, 1949052871u, 3348542305u, 2126207026u, 2571967031u,
1969124223u, 1104069332u, 2844130133u, 2713773580u, 110283227u,
2481609072u, 581450358u, 1141429464u, 573767071u, 628702638u,
1226175933u, 1496995439u, 1105107520u, 3790323315u, 2629122303u,
1138385203u, 2081547238u, 4128122826u, 547119985u, 1760069398u,
341033734u, 2326900356u, 3647703883u, 3295713467u, 325211857u,
247163411u, 3534750987u, 1351316687u, 3425408611u, 1131435045u,
56237162u, 1182140676u, 2841516219u, 2036405666u, 3011909393u,
181354475u, 4099399022u, 2263280522u, 3301402229u, 171474648u,
671798090u, 1018093993u, 4168485423u, 1275944499u, 823679180u,
4200934132u, 1111934299u, 3199618087u, 3621066247u, 3422907952u,
1960186230u, 327155934u, 2648626799u, 3085590530u, 3118851840u,
3791862980u, 2023795762u, 9700208u, 2361138067u, 4268467660u,
3704256002u, 2875035367u, 2027303960u, 3457589647u, 885044336u,
2662844726u, 3072057497u, 4210718634u, 1713969286u, 1983796584u,
162684133u, 1680075615u, 1605451006u, 213476914u, 633139757u,
3749313632u, 1967155290u, 256432133u, 409228965u, 3211834734u,
2708956481u, 1130100839u, 2725640478u, 945525536u, 2527400967u,
835878402u, 3714026506u, 3349608339u, 3265722245u, 387938828u,
1661608822u, 1945317790u, 63762452u, 4267518590u, 2829827589u,
803587489u, 2011172466u, 3058409291u, 2493493652u, 2358944923u,
717080147u, 3264332285u, 4198730664u, 1575482429u, 318381561u,
665649665u, 4090251887u, 927143108u, 2862607660u, 1760435706u,
1877432652u, 1771873366u, 1874464602u, 1167059997u, 3020490408u,
1074066123u, 1379644398u, 126243592u, 3195614646u, 379454934u,
3916240656u, 2888173309u, 3691637364u, 3074570305u, 234168674u,
984718484u, 2323634090u, 2957625706u, 3571063313u, 3046748310u,
939117845u, 2447953439u, 3607149135u, 2109921668u, 1582617334u,
2947121532u, 2088820125u, 1311220491u, 1306760315u, 1526878608u,
3921204841u, 1464365659u, 4088339779u, 3839989510u, 2702193424u,
3033074280u, 3344899646u, 2784651874u, 1276498418u, 3085361132u,
3355531897u, 4084951190u, 1501726664u, 1175048372u, 404968257u,
1222303786u, 1754944111u, 2544068457u, 3514209187u, 2271843748u,
1475268510u, 3989245286u, 1371106318u, 129716112u, 3544402121u,
4044152139u, 2679423850u, 2290541585u, 3199575633u, 744603621u,
458754085u, 621232718u, 3523809203u, 3640321157u, 4159876693u,
3292542003u, 2614643405u, 2265268131u, 2175536109u, 2364640379u,
2464849350u, 788537884u, 947581145u, 1865279252u, 2550878652u,
287140567u, 3765319030u, 3181972603u, 1037202683u, 574960613u,
723287358u, 2264164901u, 1548449675u, 1992765225u, 1943406983u,
4007764606u, 2734816626u, 1133263828u, 4094045449u, 330380303u,
1351242405u, 2139587057u, 1170408100u, 2151621933u, 3076660584u,
577955961u, 2930728868u, 2191524223u, 990695029u, 3332539164u,
2415265923u, 402298882u, 4102255429u, 2991709119u, 2498622844u,
4105956877u, 183958547u, 653603897u, 1809232009u, 1453424169u,
1640850437u, 2483305045u, 3842897193u, 2820742683u, 675242394u,
234672814u, 1219775413u, 2856515609u, 488790066u, 2475713844u,
827998856u, 772322586u, 143954203u, 1728063401u, 2999097055u,
1258585961u, 139439149u, 3785937564u, 4250215304u, 1921492716u,
2854837455u, 3335291046u, 1117431624u, 1803714835u, 1365730596u,
176474541u, 1195819223u, 1905686043u, 2606575318u, 644255847u,
2626902930u, 1696029855u, 2469470787u, 3140744731u, 3124183743u,
681584615u, 3124853055u, 521289913u, 3037640139u, 694512606u,
4196362636u, 3221960124u, 1809151323u, 3104570936u, 3457186537u,
3230064790u, 949139600u, 2794693823u, 3605652340u, 2682195244u,
1972126161u, 1304624176u, 2917192451u, 3413390736u, 1272630300u,
1614264576u, 3114707895u, 2828194783u, 2737493590u, 1438642720u,
398059486u, 2046323248u, 3858845675u, 753870998u, 3263763629u,
3560607974u, 97620978u, 2751877635u, 1508838838u, 4235953225u,
889039423u, 2749896870u, 1058740777u, 186726216u, 1997325597u,
673398419u, 4054809100u, 3573007303u, 864341058u, 2870750111u,
1875827492u, 2133845783u, 1989074132u, 2286405673u, 1834455764u,
2866334629u, 2924929701u, 1437706889u, 3399134825u, 2989971535u,
360902372u, 1167328961u, 13923096u, 4046233402u, 4170341145u,
1168846931u, 4262408566u, 4159192264u, 1382737528u, 1362165181u,
134110655u, 1886221955u, 2952826762u, 3449176844u, 1662266626u,
1122229274u, 4041152892u, 3130892823u, 598378225u, 1217727498u,
1225176566u, 133190688u, 3323826221u, 547888910u, 1668299591u,
504078819u, 2524882623u, 2749626450u, 2984267770u, 1427332581u,
1374197092u, 2776391902u, 2950543940u, 3597584186u, 1694883952u,
3690380608u, 4219862249u, 3194989758u, 45833324u, 2290428961u,
1194523277u, 2080305090u, 727617120u, 1871861852u, 2852766462u,
1377621335u, 4205311198u, 639785910u, 283107621u, 2955818106u,
2342915166u, 553292194u, 1923106993u, 2037851645u, 2977117774u,
2451042230u, 2414973112u, 684116259u, 2194888935u, 1353049451u,
1794293340u, 2470657725u, 1586299181u, 2930169238u, 1014804130u,
2325649911u, 129021041u, 1332147710u, 1594434776u, 674914589u,
435079932u, 3519940708u, 2142186807u, 358685975u, 901678227u,
2225668560u, 1990950041u, 2073465681u, 3692487862u, 1345669515u,
4269341801u, 3287189638u, 557048773u, 975524480u, 1180641558u,
2197478024u, 100938323u, 2993700884u, 3977138677u, 392899815u,
1337314430u, 2115757123u, 1596565812u, 2447096231u, 1875036431u,
2756857064u, 4245104177u, 2570394607u, 1863785892u, 2677793010u,
1725064153u, 1458810935u, 1917847573u, 4193832098u, 643623708u,
3495798825u, 710289455u, 761817339u, 3299308563u, 671529304u,
230310926u, 1510576771u, 3374303917u, 1704698596u, 1640684325u,
822663837u, 2547915455u, 4069104144u, 2430564715u, 2053841090u,
986319080u, 2210107029u, 412064727u, 2783613259u, 279039381u,
499244831u, 99653989u, 2628011239u, 3746387564u, 1339491367u,
1544434309u, 582419827u, 399172998u, 2292817995u, 3518067082u,
1978161243u, 2134178320u, 50584408u, 1639288186u, 3729935645u,
3394981086u, 3970214462u, 2266863843u, 2098019031u, 3498932754u,
2425450669u, 3011644541u, 2154834295u, 1566569217u, 3550818423u,
3342256364u, 2855763981u, 3737540430u, 1191621881u, 3840446275u,
1890042079u, 672062740u, 2015167539u, 1224827706u, 163630564u,
1492072834u, 2802873157u, 1707472572u, 3763790259u, 1331259087u,
1950565242u, 3384631538u, 1117904786u, 856680687u, 4110420132u,
2624530728u, 3940769225u, 1495633832u, 3665314334u, 706218959u,
2446541599u, 3767005930u, 1761813284u, 793760371u, 3843098778u,
1378121808u, 2531610112u, 4281885086u, 722781736u, 3023014411u,
2799556405u, 2819357928u, 3141278046u, 2441527005u, 4151479894u,
1896941819u, 596201422u, 2064424897u, 2126371058u, 3296815812u,
4010070378u, 259579352u, 2113384079u, 1090898587u, 3505987476u,
678816428u, 1752720171u, 557092635u, 204016079u, 3300920851u,
2972890266u, 2447503403u, 3824050309u, 1206418589u, 40226916u,
1013674257u, 2994695015u, 2420661479u, 617755021u, 761607669u,
1276642071u, 1207975455u, 371458107u, 526906162u, 1617712095u,
583234254u, 3855581398u, 2661783995u, 3557719699u, 492761818u,
633313678u, 1392788289u, 2926435278u, 3269052534u, 2927639451u,
3355075155u, 4140349814u, 4017839768u, 273149017u, 4129597307u,
159613376u, 2525558019u, 2853612230u, 1277913653u, 2906920607u,
245739105u, 99670052u, 2124723003u, 1161668924u, 3249459940u,
4027543729u, 249730846u, 2654735532u, 1775757814u, 2799175066u,
994058658u, 3128508225u, 4060936510u, 1764669280u, 1591440959u,
3594681350u, 824721464u, 225498530u, 2961877671u, 2164367433u,
2227307590u, 3668888759u, 778727920u, 4021230187u, 1989921618u,
4074077089u, 1773124827u, 1248866715u, 1571786792u, 3651230686u,
1590808960u, 1798833201u, 3171851922u, 1907257896u, 422163767u,
771204939u, 1569344449u, 3620107018u, 312184228u, 2667690438u,
2736728328u, 3351679326u, 4293266120u, 1479297505u, 1321697177u,
1476450712u, 1821458355u, 510639697u, 3353685695u, 3223862600u,
1065307464u, 3396619366u, 2438080414u, 722925129u, 3029250790u,
3723401561u, 325572601u, 3630972120u, 385035816u, 2107583779u,
3204626616u, 100167064u, 3021789383u, 3958838301u, 863200373u,
1536140033u, 1653480108u, 3275112869u, 3452491352u, 830675654u,
1927345594u, 2721579912u, 3629599505u, 892928392u, 1071240868u,
251251858u, 196891116u, 3491476074u, 899382703u, 3890183726u,
3826018294u, 1017648853u, 920309298u, 3340661250u, 2612512342u,
2811793941u, 4174781029u, 3506353467u, 2033190700u, 3373457460u,
2339237219u, 1020418269u, 3590499880u, 3692832637u, 3566030303u,
1832595957u, 2775942935u, 58937028u, 226274185u, 2552664048u,
208605615u, 2633014230u, 3004371310u, 743686731u, 2417265339u,
3267972504u, 2486843234u, 1371501517u, 1968339331u, 3795872153u,
484975515u, 1740963751u, 890579912u, 399537152u, 3425765123u,
36545252u, 1700278613u, 2071323863u, 2207555149u, 3425290523u,
26019342u, 1529855572u, 2783751810u, 2802986929u, 3415140068u,
1064923916u, 3314992217u, 85471931u, 3509335678u, 3056191779u,
1825414916u, 1273785748u, 1884000304u, 2179774775u, 812453409u,
3224911175u, 3058589832u, 2859786012u, 2418387021u, 3114589689u,
2615992905u, 4042607554u, 970734203u, 3573160036u, 2692623241u,
1997039864u, 847852728u, 2229073638u, 74712714u, 1252676139u,
2628109988u, 2504938772u, 1379597940u, 2056368055u, 2089953286u,
1811579802u, 415412431u, 1439907673u, 1313375505u, 4204976878u,
1700729450u, 1039803553u, 2234612811u, 1824366910u, 2738413467u,
2205109633u, 1250436225u, 2132231554u, 3458837279u, 598753273u,
2368403394u, 4021049970u, 1394468059u, 1917980928u, 2513390407u,
2845111052u, 112183242u, 2065736285u, 3374680080u, 2630858879u,
2493197297u, 857666598u, 239366099u, 396468925u, 2165301993u,
2566000373u, 3177083531u, 1241714532u, 4138061872u, 2894145478u,
1129982759u, 1308535112u, 192836408u, 3902463321u, 21115860u,
2852921750u, 133647041u, 2764366837u, 1745066212u, 4175089945u,
626870811u, 1145341095u, 2949286171u, 875760879u, 1701610962u,
2050177321u, 3255313724u, 579430573u, 2941018813u, 1643825778u,
1448244108u, 1264534555u, 3064122081u, 1018367855u, 74340227u,
2032257813u, 3231709827u, 2162359926u, 3883904895u, 1769910445u,
2646114017u, 1568370967u, 3688753437u, 2727243902u, 2762786309u,
736986713u, 4164267736u, 2275640205u, 3502195760u, 2422971628u,
1314654948u, 231264130u, 2622060886u, 1428226261u, 1895991720u,
3901143259u, 21840777u, 1626372171u, 3100053354u, 1887939103u,
953797637u, 2090256210u, 1038111897u, 870472499u, 1782057015u,
881883769u, 2252280146u, 539294114u, 1255572216u, 2539098155u,
1593341126u, 3426128314u, 2067868398u, 3497890577u, 734480408u,
3561086192u, 2482993071u, 28230985u, 3952654161u, 2386376929u,
3187237308u, 1027326004u, 1322417976u, 674246931u, 2567828541u,
462810786u, 3906345343u, 2679088468u, 1635438811u, 917859212u,
397746780u, 2991343807u, 2242932293u, 3257743007u, 1536536942u,
2310652354u, 3858234926u, 1785883731u, 4148952914u, 542852434u,
405520301u, 1356469089u, 2662672540u, 2774250057u, 1100086288u,
3006372138u, 1239397222u, 1008026014u, 1943675912u, 1446208466u,
2821271137u, 2469856346u, 1735560439u, 306160955u, 1604643170u,
2628512252u, 1464887538u, 4040683764u, 1699601332u, 2569212800u,
3373761230u, 2970178404u, 394939247u, 1969326589u, 3641297762u,
3552329785u, 3494204604u, 2533477003u, 839404457u, 2837066589u,
1887770399u, 3963240603u, 1566589133u, 3277605804u, 3366293223u,
2503723792u, 2105674080u, 2170235408u, 4130642859u, 2899266769u,
1268252521u, 4054726046u, 1799410781u, 1691559077u, 2708694364u,
2508525360u, 4076845476u, 1933402539u, 106704659u, 3789369987u,
3771235034u, 520734008u, 2442493189u, 3815388346u, 2027438978u,
1095008152u, 590458232u, 98793519u, 1146786523u, 156665803u,
2792356386u, 2047668331u, 1210331595u, 2616724516u, 1009701537u,
697639289u, 1367514263u, 1077777630u, 3172655958u, 3111472002u,
3943877061u, 3567041390u, 1507343754u, 1349917753u, 2183327131u,
1308313591u, 1986589932u, 2085617066u, 4009147247u, 2968668381u,
3551135214u, 892982226u, 862813360u, 3985060019u, 1376926050u,
3024188003u, 949735999u, 2871900054u, 3171468848u, 576549665u,
2823667892u, 988046782u, 2391409204u, 1713668465u, 1020006796u,
2118242357u, 2201459024u, 1317303980u, 1749974557u, 632277769u,
3688223773u, 3145962284u, 262063403u, 2139143645u, 3099046811u,
2787373021u, 529996562u, 1510774569u, 1310986691u, 1510343925u,
1536308645u, 2630193557u, 1953926582u, 2246912376u, 3768067684u,
300316896u, 1802303731u, 1270975835u, 3884467171u, 497161489u,
2097346700u, 14945728u, 2290965917u, 3689541248u, 3254637316u,
3907317116u, 2862282616u, 4040733349u, 37537367u, 2387383048u,
395862630u, 2778708620u, 3411960647u, 2656086542u, 1787782087u,
4270883693u, 649699601u, 1274984918u, 3247080139u, 2726606914u,
101994024u, 2381680152u, 2496887912u, 1438931885u, 1972814463u,
3304990985u, 1411408562u, 3639691527u, 2127645603u, 1249273999u,
4042725697u, 3194015825u, 4004654193u, 564908550u, 2868688439u,
2039450632u, 1332535630u, 2602944856u, 1924842299u, 971814105u,
834403437u, 3193316525u, 1644914174u, 863939595u, 4014965922u,
3805794715u, 634057055u, 3608454301u, 3289222059u, 620808484u,
2329157819u, 1684810552u, 3258379622u, 1645866960u, 2399432486u,
3343530218u, 4263505887u, 722741832u, 3800010203u, 658988677u,
1484073050u, 3101531846u, 3874976772u, 4206597126u, 1848102857u,
3193138690u, 983512797u, 391404518u, 4027880681u, 1963064961u,
};
int main(int argc, char* argv[])
{
volatile double dummy_double;
volatile unsigned long
dummy_long;
volatile unsigned long long
dummy_longlong;
mt_prng rng;
static long timing_loops = TIMING_LOOPS;
/*
* 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.
*/
cout << "Validity test...";
rng.seed32(4357);
ofstream save("mtccsave");
save << rng << '\n';
save.close();
rng.seed32(1);
ifstream restore("mtccsave");
restore >> rng;
restore.close();
unlink("mtccsave");
for (unsigned long i = 0;
i < sizeof correct_values / sizeof correct_values[0];
i++)
{
unsigned long random_value = rng.lrand();
if (random_value != correct_values[i])
{
cerr << "Failure at value " << i << ": expected "
<< correct_values[i] << ", got " << random_value << '\n';
return 1;
}
}
cout << "passed.\n";
/*
* Timing tests.
*/
struct rusage then;
cout << timing_loops << " longs took ";
getrusage(RUSAGE_SELF, &then);
unsigned long random_value = 0;
for (long i = 0; i < timing_loops; i++)
random_value += rng.lrand();
report_timing(timing_loops, &then);
dummy_long = random_value;
unsigned long long longlong_value = 0;
cout << timing_loops << " long longs took ";
getrusage(RUSAGE_SELF, &then);
for (long i = 0; i < timing_loops; i++)
longlong_value += rng.llrand();
report_timing(timing_loops, &then);
dummy_longlong = longlong_value;
double double_value = 0.0;
cout << timing_loops << " fast doubles took ";
getrusage(RUSAGE_SELF, &then);
for (long i = 0; i < timing_loops; i++)
double_value += rng.drand();
report_timing(timing_loops, &then);
cout << timing_loops << " long doubles took ";
getrusage(RUSAGE_SELF, &then);
for (long i = 0; i < timing_loops; i++)
double_value += rng.ldrand();
report_timing(timing_loops, &then);
cout << timing_loops << " call doubles took ";
getrusage(RUSAGE_SELF, &then);
for (long i = 0; i < timing_loops; i++)
double_value += rng();
report_timing(timing_loops, &then);
dummy_double = double_value;
return 0;
}
static void report_timing(
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);
cout << setw(3) << diff << "." << setw(6) << setprecision(6) << microdiff;
cout << setw(0) << setprecision(0) << " seconds (" << (long)(loops / secs)
<< "/sec).\n";
}