-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathTestLP1.java
146 lines (128 loc) · 132 KB
/
TestLP1.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package rsn170330.lp1;
/* Test program for LP1.
Usage: There are 7 tests:
java -Xss512m -Xms2g TestLP1 0
java -Xss512m -Xms2g TestLP1 1
java -Xss512m -Xms2g TestLP1 2
java -Xss512m -Xms2g TestLP1 3
java -Xss512m -Xms2g TestLP1 4
java -Xss512m -Xms2g TestLP1 5
java -Xss512m -Xms2g TestLP1 6
*/
public class TestLP1 {
public static void main(String[] args) throws Exception {
int val = 1;
if (args.length > 0) {
val = Integer.parseInt(args[0]);
}
Timer timer = new Timer();
switch (val) {
case 1:
Num x = Num.evaluatePostfix(new String[] { "98765432109876543210987654321", "5432109876543210987654321",
"345678901234567890123456789012", "*", "+", "246801357924680135792468013579", "*",
"12345678910111213141516171819202122", "191817161514131211109876543210", "13579", "24680", "*", "-",
"*", "+", "7896543", "*", "157984320", "+" });
print("3659535532566681673026857047264590495633096120170316011130546064934049533282760410899967541", x);
print("1912991252611125159670459142926165956543555293", Num.squareRoot(x));
System.out.println("3659535532566681673026857047264590495633096120170316011130546064934049533282760410899967541 in base 1000:");
System.out.println("Expected output: ");
System.out.println("1000: [541, 967, 899, 410, 760, 282, 533, 49, 934, 64, 546, 130, 11, 316, 170, 120, 96, 633, 495, 590, 264, 47, 857, 26, 673, 681, 566, 532, 535, 659, 3]");
System.out.println("Program output: ");
x.convertBase(1000).printList();
System.out.println("The Number.toString(): " + x);
System.out.println();
System.out.println();
System.out.println("3659535532566681673026857047264590495633096120170316011130546064934049533282760410899967541 in base 87654321:");
System.out.println("Expected output: ");
System.out.println("87654321: [22061598, 62391617, 19111561, 28159858, 28355320, 18044843, 39952418, 23667669, 1841756, 82528285, 23042337, 1559]");
System.out.println("Program output: ");
x.convertBase(87654321).printList();
System.out.println("The Number.toString(): " + x);
System.out.println();
break;
case 2:
print("3659535532566681673026857047264590495633096120170316011130546064934049533282760410899967541",
Num.evaluateInfix(new String[] { "(", "(", "98765432109876543210987654321", "+", "5432109876543210987654321", "*",
"345678901234567890123456789012", ")", "*", "246801357924680135792468013579", "+", "12345678910111213141516171819202122",
"*", "(", "191817161514131211109876543210", "-", "13579", "*", "24680", ")", ")", "*", "7896543", "+", "157984320" }));
break;
case 3:
print("354224848179261915075", fibonacci(100));
break;
case 4:
print("2597406934...653428746875", fibonacci(100000));
// 2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777453778337299916214634050054669860390862750996639366409211890125271960172105060300350586894028558103675117658251368377438684936413457338834365158775425371912410500332195991330062204363035213756525421823998690848556374080179251761629391754963458558616300762819916081109836526352995440694284206571046044903805647136346033000520852277707554446794723709030979019014860432846819857961015951001850608264919234587313399150133919932363102301864172536477136266475080133982431231703431452964181790051187957316766834979901682011849907756686456845066287392485603914047605199550066288826345877189410680370091879365001733011710028310473947456256091444932821374855573864080579813028266640270354294412104919995803131876805899186513425175959911520563155337703996941035518275274919959802257507902037798103089922984996304496255814045517000250299764322193462165366210841876745428298261398234478366581588040819003307382939500082132009374715485131027220817305432264866949630987914714362925554252624043999615326979876807510646819068792118299167964409178271868561702918102212679267401362650499784968843680975254700131004574186406448299485872551744746695651879126916993244564817673322257149314967763345846623830333820239702436859478287641875788572910710133700300094229333597292779191409212804901545976262791057055248158884051779418192905216769576608748815567860128818354354292307397810154785701328438612728620176653953444993001980062953893698550072328665131718113588661353747268458543254898113717660519461693791688442534259478126310388952047956594380715301911253964847112638900713362856910155145342332944128435722099628674611942095166100230974070996553190050815866991144544264788287264284501725332048648319457892039984893823636745618220375097348566847433887249049337031633826571760729778891798913667325190623247118037280173921572390822769228077292456662750538337500692607721059361942126892030256744356537800831830637593334502350256972906515285327194367756015666039916404882563967693079290502951488693413799125174856667074717514938979038653338139534684837808612673755438382110844897653836848318258836339917310455850905663846202501463131183108742907729262215943020429159474030610183981685506695026197376150857176119947587572212987205312060791864980361596092339594104118635168854883911918517906151156275293615849000872150192226511785315089251027528045151238603792184692121533829287136924321527332714157478829590260157195485316444794546750285840236000238344790520345108033282013803880708980734832620122795263360677366987578332625485944906021917368867786241120562109836985019729017715780112040458649153935115783499546100636635745448508241888279067531359950519206222976015376529797308588164873117308237059828489404487403932053592935976454165560795472477862029969232956138971989467942218727360512336559521133108778758228879597580320459608479024506385194174312616377510459921102486879496341706862092908893068525234805692599833377510390101316617812305114571932706629167125446512151746802548190358351688971707570677865618800822034683632101813026232996027599403579997774046244952114531588370357904483293150007246173417355805567832153454341170020258560809166294198637401514569572272836921963229511187762530753402594781448204657460288485500062806934811398276016855584079542162057543557291510641537592939022884356120792643705560062367986544382464373946972471945996555795505838034825597839682776084731530251788951718630722761103630509360074262261717363058613291544024695432904616258691774630578507674937487992329181750163484068813465534370997589353607405172909412697657593295156818624747127636468836551757018353417274662607306510451195762866349922848678780591085118985653555434958761664016447588028633629704046289097067736256584300235314749461233912068632146637087844699210427541569410912246568571204717241133378489816764096924981633421176857150311671040068175303192115415611958042570658693127276213710697472226029655524611053715554532499750843275200199214301910505362996007042963297805103066650638786268157658772683745128976850796366371059380911225428835839194121154773759981301921650952140133306070987313732926518169226845063443954056729812031546392324981793780469103793422169495229100793029949237507299325063050942813902793084134473061411643355614764093104425918481363930542369378976520526456347648318272633371512112030629233889286487949209737847861884868260804647319539200840398308008803869049557419756219293922110825766397681361044490024720948340326796768837621396744075713887292863079821849314343879778088737958896840946143415927131757836511457828935581859902923534388888846587452130838137779443636119762839036894595760120316502279857901545344747352706972851454599861422902737291131463782045516225447535356773622793648545035710208644541208984235038908770223039849380214734809687433336225449150117411751570704561050895274000206380497967960402617818664481248547269630823473377245543390519841308769781276565916764229022948181763075710255793365008152286383634493138089971785087070863632205869018938377766063006066757732427272929247421295265000706646722730009956124191409138984675224955790729398495608750456694217771551107346630456603944136235888443676215273928597072287937355966723924613827468703217858459948257514745406436460997059316120596841560473234396652457231650317792833860590388360417691428732735703986803342604670071717363573091122981306903286137122597937096605775172964528263757434075792282180744352908669606854021718597891166333863858589736209114248432178645039479195424208191626088571069110433994801473013100869848866430721216762473119618190737820766582968280796079482259549036328266578006994856825300536436674822534603705134503603152154296943991866236857638062351209884448741138600171173647632126029961408561925599707566827866778732377419444462275399909291044697716476151118672327238679208133367306181944849396607123345271856520253643621964198782752978813060080313141817069314468221189275784978281094367751540710106350553798003842219045508482239386993296926659221112742698133062300073465628498093636693049446801628553712633412620378491919498600097200836727876650786886306933418995225768314390832484886340318940194161036979843833346608676709431643653538430912157815543512852077720858098902099586449602479491970687230765687109234380719509824814473157813780080639358418756655098501321882852840184981407690738507369535377711880388528935347600930338598691608289335421147722936561907276264603726027239320991187820407067412272258120766729040071924237930330972132364184093956102995971291799828290009539147382437802779051112030954582532888721146170133440385939654047806199333224547317803407340902512130217279595753863158148810392952475410943880555098382627633127606718126171022011356181800775400227516734144169216424973175621363128588281978005788832454534581522434937268133433997710512532081478345067139835038332901313945986481820272322043341930929011907832896569222878337497354301561722829115627329468814853281922100752373626827643152685735493223028018101449649009015529248638338885664893002250974343601200814365153625369199446709711126951966725780061891215440222487564601554632812091945824653557432047644212650790655208208337976071465127508320487165271577472325887275761128357592132553934446289433258105028633583669291828566894736223508250294964065798630809614341696830467595174355313224362664207197608459024263017473392225291248366316428006552870975051997504913009859468071013602336440164400179188610853230764991714372054467823597211760465153200163085336319351589645890681722372812310320271897917951272799656053694032111242846590994556380215461316106267521633805664394318881268199494005537068697621855231858921100963441012933535733918459668197539834284696822889460076352031688922002021931318369757556962061115774305826305535862015637891246031220672933992617378379625150999935403648731423208873977968908908369996292995391977217796533421249291978383751460062054967341662833487341011097770535898066498136011395571584328308713940582535274056081011503907941688079197212933148303072638678631411038443128215994936824342998188719768637604496342597524256886188688978980888315865076262604856465004322896856149255063968811404400429503894245872382233543101078691517328333604779262727765686076177705616874050257743749983775830143856135427273838589774133526949165483929721519554793578923866762502745370104660909382449626626935321303744538892479216161188889702077910448563199514826630802879549546453583866307344423753319712279158861707289652090149848305435983200771326653407290662016775706409690183771201306823245333477966660525325490873601961480378241566071271650383582257289215708209369510995890132859490724306183325755201208090007175022022949742801823445413711916298449914722254196594682221468260644961839254249670903104007581488857971672246322887016438403908463856731164308169537326790303114583680575021119639905615169154708510459700542098571797318015564741406172334145847111268547929892443001391468289103679179216978616582489007322033591376706527676521307143985302760988478056216994659655461379174985659739227379416726495377801992098355427866179123126699374730777730569324430166839333011554515542656864937492128687049121754245967831132969248492466744261999033972825674873460201150442228780466124320183016108232183908654771042398228531316559685688005226571474428823317539456543881928624432662503345388199590085105211383124491861802624432195540433985722841341254409411771722156867086291742124053110620522842986199273629406208834754853645128123279609097213953775360023076765694208219943034648783348544492713539450224591334374664937701655605763384697062918725745426505879414630176639760457474311081556747091652708748125267159913793240527304613693961169892589808311906322510777928562071999459487700611801002296132304588294558440952496611158342804908643860880796440557763691857743754025896855927252514563404385217825890599553954627451385454452916761042969267970893580056234501918571489030418495767400819359973218711957496357095967825171096264752068890806407651445893132870767454169607107931692704285168093413311046353506242209810363216771910420786162184213763938194625697286781413636389620123976910465418956806197323148414224550071617215851321302030684176087215892702098879108938081045903397276547326416916845445627600759561367103584575649094430692452532085003091068783157561519847567569191284784654692558665111557913461272425336083635131342183905177154511228464455136016013513228948543271504760839307556100908786096663870612278690274831819331606701484957163004705262228238406266818448788374548131994380387613830128859885264201992286188208499588640888521352501457615396482647451025902530743172956899636499615707551855837165935367125448515089362904567736630035562457374779100987992499146967224041481601289530944015488942613783140087804311431741858071826185149051138744831358439067228949408258286021650288927228387426432786168690381960530155894459451808735197246008221529343980828254126128257157209350985382800738560472910941184006084485235377833503306861977724501886364070344973366473100602018128792886991861824418453968994777259482169137133647470453172979809245844361129618997595696240971845564020511432589591844724920942930301651488713079802102379065536525154780298059407529440513145807551537794861635879901158192019808879694967187448224156836463534326160242632934761634458163890163805123894184523973421841496889262398489648642093409816681494771155177009562669029850101513537599801272501241971119871526593747484778935488777815192931171431167444773882941064615028751327709474504763922874890662989841540259350834035142035136168819248238998027706666916342133424312054507359388616687691188185776118135771332483965209882085982391298606386822804754362408956522921410859852037330544625953261340234864689275060526893755148403298542086991221052597005628576707702567695300978970046408920009852106980295419699802138053295798159478289934443245491565327845223840551240445208226435420656313310702940722371552770504263482073984454889589248861397657079145414427653584572951329719091947694411910966797474262675590953832039169673494261360032263077428684105040061351052194413778158095005714526846009810352109249040027958050736436961021241137739717164869525493114805040126568351268829598413983222676377804500626507241731757395219796890754825199329259649801627068665658030178877405615167159731927320479376247375505855052839660294566992522173600874081212014209071041937598571721431338017425141582491824710905084715977249417049320254165239323233258851588893337097136310892571531417761978326033750109026284066415801371359356529278088456305951770081443994114674291850360748852366654744869928083230516815711602911836374147958492100860528981469547750812338896943152861021202736747049903930417035171342126923486700566627506229058636911882228903170510305406882096970875545329369434063981297696478031825451642178347347716471058423238594580183052756213910186997604305844068665712346869679456044155742100039179758348979935882751881524675930878928159243492197545387668305684668420775409821781247053354523194797398953320175988640281058825557698004397120538312459428957377696001857497335249965013509368925958021863811725906506436882127156815751021712900765992750370228283963962915973251173418586721023497317765969454283625519371556009143680329311962842546628403142444370648432390374906410811300792848955767243481200090309888457270907750873638873299642555050473812528975962934822878917619920725138309388288292510416837622758204081918933603653875284116785703720989718832986921927816629675844580174911809119663048187434155067790863948831489241504300476704527971283482211522202837062857314244107823792513645086677566622804977211397140621664116324756784216612961477109018826094677377686406176721484293894976671380122788941309026553511096118347012565197540807095384060916863936906673786627209429434264260402902158317345003727462588992622049877121178405563348492490326003508569099382392777297498413565614830788262363322368380709822346012274241379036473451735925215754757160934270935192901723954921426490691115271523338109124042812102893738488167358953934508930697715522989199698903885883275409044300321986834003470271220020159699371690650330547577095398748580670024491045504890061727189168031394528036165633941571334637222550477547460756055024108764382121688848916940371258901948490685379722244562009483819491532724502276218589169507405794983759821006604481996519360110261576947176202571702048684914616894068404140833587562118319210838005632144562018941505945780025318747471911604840677997765414830622179069330853875129298983009580277554145435058768984944179136535891620098725222049055183554603706533183176716110738009786625247488691476077664470147193074476302411660335671765564874440577990531996271632972009109449249216456030618827772947750764777446452586328919159107444252320082918209518021083700353881330983215894608680127954224752071924134648334963915094813097541433244209299930751481077919002346128122330161799429930618800533414550633932139339646861616416955220216447995417243171165744471364197733204899365074767844149929548073025856442942381787641506492878361767978677158510784235702640213388018875601989234056868423215585628508645525258377010620532224244987990625263484010774322488172558602233302076399933854152015343847725442917895130637050320444917797752370871958277976799686113626532291118629631164685159934660693460557545956063155830033697634000276685151293843638886090828376141157732003527565158745906567025439437931104838571313294490604926582363108949535090082673154497226396648088618041573977888472892174618974189721700770009862449653759012727015227634510874906948012210684952063002519011655963580552429180205586904259685261047412834518466736938580027700252965356366721619883672428226933950325930390994583168665542234654857020875504617520521853721567282679903418135520602999895366470106557900532129541336924472492212436324523042895188461779122338069674233980694887270587503389228395095135209123109258159006960395156367736067109050566299603571876423247920752836160805597697778756476767210521222327184821484446631261487584226092608875764331731023263768864822594691211032367737558122133470556805958008310127481673962019583598023967414489867276845869819376783757167936723213081586191045995058970991064686919463448038574143829629547131372173669836184558144505748676124322451519943362182916191468026091121793001864788050061351603144350076189213441602488091741051232290357179205497927970924502479940842696158818442616163780044759478212240873204124421169199805572649118243661921835714762891425805771871743688000324113008704819373962295017143090098476927237498875938639942530595331607891618810863505982444578942799346514915952884869757488025823353571677864826828051140885429732788197765736966005727700162592404301688659946862983717270595809808730901820120931003430058796552694788049809205484305467611034654748067290674399763612592434637719995843862812391985470202414880076880818848087892391591369463293113276849329777201646641727587259122354784480813433328050087758855264686119576962172239308693795757165821852416204341972383989932734803429262340722338155102209101262949249742423271698842023297303260161790575673111235465890298298313115123607606773968998153812286999642014609852579793691246016346088762321286205634215901479188632194659637483482564291616278532948239313229440231043277288768139550213348266388687453259281587854503890991561949632478855035090289390973718988003999026132015872678637873095678109625311008054489418857983565902063680699643165033912029944327726770869305240718416592070096139286401966725750087012218149733133695809600369751764951350040285926249203398111014953227533621844500744331562434532484217986108346261345897591234839970751854223281677187215956827243245910829019886390369784542622566912542747056097567984857136623679023878478161201477982939080513150258174523773529510165296934562786122241150783587755373348372764439838082000667214740034466322776918936967612878983488942094688102308427036452854504966759697318836044496702853190637396916357980928865719935397723495486787180416401415281489443785036291071517805285857583987711145474240156416477194116391354935466755593592608849200546384685403028080936417250583653368093407225310820844723570226809826951426162451204040711501448747856199922814664565893938488028643822313849852328452360667045805113679663751039248163336173274547275775636810977344539275827560597425160705468689657794530521602315939865780974801515414987097778078705357058008472376892422189750312758527140173117621279898744958406199843913365680297721208751934988504499713914285158032324823021340630312586072624541637765234505522051086318285359658520708173392709566445011404055106579055037417780393351658360904543047721422281816832539613634982525215232257690920254216409657452618066051777901592902884240599998882753691957540116954696152270401280857579766154722192925655963991820948894642657512288766330302133746367449217449351637104725732980832812726468187759356584218383594702792013663907689741738962252575782663990809792647011407580367850599381887184560094695833270775126181282015391041773950918244137561999937819240362469558235924171478702779448443108751901807414110290370706052085162975798361754251041642244867577350756338018895379263183389855955956527857227926155524494739363665533904528656215464288343162282921123290451842212532888101415884061619939195042230059898349966569463580186816717074818823215848647734386780911564660755175385552224428524049468033692299989300783900020690121517740696428573930196910500988278523053797637940257968953295112436166778910585557213381789089945453947915927374958600268237844486872037243488834616856290097850532497036933361942439802882364323553808208003875741710969289725499878566253048867033095150518452126944989251596392079421452606508516052325614861938282489838000815085351564642761700832096483117944401971780149213345335903336672376719229722069970766055482452247416927774637522135201716231722137632445699154022395494158227418930589911746931773776518735850032318014432883916374243795854695691221774098948611515564046609565094538115520921863711518684562543275047870530006998423140180169421109105925493596116719457630962328831271268328501760321771680400249657674186927113215573270049935709942324416387089242427584407651215572676037924765341808984312676941110313165951429479377670698881249643421933287404390485538222160837088907598277390184204138197811025854537088586701450623578513960109987476052535450100439353062072439709976445146790993381448994644609780957731953604938734950026860564555693224229691815630293922487606470873431166384205442489628760213650246991893040112513103835085621908060270866604873585849001704200923929789193938125116798421788115209259130435572321635660895603514383883939018953166274355609970015699780289236362349895374653428746875
break;
case 5:
print("372764047...70016204514", logFibonacci(524287));
// 3727640477087217810300483049622606327914378468665807564626675120034372233462717080985039873199271949794205954639021269434029801876379530229498064912634351622100323910172807013534844835181777388312097756106414492636072630423470346056703563291269899679186634058472093693686760838330731921395845929346051398332612852560785759651212527473493997994194359834815651743192159129379131254748298219082030722667669724131403270910890277730375677818219712121851869204740085547771640811868259419767707510089321641444142996854213750198520401592754964036054542476285449925586109335740615631209545283656632117662413339989186198422306726369682453629123952701969275806375238859206480146862650082842493153603297786390269796251046071779852455929738902495695068623667636531569680007042702746846514041678833060321715551874036234760888040976120532852329059760648271060235301534246821092921372523458515826089759646566821356862487585228341976928362663996633158848122205192742700525900210518138286280827671027502277457649065351125592167891454296040203758738272181350113047922784524395943260143413745034270822519302606444068749213335707093676093681775559815885381104694873138997022650720946147018184642860215033086907797725430522922239349423582544205083166916184764055165574623780894071636636484162994693220684228033782482764477199383257733784134285961256660790876506335090470974847118082682876697444426027170898557088499411025827616205504712215153120229964786180257887122541854110096587060721821070245916293904811953097531820929988101017145375191193082310886405449941932978012012112924973435191024503687450734022702204941955474549151438304734185787751267833384761807865657584770151186956377690166454945144341261404917893675409330444514858059734071370497793083113482771902198354953970532592345996579378811438371222895797896858567228698079149309915201511744434064766335357896760236499074969010478449454116801896017572574407389844063127491566757361585955223832529537071532146604598615992333458687322304415008834456843923880063810726041573774214238640018166401950902412750452740862601979908180192255669252987820720906266140856107148533735643525900727279338065874047206935624385970115482201187315620997637976096331574596213910452610164434997620008623613742958060374558238902977172407486757443185486491690312244078364458059492928862417908761819384248172288202477853382973548198168464198147237481419383959875445049953984043371311457997550503326652643439145506113109198489974730370190136998481791529694254300895607753805447498034403701999492133171954455624014581312738372835539978614312565649601931317143698382955395324780222259543107719687555254218355760548402362887211541802147758643752854222337778914257606950324175953268067089693593089062154214512598757774633369119485490745696406162957620042617063145686050624770023192010711854958194484776263826477548305170460827844789240700191203993970604461413554886428087275206492099837997779841133591009999230823177479456063914309405151905018179887195888080627151185076308188513079109634476709799721148310353846133953334086386888248877778637773563539882017769313276049213359765879136836566905644435306138663738573783192348350238464628299210613148836629368582194671351795511258302523399500298712701567554880708082484106508450521207660334285928807671369022054748006393785598998987315594759897457592440654201350433934185275698730108650861071228646760158443982219210313001797007656097281392563026243823590327157316070410742093732790520388954049214567515588089102227755771945584340276611681502716347782049218519842716619326864025810139373641064021480802722856330717723691767981328879081123360621044046016132184424159425945705793031695715434563407847633411754850602878260899591484535910523062906127564217153884785675395558407292797487313248239186494418090631591363188276151287958971452958242638788722691767414590625896890459317256324847163758321785121408749655150224482856286899416728745973116045852530473589631542687758885012232445072498372599475865265339100851123081350979315980454655835529409047324513491617915332665117506444429011535352067610001027958988076920587235224750502753222871783846917007457974536051555788612674210931388780866480733444089670245122213175491971249355181475143440522763149232356289166964934071169210314034174826840150578787536349612660461320782742762574589259500725509320190629540791525252303531580833584685545468257574222963361898125532525715414539313244319486523865241923789202580536584441002310258588111780770062276168442337560111658217030893234745147974416065015021069900930556647222483900672598758777482640241072420965083069527696679439793488270487838039216468551073324311300791305805923692137705257630470735362104653665374480897478090970563600478341054958285144084822599544103825838731581297228281491395048932560672764778516966883454585854259429371503653632049044636264225705926383007085766216757743795613471420135458933281607877502900404448127073338623861135483097978145213934181371580177128567270684037671740105166235055066815261389424191045041088309445015009406961018895722837587847224995220908509990740541759211015673098049625740691444806621655256868606458067616050180686418571746510905116386716163729962912008151754141923095809188652060470572163509997411402123720007491350148058209159122416492512379375247928287875586555430154241365628705935625016271493437676169260323090570633401305052884365042484365904386128926698873442539222724517115722743979990790317711250981903133837765342286022904708455438788434059106177091285063068453974962711732395244267138273754693038060113656349506950745348636010876199204012103022266712218910651633534458881199971607909522106690269653968433725981856790418523183421187276466591014054510322536538631341138037130573702131631478155307149459010682325281999245456315895928638358548326225767485470452029822983033891776027268359878164452633125058810740892646838138728194945793294521539887228694992805722288478409483002982881257058395301583629205597425601671682733665858885714117862844957714658967964977129020868106626832381427385992787529931910962937313878942070235041918184120078829647340745783496655343262617493812879320316334633569912386161563877572398085400043381316538256723903036689821442463381700870587944667803858901975249735112387827823967814621140048078706206255826538660527642133692768843815044666367417280419919548825995392214415703556750071314226962276535998654924146492571993103508517429049349148583534241387835958254326456707605227726863755102599114926133291037174456281752491152893017651605977756188886292853785288130514793108209651402996168377223780987094708726476287219208040794417032714590079888077104849597764058565410810220947029614318954861300666952741589151114439397446602108962190940808906384696552958280854143236043643818419897271951429606857748906612098898065762642202678541643830837261109576134825974688765177073436733673256695908934276900956594369789205189195894517769605543231014339659976968652253943783887417601534180831562055271087803763742351262627091869375476929132756060717525040247441544417085805655813451883549096288671129747238103464228921767157918236240996152060290757527160999410489250351415117529682220192121124318701284472348124401295323398084278210041824689875103400624876405743349393563951808548649964381172502107982209385905608125182636783243936665898641422118944783272927833462600801592602700713998439130562752960166479150870484691853094015808475717850799719615720721662274978999889963971184287300529281829257386932633684096117677682928935805356278185660824553734447320732848738622357280706669465481847717852287913251774877929186869744336511688289715209134186941078440045112138638365740927241778210515188099740369304559456566220854399768525729393065019405293917828586721210547996555602214778617232443827410578457297304210616446664661157330828594847187811079832708585701027254193752449904680989496348356938286058751896977664556914375008898594519370445576528157046497638537467312833479123736108032363106756949435202185980928589865072136696633813217021989935816833506086332522768383147280611766481095389697673860804779835332245184111358420653111785752308483342132534631628473195932147388124061772365583803594252452710080382223173873675961194293666666135282965306087831012035144077544642530623402793697805176084961040390202120068840058605360898586113107109884820242951067021992734251487805644352580300986155181417150545499631380258171013089708846715584200029690188892660912719104175317154120605449549061514323048916421028747561692196308125552265029930792149416853129304847427273075060539223374220774365778797416285248684638939374458363388822092751420306513139362989543511905454166743511110607607789666854988681036407285713752726671126545887704802725693561636707092030395502550993799993097037959194051236032358685522690280843820507299004970782534724545143786379053821831015117366874854500232685970699776324803335010691703559441419740187154102213698751626042833618473158594368949023698436663746459228576904184425335879044427096370970429444610421996706925759774546031706504562141777458412392772528270171873002519032042015044273426215479812499313970790730276833722613646445359574482737870481713699865155061752069553647216909549089151787573977737876975148580480653416449894657182851096767788804815803434555940822174343922169536607937132319344280049879319335971694438947024332990146472984064266131033189581962051591368874823035181212325689441097024110786570060974815597042622471006101845227821402167893481542163955335008671971415060070371855813143054978858046434299137730905923945795144625910608922916210145007923070210678946290960490757276491908046041727498376405335022438217492469455085648355239352213272404808970221171919201472939547169731360215503784241183993760917491701187435629354503125387425777328183153039719448351868080002838601641169701028898674443841294990802378509206273533740174309727018165743152292686406613547444184359503003377567782412461401572779683936837300353002136642014868925060336758068956296744433740024811828348467756833182595892100117699183409812747964321085914157274322006632639437455119944835628945453788179542750126053446677672879913620574518895079789858274858638225231440036340999482735826863172834940408707330770482853064424038007628640129170344660635764540143046365535467760265565521640095954807590535647618389216118408173477525419545687627763468823827328916586395304995153123306610232402211298566151087041354392532044846666478454513777056518073629632571172322007203240818462587313798042034349227332527192228466392263605747333880361046094830002205931065644611494669371588833847837572340381216034925981340240576951702270009724745654873436325624183329391710854451979284586920171256941875697084307414921190604409485373405669377292153110364851224273986512315422886936882116143101836458233399965831702887706014596291006657630980974912754890032949833819914833564594738442797824500870792926998318597934321877408202063389733714333324909005692715052154414382958134159819248941828974895812790499899245257569494889096191157858042868950438866759891868241642661530428012392079350501832018354848746046304183241988427043407580529829978152617965708092701343879355332865036908665954174941550733431996235156997481012252780905980434930158666405501869861300227791757529102429682015227501780058350407513256863518386072616313734446398512914908882424829362864431187052578921013409615083953459388854737008407088890076496439098900401585411734705780950614427441483197153626183552009243979847388952532211644407169187547120938450240535644125828539911422562234377223358703442069344355148611421272314206442151761657629601897355817034844685388676494068301898597350969385495837865678975786289548326805570669081724728473378314447013987146067093646080558571039740840238801637891488518501903070617350865589081694457473666255825651614583206038043397231450306869271467411623932603165893377397963270909322444133331775553415046468004923690780177636185283650423351169619280264413731657969159218366093949600388556572858529257329455426222029896951971356567750145280431188679127021521130062717405597795946337235283778583359744534111167842414996153135343091469750785150974550197803395964202032199582398714805210300110471869668141599251898495719894956176791054578792082445267676330174624236143142399102864767127536252744429156440742422037113285350276674451593892963313660948886914403533170215128843031180391319240831221720958504029964981301037513191002727922780983057734908978360579277796227981544763957739264822658526582066369687646090070372425135227141593784158393651902011977139253705842437474232998757434772571365352284594794832365951671376789246216974539528993796640651428622363961451054680550258743565901126308368110536176659756778988961189021536978385477833695193558545402623959818580370554824185813647266344543347529531524074313478273036098561936795107723120691530299300886060498922230206952322928083063548194592347786425411618238661586897232489114142787079390999834566147027004302125441062575267280868060540545459962269873828508244046117227878065136475044080255574344078710775101536270044668069227219758381544229155546527456535877369918905344172128613752645279981845775090702487020417743355559638220450289974118345726913642074117984737334568348073051238239803015105821519274645808376270965183781957931204473630618727438898669638494879899705451412972595546835532840721090214858887985153400885471426309369845213404411687541575039995826719373807448915031697734676193585769220212824806922597519963790145948829989710835547194028741358117221150828274707298427324936498062438311053696533784758314285137515502408245909625813299236856729607287109019688017468376884972785595846495367081632194886372234606326389095597632517171240361765400778884134354970257689237921065673819958980957841323830386167838918482650863879860922429198111196131984829674260105147144994003693304951731794288773932621321533562401499727970162147060741604399081920398727869410891885428114765589163317255785098279040783247610924640149012424980923583939944022817953544987611113862613231111734203215113729520161231439150575937249997601570272847260106437382957015378029131414484838837605329010292802499291802691846192426299383449539143767733047367370843683692839171416454768803035041692939765513767194647159132323059703112334729899268130987829794434142949739385748849129443804913421444803867206286208178728270208539006167601997237074613416464116770011447255067795650659942386822623653359616278425440313765336351214424512408228916205162168415567240444330872212484582192155244932795697059868371344087038565668145458939652412093037211157257503382357330349402639084713452340194363880767409527266969134815190534758866159122189291871458128026946110811410491299658510365247633548944771295208523848694746323593541446102181705105779901094987207084799117349828879518111774759252403496293937730824927439645855092917735296975750638454063450525933414030962303798570644310546697358437057026575578540067162139307948395361829163479663593540133521742620609196849907761329695733489671815609648823125788642255381932204983396526907268226239332719397413494184941113579756897934542168170380455335943534358815442779422479219532930063257372791793114069361808850160473952573578716755543222828081952766237689615392283533827488771998920974979188350521583774010809897645080609479084725970110165371448257842049940129005668476558408825368452195241776555291865404116398581206701186108770995480454380813743471768084065786994416417715700194557916647285640596943680298369928639759915561669780101313978330496330136596777676308542420478692805889947552540242952489403953303868415423703928503137380375818690421684029414176453661330017635708203200569742808814216228505125657110685631491909826118568813782920311512429905125661517836083536685820991759401962108803447490301328457137425834105326432004601233271368953716393992003713630325539050851850110962980879562356896353698564431979600805525754970985375864709678315544073913232237466198087078101129595773204656172922146190151696972776864252028919529116096477222053682943671171060291229526834791582623393993155938278890999826533295263357252166086379234783582936300382800367490743635044411158295924513986847439868060706757973354295838658587076258750721303692430868419269133518657408818248598622616331222863038256514676844586627936809729979403789007218428297962748519623280361837567183314865769282041194248437621352257231663495296599273345016653273111256886904372713870584495435463384376944979542583081538289994996472448487412817654570473934149078095521785953797254152235882610801724162886248240234694202518553603116183026360670795288423374479132546372040882231758979588739489807457346404867234941278200237275529143004077914971587472179628428741766296566403156886627907137731184517857492015232744560551113676556827687191924837974804763644899820124219205862847327256588499498408889382701814364487266603209786254372125247204551574626008333054376446570350873297021794799189846865119033201101454230610668529751560753994839701066860886248441961817122543019936630041146883099437847812878449419634673999942274612789814110911713492997713801733252144467837603289790467570994399647299786215829110660973696040695230382602994067456125949004563076376219432365985070083303154096042920759430528460656564493839259144467636047362495859066023181941221223779345860982736328872197087515650107794818369659070629719539981614518006743540362699728558425646633447860890461493867250306978491297623884799441105375349214153433249971240622917699307221391471884773349234872851118589615830417274987386773021608498680314924569086795722975715592287051079437559060615027833753701581578090215507018017870875860947189173688376174098907036494243508970407259215540750676063133063337599463582752423622755651707048683473182977573305667853448396916414921050813517841708747620449670531347153277597243370025215588632405060582919387421864108357585956522637833097328843253627660130792273770621246579478175357002524279558412111749677128049827745446205966636108480169009862675450712563084171485587526361193174855681778500449740857450624541865602087053246633878640295833586030204744218463402044356683855817510732578641000550591770982123559803131606162470671488747859260178890108622032280082961576982617302910193386329685858304382797828169695215075268281681198218864170887005138310039745045141089909383037513831512202096525929452569141170233487640490229739112901211611022240691066561635895091578107656150676141730990604322502820392585320076899790149452077432609945262832341874101844887518494417509918892705992744180781381114930820340735926342195799043056107577156493417334415934795178257134708489410933276395497246390118047353532745130531070487446498276015825876293725589488288116165905404445704752322839042497949050702711071594298447648169337345985192062217189764998993198083311207372827576938720907558325796021688273518665482056001244414936216941077324475226045178745579259285838923147510008567246396653132321397207074660292142534558432901612469966565417460525124936742621939129455194789736220806637699339720579895151693951412474444773275889338366661971524849894224154735707781686983636994404613977889081154641873632273966298481675538236272753726374529603468600207341677445119420238767025033090205242835359354506366910502580760723157225077484322497140030950922893795931391624340294553931319513616300064902989578652032503360202743636555043094457847571090139791181457729331750087664437852363320243313990772366452145600737628105822756100648743767683865500169160769240829099019163754870467043281914519423753138946993043639096579273476813295828573707236544670377461229229010055535192044974572209740633348876294194633440961081513259152836862764928980366903872694989731794427145042921710889253337285825162561193063786404928285252865260843427743548724634535578333851097909754041438069922434096472369227297522123333073721426569741638868989267390317863989187824531544098562781390756457508159956898737460790272888338264588008102193139779348313410210736972425165632483598870681982917052712667463226962075818200718559152872534417230714802249023608938789202373655729642555589618019924658273210936788981582695574847239235211259521423742935728495744360978405932198494040785542757788517428551425645719309184208594900972695519429941876270516979185487014407418191727811905696314684704526922369928951908279855104859411032471783342574182380754867863370362352690573943704343456821546886510660019093569283025787247025257259058842068780432878895946463880454187182527163921825518941410327930837900005439585758799443220005030481377256265575754562024928959382921941629472498281717528831021872411225596493912666039419687927139414969868358292294428277923321301099119339927195473221343712893981757876310574570412042921463028075922807582535264045602331476705756384212724847734434656580851818775423940351439148328555377095218666351877930375774515432430364158914882641346502740385929945155401442371809308907494064377931233510077601215545201783510931068931391577525197917114273907030055212894838613867120480136635147001085649223274795446806854177013919911403587583662772639102442403757565961579588658060654163294746027172987595640645940835178522613864630626640386733091778615230058964380460309439898686754060183757335989261908979345373228129155482429243995399016719619679266653751630788061731090347862979874746067587418926592965771674509671520420290397142571244533035249008236587189309594599726019153595699902390889831796836120814353103494171619618749237731524939953563738553605216564700253790661338718078391160181405749990386445664951762584517063129694409714106821410593928255469137999693853346696799824113425997878508821672345713571691650356800959211228268548587346737360752313972810703183904318845656433634667749673971838793392200928078656376596324575278980786778331605806036268516819449503734904241210560512168381341790493788329458948657287424262474844608963587757920034400984085506135743586583244834334002326628693153883485163939249912226259840676155247860204172553581797959374374652470391467419717691857818755298465395790465084877014508374063911398529616174709823496846563112954527409982910924661913183316995183496927896118291330105813136864629363813184663867728667571889888597190534082235800779682425095187303629154216507206155580420487870773556831591457880673406578859304700732173123193062292283948422002120792459699472500109713054478207078223074645524048924064281551530516190727587923691602757130048355890648708782928721658196320584869028539538521134491941983505971938087587528072101218295358448420820564340228987140920766749204028277653811962334380366311902783967323812239357804918267371804060770571423072798554853556737468181531403893341568103676902018106304630763526502243531782610394277312273832760257960874647501003604677755082950617798686047900020966931549896170630681660942697256028753613746383474235246609958478883073549870309432429800185646167718528342567090455249343528432197677462943378536457149538151999514276431414306611021879580539020980695475095537423540363106871438911440965081067217432575189402137931550025736966078022541336476353385582002316439715220914694102044349792722968963208565786489174041417798625412495140971726132917551190730300229622642566202839991307982680430488008490067512935880925208017485406488346682742262854664779278837394311265494130003201094228100822349450194028313115921126274153975510662375733286924487522571794498101246673972554418257564723114269821644397369918285115632385203151682120011272996867308895500893748143376137476028188321526642218793888261420250034942669028577468986409657130667052592462219896519731451090836031555595020842989501976366185310473876489157882695241566867726366231058800215648497043310638775766020399597362448408122041488399877657519108242885313129157950153120130645133741102664110435628197861564827817967538618197581132897163794400686261627089431789647446373343105065513108783449622928600974872625509726753110846386641236614389152876286424353421996686097989001002688059343681437377264707397561004987926250213595245340101989271278126262460390332844147101089680378063452585204770618906145153043944254917397825753265463049935723864044967746397248052894910651511839613131730189912381747716478901119199886714816687105453962761070623002203253475130758662916470438137113229454044462231724427990632066385054419574975073519503889669676558121545453101659777191151063310424232617092159659286210532821464441259793608518291164230680045360594123230936371931771848798561120103549515739943850204902553124874844943502956517641206837327407165030159354715722496676176791785376405110748002810987368637535606170076937246355203657569034986240164704199799689257021996251434217077466941300024473656010199301331704063402101811871339787212443000654536697113024302210689557455283745575301564617840080333844282994251198243318722218640897011786240199811942060570123443890174572927732539030696489005936754597851263153052434196837982188530582320881648917345086883444764210598776131055950813193353019968624479659722228191623435779175523750771993575390956764109758710731351135833922902454215426979835112254741794596898142898118365528380193157372287694851440840505222358618916245767778516879821558123194020725254602966429936154245545150856668730725035280370847770977640482998910983761097404054750205859995212957347719387862861913340702021149974565521472908508532218457076445817518809995403299075723116408907498088789660348029469114766713724320716585845224695130173174959325694982209408140085138379681117354196922600813879502359085925872175255345238816095620042194255883408070310784573108907224126873633801937541273668342078932829214830295989836887170875882702241176859917548853406920624977086406333183291107186009413306997340905460194527318010776423271269946314689503537726251998835406183371641080783503867894557868819860513758077889859824401115476046527833623013541617856183950784023960424584149707936603928715367169848180460561665275668001479533755108605528947257378925219977750745073430773201850788323897070528501286057433545538264087108709332646475231607908401207728949710866714295924981615944692664065802509067619453679910691120631584545066636958446966138115682546622587628781023704809259319600702354661969028080175503443194871676189645924514201502701562585351313418020595407868702994239383394224686157420125860968355831535312630372003049027418372114858091593339781221054934716579193221531614117936784435534104366731838187145806218392487714209761416338340279773289578707426701695572065330084549756981664267872868775792266876173802809458867668469296856578078484814346389577647544389801652759801011858334758623364225373542923549432315825548843840561325427848080122446427315292838220198098324641924544158255972138766714372163431007465331129277000237956972340283351193637213889337913396385588261920732147041427368660856064283351609446203055189448838148723999701650017960286486344238259508804272582769873048949743264426691725874839811655437359065314571363989462548768232062858396152769349330063145055049903077922292329161632726610093607756696783892878637052770452904881783116038689517151439450246790974475753161610220318327270128069118427658852739553176437818323294991639795905357602642139038413057314911250734647720616619459950361546230444012756773367618639956972400644149674890318134310595235810854157728957596733366293836395136128658567340574270546822125699153296360853180678650576625789927760560846886690192185114476525929056503362873112593735714887293334926160522343593000400029947734925441122408757402676125789787841640478478936428190741701164075860717476545528941257495941902210540066410091757268995395271967522052121475981621829527807748335346560362625383742678112031806008581124325167063873723666855163200678350207438878929122140959170954109010141032173417469630745698756002647025245690107783237968139456009584324022761386684730191771538507314486270506037768139096824119056346832345848062181896155175454857241081545378783215949118093169596280367488342173674488131975094739796057128920077132935111771059078275759622961793864946481035385486225410398436990174177332912361780862779587303478366833439408186972991485643723694208784817242051628288007438262231053342797668951609942755897744489577041872291947465959863103142501143069350223400917912758336225402758106117486040075376362129643909105885232612818831191580755671984317797524729278772085912456563048168935878511506858779136409864686798316542493711488014106715905112617075941246475395155551146380198375931579724644598736430714292226175541818410562117319222047040562099880379382544570211774632389580364576298596180078710180445850980740636900298070366571050773863685685708165013992913206377788800568806223861628835100077928213188225409638458621835798930904281677224000066634604206876029372041781910873819991031534088556142139701389388404537196459732795204004098875715925145655814035353856787961220940708097693437215389192461854076986203585631955071611649450699760878268194590363837447641085689357861955451742224671634098546746299695278205162978066439336031279119487908582689908230362746106247979270389685196437479291308916142555364689916198698564914647729518481449151046018781057624239517032119729439577440228557900674932116634155660220504996801938944763750830528765330849000365706652753736197330684251301542784708641160401672813525481893300055687226231131567001528240453281538408832116710562834249453562249898033437199824067312344890086659663215916699017924239536676924079484418364225763139737266013140755298976780735188511194338649472081121733763117797414036440510361559193510980295882844858043633069362502307778010411729771507448601009187115179446057216992556521456209228026751060945409882433112580004202061884278629753146479769168001895880443781459507459991151842787696481629006195958464654005452023944501388050858956183911685740168566077921970793895892201948640500363242940730314604287636925103788816917849523410160388634209265478410846134584959894483131221117079785928743173282923632845988573592016469956304981039523646076302075707085623266685815664128945714659368073173295638660543737034689226903841275424928010984594181590496150956083699607380991369590883888062305190632213706903649887906130697028796505402071343941840807448985104639328976711367605333194908602344893498598367150743843422974643065843296685946046437818953001076699753568156745623610268153009234038010541981478241471750393559731554768990583776321480054415707706086410384480264948965717511721135585311247708161040719978469980813280565223204244230156597215035785592146618064752003582424404443213469983102145079054024470876795621700137417827993367421138027576848860053468250370146965311797445771188683534948736062809521602691372985634969134616121210936352166791080293360584457950502078185332326013479956146826813832943091714275588135183941181506428453087717518342016200970341747864626270210760173709377489599277009298332163945966483020452670626265496026849572211690926524922529382130487087767045194782490107751737417098715832302725674058484995863348107224540471608878222426050574136612740076690849258094148448387231958687221718482773436725818913754045461656607169162368192538224414390560050364990071330591036833245771053036124964638240740072763038826422115780469832418900958410933725891541422434260931662938022449676117589324010008030551125105862469099820205809614446225812380403525202452466976013207942985708822978873865518633160826688344563593433932949439473346624958875249286132834679687663239536041407764027602801125661988924671454561017273278533818958875343607561332443575162558169940215559361349906583247136649420197262225004153045274171424294138900509170809018499576457224288746966075372644966387388665155498659651198018330025928281056844638034086366315855363388327867382189715998518618710742272351596672776702981273840798027746570791757296926005488345872306414898061162791025412651260768443570076641204781081870901779494289519452459458574492964119984992593790203248944415627457719222637753957430891967713228106924004759304127357187369626131333829568047270277649301591994018327971712527657955002990247522727408311279321564731516817148531717147552924042541547585517477202534132086357703093906800739847120833821484576573429236834746200849100034733891798334791234893327583731355476774014284484917017150072836464586048874497889536648390775918770706490216840177055840475517241578960894540598286752059119392714995453620478000773235289438862112503187558658625017315906750897059030671861227890163934717957690388289242059799435625885670368003071586179786920996846658479931911830301293254884163640380688153222259872889052344080604791646248073152753100200608320787541377164402222687229502682505054253969609217995732312177990629714910353063236963916591853166155049088753265751285056007172997039490790996502587634059941757624836231527498521490130490342562101690893715624607415755744259053686273497857556409417762744130629951059705739870017525120164488102842583476180764552541879487323112656934106145398152350682157419323339700220269547126594650252361042598175420672208781483034802357245600773044908142539381933048990531092641207929474852123423346315707355309584263511039575604809630917795322933047571426729679536641729067260632546370115480834727197746081138920966020377118010844157447565278961059747407295363951241127082221251511818913007465186511310505951034258940620734466914338427810725434045329273506129634142365552216820121028956412161039297939916291739740211976035514800085641599937967828899415738166005367096872892767578080087717483346929549310666008804700868225264909035285975778186211913457454366329233042917852605244605319345108915271134386584968104781123721761883018599239464825074212082077925277000567097027676044249505269830859358682924073037630900578294096515579618414888431476981745280805207613863884876236666131239254649849820317268009494526016714847941335000084655920632786897520642625394453936745311115090310182264099311364858984623613629604108658066071708991503395135225001708826829027047301038222043000951528489236588365501078060931273273719454625632585679393726346574249304569528226645702553448363041548894903683689251747142184236032292059753473165861033287718819283947404847431225526781736573055343472775433772728989103664791561542634557530873600402943618829664563103004941138871743515889784627576343147397507190432120275319555587777465542000310804704106332914246800220223590512382539380164489979346616421730701784301793516911739623368275621994823334314325705946645851466239264675640306349659167083665362174272048160002690129475480256446463652978695078378367905763513474403977570027585061978389446562933069376735453079328739435147461332772755308467007682944081796022492268996925640054445133858935127209620196458561964486239905403591310202074471841475240829463996327924599158260151694187967298695564451843887177632891173477769293623874711139081797283584815605426621781029835873437400698961315857882344519995684218740330420483069232906097054102003871220660462969974546028237201536138716599911339323327873370372834824523157173768959476707098582077243472153068107635368866343250252977895948315105401233207508542979689293073807330046498413637597015643710516681509475066369728081574671815505476889268539362529712695755269699324194397483342620390078309327598214506496114466336141564674400015260193873819512582077368680243481188022620715871185694115158148387116750387286379813056117309770444726928036014046106994894716638906893175743211761864280947464715869029901203285359546152482765369507201700260024812760348671505185784782372828055604366663218655519591229182810820026969012995733249993511363934772440358461570138177369363443521126061925661354484957928317925588963740919451835098053730148669595933915187720788385288773189488081209879087227498036330430359045322850379426769462645293282131349138303155152172045219923219606178617617612644313111985699388423009982767857229789266035829918152835558878774481128648984750839632421126063843994724315008985226257085303742491225043661331682024586170899730244007603669659906638117548150628532975722543688913676995845092570256001391241033827921567851980571250572373561871812998885302756467957181813706510489564678471914684744252496478713597978710438127401840588118859227761909825455691596809042968723103836019886716950771564604208760236292919249964693045891377332514369377288898365992445821766923878969047150609892180519034518024303095987896474563195361743195259265074460622636636442849177963002499942699453680692636326057178783922848567695165321191097177362758965470471851776088180104911273178240877462953223247427706277429668024850952739218695012228187261572435963214494718427887300853838159821243709831128027171475639004634073139777393813854787929166802830793846039003908236565809119179380422050276470794408853211229943265740800446010219408714700796467798790414880070562439480307779315852800850823102904953286433532609382921270322638671648891731424618914928347205512916279771649784766356913841042839464781060517147773729195811464313096268623871972898024757557268095446054422817479168766270764363755843315893640180242157374275653521459034520352848909935495579792668418459140411672604447136832844563860526989072517923276465466744052927156667230016503525706872746662344476796633245601045243777181432565762120783535040106410432404124864373763857153853369268648949284659645562901616379068649109569716108752135886585581924840891791118044730127035105395991403390051825629428319211949516187654177051943186410557231362210104994438586149171481504556966560133974369540575194832101750419629320195065576129907505764343657776995357355375006162969255068916497578633371499658953488570057835068687591933539086635982249785725952001025636743204554345415472973041088103158698068316183655658865393268311397378490541803212669806377450738043720908931341795283222547449877309907107024005757312317979340039476382270422359906088598108428652099141707170913164868170365216572641202314939499044449293736766555072454234264024633758252049825085051787110142315556694779251459974288929628302493750551080780471340369997063743433591764294267131324284022401461886510226608485671869545981238480269348435378638775329203311381681899995532114747070261889036705906899630949086775685752843951786073110026257240068827297295224719155336987902709615317295891126505699728996484274068767212135548001382150718157496421079168252131940514888453093497278519685027219372111658051165619763879206048285206015558535032076306020607556954018176697254754344163829681133106387742913075139135517620172184232888692157492181599649758390650574243700678174862799670347278027410737434400493453420616429849308726007720381545047767781392134498666954948308633976515142343321023492446711872135425472762121432975736076087582952656278978268376788092195491149860393922362249868834309675857147634876558417341697693182842810566539216661217592833087941072749515662888231454377102410176717679277814429144252967247566664484097385527137350302458913161784767337234507025371553284470009429864184668109372370011029856793836844575266751460184023021546813324475499224907267719406783828139425544962581291772550790635185357659483711354913514117927557545390534388198395104211261320415765544138388348149061364049258357926246604856934107072217665655821468980922407234047324896973518237006761596930591900585624166678152884679876250383304978016915989161362316620399258988826938343582252873026844127005159338115957529950947006765879405836571206038442286161910195546799899948587016498388369426883836122569845934168492489612917857142911229784401442250554835091785138620444783278106482246703048990495036669861456260956973254393673416941322563526003593785443283333964970963065010489390782967194327786964905480819649566067234405755531736384197001025342411820353051676609572474393012480593791521303189119951363188765246311216964182784606179354824724186887609431112902786694587457224051718167033641084439405129226048788990143887102666164159361382504133630846501878890073310748131970531899837611170109256703010276505304361904916961978853043266592362529286912926655840724052271358574976622477633898307891683143051121378633705699241433873530942619744774115827160233177085288456639124026340006191866157161225212967454521431498165616799278969823868139286995053914509492240009134622055849101836755265328950313820814789229913079616317761311825530454906888490887524299154818449764500502142922516066411939827914779826539399712685660345118528489542669407020477760067927990596545643872412420956570333678871737559988669654244435046014695635756491322797151929889217062718095673064645505056928100561179053204263082995617648989534750049524701524914662608769462246037738234173795767912344090515860945203541499291245319052733414549876706495610437756727101011593280875666344926356234015944420477769499293337543237754518697402928583417930046279074307951298790571499223750117457435652275055720332777442179070834712049886370203808998815101798815611348893352117015514331682988401998401033331179670546242008872223078158279911199190153820149226900614899699741217569984587744056122556478203336223247198069161609973313420959066867066882384169177789465660417814958734564325700146328625935025361008470499575405680031601106881494096281511709691932645782927600713300812178635747524244821013750686267923826846409110189435342117452891927915271304532352428026337171424972838754506545019312529931334560189795409568287677705473308601825577123788255309202793664524126097435459192908083326440225318754787833939187143277485280852766288942953556583873423846755906025114957048325778386818385764653555833066876971486098321079477010822927327767388495382072654571309508390433696334853818702261624022009202363085658341987179209297250953742692189189478257347790132600873854758420171071605494126962607669428648110128412566431903879598653602841280693412242939270835084514649949290810832777005660103187636091718284266986874520490902006024246451558505778276476626534472940274750570624791180347621964328454957691383500844356117135790492983288863616817100502252606881813974554308097753009168892463878400162667548830778456199240176247550160337885391557907570914370440701959268911733258139882841670994952657470997658268828494601111015028065491246139595997100697080164540577423509960605610349750360829543263883074247531646920987331125512285136585114199431221026605414753719457905799395694143963306310876204261446142957447883104925153014675992022397510100435368981031545688329922578655074807923503117413101347539050097737025456222822690007365071756184400996639968552914127634170650405653881822898523020365107982674550837326453334784860553109108271242789664094735753537478937067551037627684316920728044474767967493576995979829210920524242063257262023497786517956180668986098178627755212795137014276863863845767759741843958581480869057795348861517838437726931558776217492436372545269737640741594407099252931628155810647138869083875114008518843193204686764105948231318583931051795068708133002032503812979470780904119123067164201300528583873885386496021909171451873555424304487851942502014861189254238127753907858371991223929002243784220017152739435639449749711650810145289666365874549923904284118376848368268419850369005294508692701023586129752839478837492467128378407616611085574737431622779544130025429841729478051822645362549685680797403306231697947803923793795018174425828395211668846935236982784918940531618453763482377346370448869290416304625464290640480799480712633748843305384129168975143399394712753162338937101048326523819959576281665608650125538018402233337628502779296957215049129440359465430348043336766385443547986763230757697009728865537329308393953727704484545204576873020969485925190111875743357792116025329642193748104045353708677965365207566594680555595506969969777196296626325912459743975278530763874396559643028763107559604981307621550143426535699564630739410525318595134383393324639963365178143918820686485439179476476683066210141619534617067802431570115828271862278861307163630989605904717994692805553532174745024143828997637783449782206994507692869318027641737973409284793302638773373775647101219716250339106757591393510098317901634900902242424219387102490432204539268033432878966100130432246149440077109692760577148628764547878128638584621358513466592480316104900246663261469497663122462373061136455959752694152801971498795666865201402347946037638221888202155741462234257351862273476499136544294699106924580864476828049060765402234922539957862532994630089408377073269816479074135007151945566382631569876589804196112798619111377539066298908554182508245667294302623087994619226986378906942095394838122720311610164566386409301719751190115735370098891391821745539298285795488545573263801077443533980769259136435352422074517520348594568292654446054326023214654509092152363846835066648328716236678105844146699467845909002034601188512652196027177419361801751488713340138856539684355041587926874974422162307664754063183112551513520579439317866036166372803281148486302246798320958336300997737882590647703130294010385862652685758831382464432432246570914215305628600084723165836397490023604833882654378495218290451313434879718918182786374003894376239129520203824389394818863339013814926661174585307988749945316758690877231879031858616067868009269541433665075328379003708885750097949100010886524855939466490390755950859060925354613776176834255208481210488428755216519248356486800579060880471900134285313587043154798172868870214041296756475819041115737585407905961631013856121495594145681677318272808802137067001030676413504844418565958954916906306085219646125563575528585558983454526943391998864031894763740984115481570149239243941851687865318927937596835601171602225193527788435916998485793020982440758927132005971662665217162583588367328961780316795397286039283872241989546953948917352226079879134956284650624770451968087514133813070391599818227273887926052071128395525914741262399751543094861779353891904419765012074225455378476460105338090712071024686376695722783638123063388056308048771912212424332672556972163828430513850331021783709404276616107551617185970030812235255872982301745929476116414776503798692941678307800189042738728427552015044449415067347067044571168171987394421090666460889998480611187193194012109877749557897522396903330763263548835706442327955264589964646204561562653250383047354098176363437941097146290637422554343697547057483821820172041898001560226069776449135546574357893420001465673354665640580167484534053629565686609979518555607470675243812878723761998941206197079252382814820627127406770932347249510005776685354987113068968866643410226229935635901826583154539513380876750552495524550691028798687706518534012242261859110873917639639262702849793161104151103586021514943643439399828445525866563210137292638520420037213470466312320866274547664538147723423289417608680652031812710273491105937063418127339606828379266609307479011810117386781282161307183762672183582101893721713235558940241654942938371774640396494318688837221369202093303964242235124418553833074674346224001273504388256240440254294956040319189815521015488119239685867130121977627809030794745959945795540809083448366676271857032024162114493669280857974546791025642041676332800685910199155446436323559225726260123814055932198335642678184011687750832949655750671233956300485719010292632435551800030497367830290344541502569331724633182508883393181788730044395269641457799134187130761293899718303376253272975647370322130415327280330100452742011490566884296662842502383539024525751465908625761831951367214971548853959781205850422388297065824359136909287458773476707760447699702010438873825795349334266046209951684234275384688021551062310482311672663380652507916583648294894647286135125880222458215470053197075003791048759604650780954506958852875691156431848663810254039100962627606314547316778752592887250062130166686194135804102331222015235996040802527397291234030747363763771290303217863969704207086545973022956975737791574344428177142305445295425326279166515678866937168221898442371118066319965397241973159589760296433009609538975813715451826853912743956390310866071111360120297108214284336741095778106938260435174645970821517549184000898024588794745127375703851517371435222802767339578730874810133705320283955557291111496646475788490718343758628539975592773543638449945817023011076655226435247797761133498361935094627460237525619089499835875291133296834326698417604109963822618787176316347161392316085632787963228118522730268758146492807312623340679893759788054554335823809584702000506420672562956931697794507047174587857112176285261007563680241969748754086824928531944973912317997776207085344947865559339870006705750483374377567167381591677320642584700272672452291991204636091721788172369483238835085628304905882976670618413361910517249963844691304079863876978228516543496205225116197414699974504305977694867657151898162691391475889441002060428217022881910047381832493167077144957430758679140627005244332039397779886748397656966927855117133349300492623892068923322385471767376531540239301403073149190355659159528326664872860619260813908079064849453353459523527510410015843215483289105520349508454193748773503038648901772235659019947204860102529235655521528984005767420618169383549386018032128851120924616194447932941182815870695711960511054026288221444197714362033544273489572886952643041969469513973119784913989843839770399695860463663445719449767879766939772408037144955720218286734264715442537270461139516550790667239742239029101575285259025514474934314397623765165709576405455892657921896041018921961108975637531835687478692805185118448148299444181764811143864427040598380710288441019788905286943644942161051345306991964574552193920233026778986699931805833119643177042943723604889048067403495780102764127073761027001601979969311944502537328663069857890636960199385927309381555897952997380867739815362669366241188393682047225038496881886899857882267157074759937466651368826046065425402462340730038206074819966350495384341752888931374005151304550414276908888171730290772275680137185030899803172796873719491842487425951312908022913523254723850157038156234104053087800737484968997639541261341404062307569903036493050427130613651287311666218988189014921810249332162987324741860338411938484556287638974982243148451803616376148812512890215428228557552672984177828899409273321505867335664467334127385383836763778297975937450876365495052446351451583251523869882137453866863703009942090243666651958179316722547195535422874220686894546963677090238788102834588048168159735726939262080702298875469675656136472392804428496376642107266329503622224086920588334899564029113510902395927186878205964463609238197213441976629039142251166808903300542650519961662572865863486129122889452514446015938312483450713639153888147911386950046420969859895653049269027405312568242886569867837711814955660388263789838371576698868070550868133220451741708521682732437525808553612357090174538026990408321193822425118693367294808706772299634660950254690129419441457367997569627704383693945612127537868586770246531603666684939036779358085303954811674011103696379415856240828081007373823435594302467581172191883089446645838975205760142846407963993358821436805460552694482263679800726962255425174914003446267126991320294417855106502839983816899588361706544183777980531182362103352897399888075541635233911358004187536052027267710065421508949015983481768923178162945920653312645302300727239320188642565253716062402158359205585253125319520796981240619960353042574056452185106247832163577000761039979737072338486837192153920150772780703710857113293140824706439696172713290928548692739311313105348787201677599659279895686068175720128998874803683712564351124416917694217936658514659492607749707266195533296851127430868968776727856689865519377776272970341768398564892923260319571639417081407160136250944321050289065387153890048942251503778938149042714846274356834106296408040778465757271112360089855160988664438377645403977081683045602954905017122809704850357600861698454844199723533356495990622381967427136427345171698728004839200774505828508629104115077693715541790327814407434439547623247248516291263071929238984372306200683429055441501038513295818030455027730532813991911727550753054283547650408326556998669327008256370842762683200406184484540626414488344775235125024237372736027724373392382825556437322529812555101534239115652094824148723902973961217180242628602221130741934559692776059238218155908433837420207778383791749288554498618251781453431858178498770644758180195535859591754727913077369059957623358304981876804338462613903083180144618552183303694666070984496530753193461803462696822634930853463491247378557980939904610908774021980761086900434175735529189860537515453574993009091069185266742098144709099924047428596178694115719592109242883207947006419726187994434000069278928912037477193327278292124342067072331727592565884634638778957818182274206058067180266151878196452917265286681443485478299882739172069638630576983813584005192175919858039449274825561063961686818481954189163267646208151064910343058470349517430653408319089148934425850454949442565754605871901522079688342674492642684531277144339057516057746769183840105379598600224508743561894781147659553396250042238149785647147683508445470073413651778112524692055716606482887495373751955182713372899329447129604019583437706254095153815193261403357922065313526724348494297389398666093537721413905371327118477929041617756595410596677169578173847840733591997961499134125459135763073920029288219604067220919318436789076711508844313777298021906839993077583911867005713697965748519382281601552349784227111261318990949787896535124628709662278567714465203625013293271023981269345901862487561403223014193744706471411947630731269774770742370262989935536196796820013004607306231045591973261000287743817939390500013700478604203525609038258222699612106327300804820358259441229493469606092529739198852482167621427213098602573943228719055172095087266389140672884169293243246832955336143457849516568892989091839278350440362713383605229868581120892600065788068396742013713833621714084840614497314898377625357886899689815482035125323241091691399747736087180028105375325214537113807320221404796849871174430254271610685056624578327620591821669954617691501109280972529189859917038516273655842522652621655947027474957642287699316134480216752855880341370015370302298796777750366813571412135084803233146779406712617863629394244712488098873963805087469027976385363326691589319088953576492647582581158990933401839380039752262394741041826438533638107214759357741167007866202138049043521398088516140731812236876965766192027575927725056536423102321202195702569049340033696601373959308858151126629515359825779752902802903870274488443608781228671053553939471038024858534664683362189054649161006035932392172920425768132979097302606184432349751517342405285814932277975586316845145353600327076754181316870864966907873490067672973064278731037366278129137963431399452639930472980775087111184484123183977179651391506654578700855967871533706617280309930097502648155837669698807169406280553850831576496429741681136970031051185661107131086903340799112825054395773387109234047660771078547272130618334998096469598440114180575273750768570291194224668159194657544737025570323750565939885709620766253965330909010841355390605889722089679816301429759348192509837952117678689604953013191046756636210715473608596067715546266770136954176945440599619555291731640583151682521377695530042126715626481618518455283311522627586162257261188951417152299696138837542413547383002992850313104932087397015984613669431248117761458730765409887417761829433451576155378907479750646420828352174135076993375597641701082428676699251218110662862880315650468782767096242887834977241008209010864620870533423076883295613228330907202378757372401991613369276983331214775266638183493293939655068749096736091601073739074760345851057570301234263314862582536973887917107727561474809233195592129159836036081094835508710889260096822169669497228428326555151494153950793882519939147657178047583034007092680711591743995079485897742748332057196397279828709159270001174518604317993573092434779402966418227932372955760687761159301677807513164507117175117998392563119670868663343511832279956306504326560314125286569069318108255720173270033694116342513469415241056162373137638671239669267315074644672414426527359556876947040857882212691467079476367068745797701594518134084213687806502768048645077880862546138471990539072750410245509456815457764279936919054371188682831249562970882104988012354910811142854540266397138956785835810166408988219042903917880352114222408964753063822426900513859518532597384081000039397419400378345282799824782529518828832312830104965555838934802854236364050113770698175499137696214331634612005121977159134148245425989471855163163336807736130715352354851124146998367437660017833396472614379171379209152440590355330954561008163219216485559325115814935966360139169770558661757136898833315048900204974270895212880856249462719019913994772105439333339403405034625887490998125490566932774856814561654593840352533413217959675475637451737821924823266722189874351255542372354414059810253768661137223189229255336889288591003559570700043947434848171860280916333692003885228250388500208352189685134935807560017878841711930022899831059452956668851384709376890826029592177598778523649746595110348798898420841418207941530161942181945241419847000971784125157452542125037962616246848631953784909940349805800099564956103450971165282235544395108206103038429242281809273003224386476334908857269189298225201650708299425364981437886601749705724362514143174233510625596513883690171517056662817781701508207757643085793411828689533823057093010379503482566425030750237527214714215756979163513930075301345510366334061732279497650211556487682409398154096103621532160230491225309550381284132137608270583857005147393569698028710721535579767931789547676337380340914109036516350989245672336699007927370263098982183188832050548481626648858530566083515237000139639986201740903356537549854801285681891378299458495189929801095645623670543213832479625775052271506626316223057663059992658096370641765965624554767274675147089993577169993421198678040824851561909529688660321966477330939790531121844420854430503201989055977535004460044735629325116451829665450792612318190780098263721628173516293683356178776092325593245727868434331824230485555583796164755353142345970511043089796109164152126542314466018347824747208846765292360323963451990152148442293353938257563375943705825436639042406622858385415563731234893805835009360549491835350658084151572723102752905633584927441225875028825644011060320869985784329247803773881458096247041553335676207433691278766134362044596441990614981217212074215068444482271616128290077128880847105127213064090989555607480625252473404625302505068969948298256031926812278434729114473208145353163648962152079264925253117518941515685024912736226364510075121389584374248969866660561508318135062825503639859584492022302142120643730610848905888598759012527195442310657923800806516896700276482757437697415290726206168543711695317193110096673822511982010691165628680912955695213157239457551799388479856962438660231986928601903111433861997562850685393556296902548732120260462817744886175695497886430760201333131600818922721967621574100679482176993389205368654039962004358621905353727283696080953005304064963376813084753921083488510372805567342254073328138974984477029290160986107918849698021364100617901905960115738491800366173408075161382907673615842204345023089226629619947206183344872098355344437994284074917680733306768504109825426876578840983940682998505572584401155365748405532163405545132880644160958487023410713725222647139030074118896968409838022621598035750319219157392609096132430241487497823728489336050590515791602296390112897832441257279885571754735081843033431838937118561543839679416320067802301636168010693028151042319460277655777636005583483108907680805093699658793976309415702230941208062789871408887140519556990531025098923642077192501872940191923028819972001485501125684744675007965367631373641122532874652484745955123418712734816800309473692562858902992754575124919318040690760596782459252251380134037013306665672006637902292249601839836281442461155487463193466960123597767101182542098264123381269762085418957653766256759856099733608835399638680763074407915774104727107188879799005737479345270542029237299830282861622727294854451453263133111690360424849044360569843230079846179155045370771804304346501475751357822338223306674043431848216790898829353461429998195820712149851262517749889817090173403670700400822729815325456189314792839814453124692623052569459170172919773281273063225677036288096260326226570592135353483238033770110054563126948542540426101973835364455404148246117656363106269841914686499448331799150626183927833393467697461156141638149222691192476805169537752854405300516183959128661166029883136655108657404453733412454106995760637626257394029180694739720018119683063901383675787724092001618619611297081553315312970888727813483210713742725865368005916541912060163309537032340683938080280209830058451214669156008053856735041801052111536138482165710001616645449359879628614948481115815424020705582110660605643162875030948714881687402226944022574150075798096027467654132081423630683516078690285714890407182231330256689045975704272097999037753657527313517239942458247926569267080701265984196035537531265105761298435928145676947522304645337686581801101172614751233850314992892142965142343629951451896865991695123136052278037072346883351911119959097949989433972505024623871677879590164104397823966556541225679285298651883167399293918023690497167153916631128507668296401312993205097852899186432652117535584860420780322998310045726020194438799371438877559013828716886385214841542058131795366647422675559899009188515451820477379093650022648763332489093199197784452894912996720655957503327868375049255218303509110717229521566138026322658812586874830116265433935338771493461948672234534697605561594686757857905267062362082376085790233361106805405532197348764285573232322926424706894770121685718560430853746909487771218562001704678174416419393302598961285134638188089848636346941976309770118433179372185456517406618110604739621062506169193530993141874897022268144756627956205170753985797347117214109103436361498777285744361466956390464182813479596722869867233669470049623801960266112132910790615947378664963603688050920738556734740900421654192041335216693590423584649832379355545095675706095365767061720555892793227387023828623037433843376300514726039284571889201047224795179902002909802294672923393585293889743556793731427771524229962632420602667368176192174703548324293359843704211249073481846778949530822370497468709544757931090704804024341663219263908066578778254099693947428647180012227788739503063087078817691474702345633250960240395565235610474909207451787906446871429844606217792539929894146710748364670395520690902810328375239995179151585492649526933903722022983699717481844202716750436745683368438899326148817972828311870215247428387727984556160995224943827945052785114613458043441088034015013529621431680788690961113456924980549407773207582908548278198956339140885209537161401097462998215395247920606771139933297745311802839939922314286425648761966756476344769765806813752860536579108899900992224010670961823545711982432998134689729719964948741942983376914362008915633604082085743080408592360040534391479459610243245004999887305937144473736617504192539225032147989873071952737141651771004831642515756242396724378341506263525941389776738855912534880789773749592623032990418995684461406838536289343195287104329241367471954546078328349873178196804048873990808784399346378895572645018778722618430125511495823108219260334680962265416433389977099506013521307287300923646312885023711258031580709622678905397515824556632577209194620805555208451739757423331136051161663397220127004154478388330599825413345019218024142928536464106297711253144931927988048853610919683134639694673565070657580549680048915381846696004016044574017599890409578220601765364431048842843101818304663238678369660359705117136751961115554925828236511185395149116081400069845542402566727463162388360768220509187284019376806784496953321710304586670913475486745064936518257512992480604682844594988599241147653940918687844986146149603325678645888354421995518608080700594410791468020614678452202350469686483597701698871940291386133124318721195934983691210232434711050055565705532676556259754704821647696394725230242656324252830803973979173757232780612203604191438638046129930911300840696588768201272682418962674159797887268109899379434189966822929505981485056962346628602136774618762123116906515241296471512299526892346494963487150844119645573270760415250779879228952065234454387641873500952732536899619282182321978226147628805377344198356274757039315242109105327231667349106842684637328253608402756897391094902435869355734799136969101467225658861721445830458501165251518276970380486404996056642404521612959617600446004473768915529485364767187670406024151372786014248445220276958031769099300315416082545136796012400094083863704282005494164665812606171128583432855303178405301398271667917391181172736260851870096378655324770049239919774003274313665290519877637692914503344826213860446835304591551498883963014234948067563645288239380117515219673468864070780444964569999805528810175286608148600294209106658390361870223113521187494683790924736620823906514732355606651897749764712036064894243852501990283345377169491452846438805070734769831489657489940943684869894952530802833528097486812370167855473870305166485595512705345699801381570271565127922149376177357700534988126104531757811083739356398241330369017592366235251589317312522683416937590625520784178956990839393547987102316981266405904084696618638314147217467551170957449743202387413986490110569766001505436359226237682712112220998139208792696779628167163648755578669128371094599107986527303265566836343309756900938962750979778391209037600498094794243605270275748468778297682858242975319879597637215366701316191659446226508630020959808774857016720279819310226265842632056434423484803634591616676989783940524553829392974874456482909795039224767080920241503370604089660496006863971400987187294390767448526578797085917673191978735410465782318267582462702702572799106351893224941116590036202813100801121239207860771695480906320585337358420249174516166477309027547390486562973900390583391279632582616986179881982388905658745850614890244133633202516822496780579732259831695178626153587357001730068906801065214447449091541212588581867874050968636619534813947967647873833942886488078400533403775069452631719908340987045201511459949812117687457785188244548074108029201899455798752851455251674061303699668880808949343687030864718180255391066637637080350663679121000139685390945483296890653073663543629589184325215425236512985125184653404742419583109709223181574644213628198329865332054631067054865261088752185196994522440674048725880952552687496505822812071187048605763254417649853923957484049820183698255965506408839841368726244711366106627939441319838042382575279819496014229816492775454612903564271881546226146464286773273815837800241550251875998127338193885195919055408871647347173748925481510630381456427428296373649534997291619049701853234809421415253821483297568466430121522558128685641880677001791842164593293334477556126254727842598436629489612123705851972006267306989406477362382021497929716601110932551472518505829187438154376595272034895592278178861600261995427112527813587985780215491701775436475009040346081101391226963063672020611871424521404338294781365806917752720479215901722676593795778705251861934513677690177588917047144956204017820475448156255530828283339826505840519657055719558095661072023131359316725142698619969431611317426450822106859659995423358447138560091574318246406502945392601427537952854120842919229818608627398163293866494311335820258872711750907303300872064621518319560892998312979372988587787300916759856361190711975542771694732852626278623626485306311302829792810018524794775997935704109198544227870594371799315781120303138533203024169101579432625247928174575632794887411038727780687782370312289736235707792260110198881635836448290690269298537049786299504089151280547956930215893087064384304783568281438975784384179963238246047004902496280606623464020369492485827105434758982262203246878483836664194305297244476967859400984995720041878684786743153321228332232446624920976276068005214455132328043216198682636066686660513865178559983508500301363174651963576161147948074702593730586334906894492811250622611044336618672211193328907367530584992075359604359484304453617136712389165942489203918549577423166128428455547580864838326956515282026601358358645699358883725413970255189976645760139034090087285991689250112245820944160862346915071007948353916656661660467424321567699535261104409712748466552974275520448553101325139557097186368148535858630592934220831895417239512722359494490457343241041281918000814757564162154645966546155621493292990091699574293936532733562198370105704875165543462599663998725682932549077274673799424424171639461989611314954814401759225576506694266898659218698755144662016702937953232551833770698749449240592248933336851979813319608226779390380937534558603017100772338834035880132991613300123221739269414910345167299937239117774694336433701458180784544567987209209488537196349870694007525908788315881395632276016154359298360635511363263367649843934921739879426621980249143660458771814434679539643088188465898880523322946856365033849765296522356079519115802161545262559982692104865778387696685676970422747820360469454089247725251435977888429644124044795294678324396017292701571856516761749106945824047417262873807851645024642024465605216954787213250962568798587874313112891943553299542017707782917498150019922112688666117028678807923391805818853961336232255639624713971931805896693244586516034850276945085779759660149603544216387216552154905493377470347312701027359369182498649718113592132508348886886196017062930735370912121516886371828733237485470637162708634553074301053508488830077569963298187418282168186493674473935204810769182683245064669223800992279753882517802081810041094089562723548489680308028964073321829162154677432261943358170896425390810801729263730611237894578940493454026200623302380218690696990333370180943378724374960021256581858891125452509308886246506360125695135494332624898863094506603772189495177416889595597098926649049268619484201486048415192785375976797810744277100806745348144095517209662703603761464984847263410115055627586075654180562550857980505649684638319304978500561915380657495227107988078671752014949179612878468012407548800718194724190786850678717245973023667885817001156408263689834960931978579923229994328150627664048494606466907591253442789634699238844276501309090893204005730019795166084450370743479842221969780787391263734406672587471848800393434538156311158199943619125509676813612045351780280345350555491291501266303481714306682583473692830709044946806382375270940760409757347879273846230501835211135463795072670816510626496600215023789220939488090305665258132167547128988751692356772372337902045935400749341774793451583494573854021763657384753043987874719930916561042358415946942973579804646284470379530153007166377244032928289898852454787742706721938617731348026618612123454854618756344862415228600716254107392556485156134919689185022345575133445185239313233826332694533519825203660499542211708542216641344768898485970812183691107846853735405084483924819690472707512801431415745927576405591677562409069661997754764531054811882750246841264304559735091840165573906261559017482401983542372233659592428606415206874397981759193214579070330708095440628986603888398085026825938037044716755411708280487414413341865383397310074696950668537671774720292526972756528940407296799793583085192559076674714645158266097417047144827593163741025349501235071659998316179558987225629293246811693963278918596697500539155252169595380659216350196565591458348642052311361186520348079311755525997917673638533012547485151783525782116796050013647842387108412333017248394754659225276071706342222040981300537625392835243839545112315471184390481306704531527784760298200959303320600361672065447997003779649098815217303710065811431690686118373901855012494153933566896515234710406867409840034918036152105146092083500391247657967548701266066417890065773856273634059396352415324975236151848062639909943358986650010790578608647564681468023895541129866528376760040484314066946654211364837812790551702719394047446936675221681861977132009009276695940904090301418243589414276530214056112928701292398791628604906498537041271532725562936260974306742895133499875003194782382467691184761270035867169078681212150822803796480895383293957594643290276884560197496548402762611288918587951672867813195690601118443049939830659177490593862471299076530926750289076738283613803723815616244601169235853416262212822551298024836195746248880635109915696991462780568152487231531524129457803017057273205831132490731796903800411456282216458382215085377666632816848275839343841515169280209412334858052527479143027722725093992932933917276709553706632418689063586424908555211348553372714858231272522006711371151182470104026116188542892383598859657716615294926265815992862348868631214556612068689788017299825922755549329463974045573130006571105561007013553968260537549312480431474086880467671677442344388222774727965588693804166774652845004976460370528400949637744435689919534873500412468056011242088863920642016761857620845289839434963842296563562186688160486043380362039559629662072300781923657858372954149598436695316703250415783746030129943909360175067110215541434568455238219196175211967061622800159374142470069943491630516916965494539516174642431779009755091927421438348535848195902340091702135363652852653059319842529975850059393171027633000954437757688035962476021349009241991086996960250526309974123440402835556837143956006990820527947368103011148718138072876662339285327271183605664575455774423791292703730371529275953809905117454976962200579192190497169843130863928372536461211710586929239386911060034052956873511589906362129260550666354683328745701404516761261155992547871802689133968305846925035888305209844359663837499521440556599903462916674984160462683891180244763572892483083027440385040719419411148594351474457055851894113853604832572632258671740134220406485059922928312745153303673609655294308789549130185743404915436314628728019583535330884818615528036365696948898422161771565737903048708577252484311769338471403082821717128836686237670957637380996782369438305207102078943687459159450343341054553661691811609476725828455149698788546901201109587584288229887420571400214230871198471716102158849706602525631847417801393039848384661032504037540275981723236267777244952740008520157437747550246397158971709204916742503638126541035093014492637323448389652764637755056791764341852604237905142025649515629696514820930657749534219638993094265346269037681732246959975519207597976685920116412788085191145542716205845264774020397364919652543973688012078290439301875657509929415449705662703920351698791584747667961647298898329941279039283901378482588003531086991401635939780481809495201914467269371145167613652214596486664426395081484190244734066238531325869019021019405972823717991658061365661229501024748166203910748170477213287210035630868531090198577912970001512983118747226101818139940715705013273716738533610708806095237203374963254781395209207946945893163329314442401495826009338656659448455699226653282020741885180330283716018965198715402179709606263515443691240096040280878688236093498640332938848017856873055225250484152949489592609067179989292896263656233137692199918695462486741581174990455724982618331221684513491132165933233768032827132286684224834791867641358257557966487005918979895274491222913836018376834889832868283340157380538298679641243454464644461603807462999610019893907436676539904695734725617203446274418268052133074285714351763730517624066014836458864114717951069583044931748835333903993323224577422545561178537791907416550546155902161734759839487018375711201369804786622248382423623957213160124139123799125075366318339060779189956506987514184422344703797850177738210515683726018887758507457076936546631691815229091433464699358890656511236718026699237315465657169257686332867774108846619789291723438157565871996161034832948122471632856050580700173196795621346140843149468495320419855301635474065287912319203660451353731188395857314964519287873235130858895583991090887687279406265096884474255017267095115608604572416401708444477904498718917852060637487235261466972398875887613865436884548143979670786355747125581999814827709631445422075832336559414938469751309429354667883130153643371478476496859356222160483582015324059012972687993205195451459280281237924864130953851411422031647279807694595071924220250067925490820164040986052098942828673513376449703989251108386480663802067990841079591654501633095894304383284790109547143919005356531717570219781825178542554825444783218161181350501384951739210640163419928610343109411202348136935315920597570597057268356167762251522887013693819357801397499994743359869536490318173613305278653263113332160858686463650233568603720375376727124576641241364835097103956301331809024021260983578917035122189190407235057850597862033496136420189506888163662616344485883897749293631771076923397518787402793547647031783250360138765806589556942980253013634803413064314332268037894660554875887688961400131701225160330567798127562587734366987417938500736388346173396722535217746027742030299403446446780089166945087061181601631214608784997304178591188308533305589033187011945761079053660953173874210337185112111255437406330761625512716378671499700237100145322407292417707529464110964605207276090797289561372595220516592197192605663868932452085253675932547069437421826744851191284616340065639559595957001439817235331257305258608487154913508882510869871685871473982615241207235881341114280508753580866328061477383957931786755821733515889609593598998333492809146797171450100021387847620994131480085785487019751274172142360398039743093780457770982572646184960702671288763373893223152171762420605214494440067487183130984929258735582928040574331840812988417953562314723681468913100768691011489364505805351262316448173333201834118365015598512407449654277688257671087354268711887323987152765396745789181756273202284147703604707200314112298943353905231616662604930801771867121632717340121759880778724020614238283832885467463531469837379676559828451258722908817457141690343103678544579954204862331810908373752553234344165528980809147256754062161477870414564865792862195239935659773832751357295854775404604914673004435000824544985590120154967698681508860628035600546065440837420566395740300968209575967284152644426865520689254962382982650612160929198809150190732159103040865272899929303414242765301978368294946352037485087027062932927172799345336242207336435297565026975003139878468124410326904008834599456779738565462837767634275354411177982414680736884239193411074702455995915168996359964539640279375598305399329032243534208684928011171105680483527889747140727709781279591339635374983581311446450601336404622293455625485913570823512756773529852610132630342253764987536983206864719145415526790122892941535482032273236689446413172749832886819994062705248649430749688114856639698796106182434772344713555482182436437571414163495483779014867448466213185468263793441716656102977200892744624411313137194481250716500340459223128984117355873445849080258181793540898987708963678523220301811976995839945562394085565054972191293769602609295382181648709783293613379109900089126859929916306095309007071814023014059947833049155267370851006876151653259698007112523136368864477808411074007387851571221098621039117332552359481945388171145081353306287140217426495675165443865080776281275450894777149829156847379990765694957866019711366950718558747690816641716931520969673788975746917311797453713069754359467554418883409920036500075416627460499514480308291301650006415540556479911570206611074849502065842668075322739457550267312628687361521322011874986639730835657057894250654317438610736305880156367915934880492597456069450193814513458388694324746697671652645234170245545061862635923223029392269934986835853332269771636628947661765422400672327030559390277777678947820604764751915067653314567718358331265681995106225133192384414644550444628368894712325367549993194154786515131616129030649358709923297782583231385794919688842918516255705356943424299294945100835697329454842531426353298599148066896331151798984002573545826591281954783533689100687933601678443788114265097852896087472478701310744650429400536836817620117126550380578796074975891022644035699953092834566550522455064919668426381931301825797420339002414079949648534248080522991714075314279484685933615457025715075701363221970154752958447489460714504997479954402848909451620826177900959893454369026227278264100227481194706138108623921122914920197568146969577916675862748665009285047710184389460705260643600079737804977569218021451721529298474717087939225323262678032457572723825354824454320826112141408298834895244451499676812482516022098493616335353022588401683515810125975277571669840826804783254075778645552270031063523811508514670799930522026259717383334179852946217331801684416312341024200170488996132867936057834722272883776044044649150215545976866978420021852665199518299001572296037085809943260819686352910387610862454141106765902842778967084945721313889295381368910359896849362565605496521523644048706461979045142555378437656658566568968678230771895126264280439751795314731827582131847320549692159191820026273542656341718453888623263188717723952208949111088306502831178519073535807012400021571406644119288096387029996596794778088443329627473933688508360009625992261305986275614873387665626190168024518542368016136348374023605815089288705253690776072793851877211668550045834890286112890239312219110450900105820863745381710266721478852906058015571367270180463978607299429185703215812809210817971591441156720139651565634331856107090759919967046893847760763833738344321022880627859521365416392984999916801825013231385802206924189491960389435576538243625374092784559197567039707224084259540946478464215349601451247369342849735471246631743326277108129862603181498045782903693068389435239011312955931568388478301771170878866078289960547789896765651931789757211313547660960207474899557876333047577866533422496285343671410565823933531635030884189151200837213825717258700710749953248208522537003579834262501446155270413547453590690101412268878372323775226179980022943035376527519393399981986173892466503602323060809369205715668049579173405006143209644127422260176283512363875975755539585484304238415063369602600760991139922653852056927311095880139272417274270615481560516942837768962256668983228167003771319685106860857823535811761508435981765180111503072286079218598775102235303580778412641365714928465871327604743109753235873336221999630699248339787869279804034337569356905445926224503479343412883756113199917185189491808488219805383323478719582828577805039423921476982263801915235942242525146363063527433662792451786642328644808359636439363080511660001779026873724804120661479689512267251726676319719163259858143389633286137787307738695522144354157069051256634362811580946985171220904705566439355643002442392213771420758281268448724028486375461576733059201715421769004450871703468947461232967042638810512505206592057739689811310513311826962750292195148635873462762197713107604361220205465686662478945074101608620817716783146703007242844520700928572556773781938061785427856080192440151018232490093029432222255295393768221557713669968292543990370286562062644002921301891261091721368770983388372213895406776914041997760073321040348838766987763833867007155053962518392218213706106443346522251884785017048557754277874694575110783771901245424304074962398908127280335779829320228027978345109131732337594034445748353754322432872747356462869112883851218931891183500331781958035796328787933985750615180858576581329315468794370785227097337889715999688919739011894540805376131858479910707129690732415507742815427582255871840953004742610019499235555058761200238010009160657735483446051682724245112774705283315954181398922395026621481144624938076377585800659225397969392787160856030755055513740481336187137815412388010675726313562349821733836447274926664681290487182553949139331381166527474974019489410698767596621852983526378023937066800212611880236680546987128327990687680033381861532442588507027533805778830566374716087150414445981926924503137856519033855849605488157627825471274965547815038105804985405107258168975202534834165119678386766315364003721073829947631629429933302056061754113826546727614738588262012780346062755401956815348234360121989919298977957648112936435573830398598478186587679859321891970169868849839288440506528890349499485361264901839379326074180787439812721292828140846817150863580695033781040442255803577436820018415919256761383522309608199096951970725167538715020500637445094608459520470545710778236029077599784478793694328581916858329182137112934879144334792467426668624330793937593840348269494929477751863680682515945134102789207955720542359258367615160757871585702501109161850761689997991262025253554000919017464525120479194919590790644781418933475106862066657947963391255500801307843749901262701318634958939412086499932291248602681428420120186585072980470148939155887467544757116139451165127220557338639725037490374630247613728545371716565844381910598387448666445041531490631367689809222986077316052637162746831788339950621191523531930203642371368404404039172317221005602794040897821439910920641117892416797000388255031030517386027847856071293464380189195354589503225005129854358451335292038443456144111012691619335942251472018983230633197225819715072968433728259076848688728285822385467779061954861694843948386191840244408501290586752403302265392567191823967838662453272379702754573217362910810120305567620234037975841654280875513219545335225141463139498570324017765229064687081874839436117548709316459091767514188529443709379497656373231561588585383377919719488912256749260141386877412978458507000718662578227340830204070040289987882832120986033281640027923025166672676115711442810206800043693329616748923209603802400477551424610648040057504535677345691388060710966716776428220016149293251022713480072124046684620535079090919580011805898063609471186816792283255829605977923465704411873039494088962410247624156889075367220980798991074067861797875627990929508997444808307630873948369841349238527589203450810770215445910778543171528950905694392852334535895686332836297530433556627002716878166311509279050251778749625594639776364528140346041750640889819304761202946225370882945550219618297977105306984461047696181513337394253039474141165072125526291126254408565731855859527136954854987469477943887613639092017295375253577082693946957619544254208291173136565755318068901607563958721017635718174336983095806106115324543062435709288862134568361991566469424571593257219640019513793164653414865452183474971042034079088501315688732581880505719969952832057073101657369860759871907813515694057406356825273428127612947611432607171600667500379946843992162977152790061739071159005650307203281465772537709662580900187906583050611940244006556764879430059481520689434883493634436161614936768305103870063298496872714969829209885646421099704316728821830606217278041926414026350427617670732183287285010425882299038989979333625733304139712356302520422771318547115879549094234806792088631049524081103227480015215862889494091118584143722983512178712811182742373999156494753023452301010865035654354750977435141266954917700083156891285682997007668503117125184015281511875457399609942608395838929387271292168466105081532602045138777938709169500015569004461017369484271208507626847754989792545352975122897881775015328739860701477773448532279374577351781892031988761986127358786811677284925138736568556164507209899701788729701381584190926442215210808045390969445856091825636550230402656578703813765277854250974456611369797929307851205757267849697172766389938940825307249747562720290086000422373787016052280293437270765988235986312496920397466207099550367887379805646087997163112865985583027131058999555536440196245780619598580054520447101981688604619816008762386039350665633850190915807318384382498369306918480496194492111400338226966267757975889478414215857700054439813670401657474137802122582926123406834506962665200855711507756990749103649861367799539394346903714805890892346870955614322703987959383790357636926851479184251866628554553921106709480277466546476579831915993715505174982669264463468450214008526505047520478073973529779515135720295930642019935260783263788627667109757588990237226286172226033798782827715050751690445898107799575432105126453116487380333851477238111037489899742458858534797471996647695089109901194042669182980286331442749191327893870569819370037273117640146801322415291242946041978882936226079743545429436349672651202427097833044124079959501171777510953182034435170571398639890861164921102354975603191622309273271620622030867034924361395722337448703337379468302586000783972812983019563753230607994415395235497044632009731291287205254454477537119243245333545034997017588203969905793808105840591403030621026225817880015064361162415468083230162748760176888445030259502835565671953623294619868499186340631491301762710007005111381004166812614132047022750209261996882398699060954926876353057580889241750678752309493282003656952487207489730373838142018621861115110867997185852321813719730887568578893725996654265066460654378023153894739045835079411113298584316665668014518800875147015480807903649565827993647943018996105623286827549444904633496963026227289360696214445918596422143016001621166688480367862614219930482500398272294384602772412112171201966371988721592673663853689228317467363424715782051694311034571109332911951229558697172386489987097150271047947898065236834408214632699556481612022465884736203494081237280041336264155278447540454347032098486635879951669322044221098348451065976924912771689925245918989583485551246895370798975516067618163474141443296542451921074561859172419004739488156319337259339158978766657342916287668743259125078115347043395288911485223776707204729688568004308434448416413776611269472079661102192815047398356670901976069512664944218278534196340044887995005292483021466534218576363572035802194059205492615443211698891308826506482773820952102323108945897907495605245867188184108981873562855990636680412206942216469535500373931863613032044018276267794536440245316860087897128374233245581330262531828516243722339653155165473109785855690992952334002379533380181005139384625264069698201032333124261000560434997387522587701056554597498944528304717280931293306975365469706573253658649130543149394897169266361563852022616933543436075722768794643025746314991006441536269876175592251946905724436824363474062456722985824716273957160521931893391278087565443597792305647554169804961185748393807778432531763796119446184752771742348790071971218916780219910480522676261561699157062837032747866336282183062963503813430750704092764031560142455991588090065442802920402830091410500057284426143700170599570389072834543951218882494112523833879958269003923992519258869115509739516028667707926731513153708282091646920275937235055547284237506015627225008153591092830474811126153496870655594854935302427400605169084701606121584716608712960806429484310766378198163910479308587305125039802493748175541650435064378040379040440252946458993290388971687167631537189624019742206677235776125293050070682188762850270018550079059719894634618602799956434703766923601307290376843261624863984547429929542156052699964266551359781115578256621797921224394233882903393538535248076584714010960665239383519503094468558864651566297783583361690552710679327952996493098647547110942309690869780643500219475245958980096959018733957086242519056094236631659584833706989966225736578993636196663192282189117027148949624229626565600356114168312052179105402071466240653365507004142237893337105703854811172249696318091103525938705754633348567260951523431726721019784973928709060042759770139661525869079971325442224539067064590803124109695187281333132981553482560752969472140781086717058707521864743865518141472322728400014826527775620115327277849830778855233133724001266019754853340463010567920130862647788495795307551767254347600168893567109186485611308630119617807948911088195195610690190351837684009350406946543182111840520564606558386436511370438077035081137832037001283312139421416821866818172209321619773080275560392015822051508809109250347900434912164219515739608640929071329310974848772235275533969518890107652693074105929731194471255633202221601821502525927312347276601328888031211692393647592270302869787560221230548986619496489988606297242998519386400341210794165641950135292835214585916641799272445693117101124218114758312477633534124462403516053055711295820162459848495403186728674376565273906800265862723679646145051949665164602457358747115750208378624939875018620781588935000533756529007368257626336696631674553550971601136175216141825441327143234060728476764875825019752308950424733519134209340349858833247864148634733791028883803301576107194281898979435390409301560825765740726847082850472805119990200993139861090946365235303081123491108050228795923751262540658593196306775774021628169074131187612490434533046499944651978653121688261997838156199170413919454705955056330899702240200714653628120191946492598448601788927263545640573861709098494004253736005547156156823504013604809514032734559480899242131372077452643566798459858579547756469905751481744727360089958851839296882053235625459426525079466284964301225429666543942482223425948952828467811416624008989435856097967113496490876466953755091109516959989100411597495079924283798274768158742591543405398187353722844223450886296303391099895792276402172048652816797143581010150480338913635329571284674859383992564449666494740257879096021787010094098251072828194372504860898041400085145512015881478941768566928330100344241857980303170821491164924263765532788269734508811623050290183570437531415324735330526352313249529760017789901585222555457869558594402955377247198452172406725564993100742352847230902818797453445184542460142351603193916582436303991615778637569386901310766999340444563072334611518838100365610093874270679997593712424336286341181435207697230112781179792638895152022917367665727686139829246934819194874649018172481565033708483272592702973602317779171347340493285051976029037630747686115419428162032830226834280279784849927118941502658699770998250406337940052504139333006337942305517943309027611553227293614287078139385791360974396095719883734829666234164234309765283162821414081651760472017877206388299001002535800436034045830764473001208235662002062566024668987315778565785594726145808660298344804541102635618096439446628222022986482962562559176826835849735709256623474973889247872633427980482845930628856346841502645810605201189439879300224354215760899460744350915148064617784300961328387610906548222605258430402117804823204351511227938421852237008509770333547497507019076165972736558475120886095982438154933006928202391367594043979891388443738933133423077797524664184295000538691823342161096946833250199055166462484383482343964895317452467033460390821635512024336095426134945708927931132534934878448680092801004644262816583339041397402934998945128910728438219492068795918570937190950302533774281226333416461380418486893240999446639559331115476955072087732831663012884647680682132049315227862507230517252041381179837877589176310102286153219489110935142642260765154236028504931215081461194940628679789187514667488251813354384264867553152551828489217731641984764930640377542752520313253695248744152615403089566563662537856556072398924008255778322960595490620125162197814860218054673493658563070260166896740964655160924276304499274835123444431915420036093516067853157617221998923052000302073054280696889936750183779961176637806277376823503052543907126226933093083114591136582258156817369014704971609521766057786755620441987444995648430737335103523521324894741191740875659389425538216986252907198093099782630943451986300784455386913649009964913530869440567444575720604316865669876185303470115510340599851284028294815186609264327016108395551136440087282389707646407591739562008704526864379944082768250548080779285608203510043772523896427599936440103555779487900139276712293609257212423582417416028206120343013093876711812012121540389564496339018838666228340371692497019942059929663797575608611129462007148717415518476077088271336454194727958307951588548787463696242755772297371752990556114534394583804619779431773470960088204830682918134229473421983312104321340745028168838676609631624317893163173189972621693983950141462522829238097854549382335665435100596907428124015315656268670240967671850359749609619555194876677357585803930416253132065580944370354654967323100230898031860790410296262729768557577625789008024301643436613184657775650222584111642808674974897745911911144857117133628025280222042400885334906079200915370193425319289788633747365920317186519301578165811070852556145676933445102026019997395089303785066018221995139037074544702760082229102346357338693437707058230602237880194820345016552613115514085191197771204409737357146043372782114624824093860529856751498872352899131803698118996286926638324375576360439953436722373924917535572810425753752498517943660397123865903790538852843932454215754051215923788869224110844970485697535781024331255071846845912726116406970281161253062731526611748703522352790276648287528154980936851823973199135671217266813467478197010139194999676304753009228685242040161008315141557161183469553921947675039743621539012213543930818894753451703523436893622007783171391226865716668441034074589047887814414142794319307496525252418474151335293737840977868156164900921017823974053390897611644620843421556281535264653033974959715544366248765465547946744770570731730575689132134143122957088995384631308975791736814929046492246012965338685809896177264545711955154810238511438491507724680735961292309272026458552937998125040786176744695562380773115568841585370393183545821553554886028172348766957070845465453096604894973360238457785462959152900695963281692232615288478955397767492817974373817460270208249082006604080758687690112424067494784187541967088127163311376234469270111279958747420477804560192219874097229984211248704481570193427671870498374491320499107692671396394722775450080711289253761252923392917781716440508658983977667624315263817835019982532981287138448394185200535613762617613920183870841380722921021396155302398271695889629657709447610192538969622818841817788556373789494138733740920487854939473154420954321946753231506509246006017768252488429051308317462366789588354288445741868125043033437260953362979305586681070868596217261259442147773392758262815951722716229150684636285155459931103071189760968943100886092482079098801190575879678144945788508311739379743781611630462566981327345734810290926171948198970907450371568039890551578820434658407600025312732938811995077911030493186659332461624962648392515611835516921968159032578449962616889352328677028440526976763274309698662109394079070528478977148112596066181601272532572599337446370671805645008691663457979057360368154608288940161838330203744959920990013676188228782170791357438276737631146424846722653133349842446764987674796538047290791400677311526241093714340325307090741928144061302152113177150354478355439967749220929506268779984272415031945990332126200187528709641885169129575476875630550173124701800287779297660728850307499548109622114766104661660347524046303730830994699203871016357226314390797533989101927218860604452300748619444788855416756260290285520869842384413500165776539111258618028558350391020014612820567389925094277986312084016411901403597319643752241604631261448934281671825556392674577716105297934939403617041022195618988917667106464891489947479097044521054156565811043048047876627466471598443078733405034681639940703551080671715302639285955934505978920956942187249113421541201891515051994807659847710498426816542239883077658920580415302936812841436326740423074934045760336523513465374725202283768401632347952184438905678268100285163241121373350371273714419711557739949967326551465994679468998240094178642524360319998594340485589217747500015929372471868111895485092999166507384753081460520842787995257055361664848489061794709603099622733087647261770646028842960425732693917031478679933519694446183339474228052738001150254739211621193972112885643787907612688270021187087409482261961240299972202891181770911800070698209248789362598918865890021357132301593704317412136066844219954385676815658868986837788384296172428756036706656977209458780165024653353641440136317533273914031983581314216014970416651475656403952596847631809478542392889947250801872530502487806426180985456209456353946755172464219900181238604567992378125516452465148502894614373236900559723753451141891358573379258057095484390983351489069588671290458021370608597920156930603575567227206886807535793616626871534687637547515425225269278651869653359728939870031899350674047873691963354625671632546055077948296629034352861572400095733219784865458748109597948221430914048379901422945917138776078782608742181825975617621948798469206855927902237532688684197853844679520508024413398255301159985700342031752191709206535792468672134255895734463429778942250325002555429171023081739970054171196612886742110423297108944751560903944994467886076779282310074865091723093870820670529269086189195453487491082336649655190473716948548915197909007558780741057713087957384523434355071242978372537600883098480102107716650134875634858067741860352976321960110984874664737416920398845866877419888837030185535980698319014778260616652348308799941467031962462064182955565639117534271188434765272240098206994457801806573157885117098326161291634293206334870280049035594189072578235045660206902986839045062177567290684187740116726431859002950193816272407377952152004141267470988350355777829317580495052698324230480840242863822216092850001376207319981933472065815647066707610953979858450755683279606734287456134314138737385423273729417581449281827685559731137970804795387092858707908067587620416903976442682979057017647818785498274196325258801310166800437757894736516294107784703336906909693680477407268654638047571932972849705251196031078653975692058938889406646711136280077650595691553684600474335037165499180878558552715166113836059664242401654580515789861510907146242445005698604271106644334856636074616321617697474077834826936823511986210922965987770196845755239421165739804029756607403940664342719523037025036897187768924267465989813796965501029955787954996887224214168547179675008622627185497438750329300326925467068735344732063633681417783625475294406737703520994655238860977113177618497612406223320830314361339147656504473810583968703788318416929791661575996348427374520243574157879378517238475064199856691907587634009398256746824260504542242631013884362370919571207484233535296153840049732854460726972117723759876377266183708506501911505640687289143796748164718969708764312552887615030346347032916757801962079717808923160492724489515790279466458246353364101208503467753399466580853544242342646678465017726896599622361669409929681333210294505611326317847128361071346847757507662020235267713254434753140870629150316981093347995405341285625393216778036332267090516905993364573785814606387061970689019400680803817809940063232322044949949682924837201498454124208444517972902000412668247143478703767370810634053947746936563193878615658825353631315407932502190939022601742202112598458031932991887164294015671539004990610056935696283633786297541643973109517778233328126186936460756922505951300173063826006071634014142421599040388173213893315152409430481371695312799477030296154764258073487070390675390196200829149280703220227546673920950018595073633313287703825130662287202951035984934211024680376254413411235831329390089964512309557958198373829889667765877999098650794808447328436999931264314537004871397765664282517118379708249416011868170256246426443013754932838138125664106882387403158895003489763945228316807828723149269620379161273540105426852384686928747873596741397820918509579929358727699097156002725675143635779546574305987858587401301664922202495797557305036529411603545721606674909823207046139416128223559882336620649451887860670947884221792523730015610419233467134667736027420057326345379402770069243808458151310947143770474830597140877622887824243486401815312958186443551097387283392325078357952046230654598053679734601588540362620060479060276536459132372546565653123695579913597058101759487603816507383345010831310713571273100072982602421100695156412162269202715892999818873081420337072130923425280303530718797127238912121542355786365190536642567735049973793744859795609123200878649687290292247483381436507006989060705972140073934734136927984163026545752293115660552974362253649933129658343062817540463504632690739478897848551329348902386945617721924667993029500725191348276888037985118447713897337452970689778856589045715285285524186663534554756828863552740827658996160733964104606176466756542873805113004382716144204993931655640443136613377434500229188123058962989657125203019921393161876801906859273769284446701929272051052021370458761779423068827913780382582415228516372232302364992439337568127670252686773717511227790224016332599819851902485443492943488249165128443962988214205624260789805459791798114252680268000832613972242890012991838260368460730961265546720725356478381840645992536200188245048848123313010232520413751240480242492260841635811788929096259313076771964448117007849282344410739505013608281128305917798175123783497920845230103058119047790235820272098066659138927403365336671644732431207246054428917895218549334958752149440466270384723153808014485954805055885438262211559900077869834684602299978408525238338019903249939423346238135179040556978131673335056016721125363128704798524153550994604347456471160504845865764241992556826852201695226154928931956741052737081712080780882950263237454804052686202735000606286798731614244406695642946685930834723438343486898669481058616545797274747756976840746832295636045708482941269533203946411189181670021047584140171158429367454221984344964379254848504922121919301621909116530342827134748794674827545702887127205074683270263134983789686493477182220370219975270216224368920037526752907224528483438402109979388457588280936842841292427586517041874773854315265047848841623539610044780052998916082168391000048059814100937905067962903803587697830721561649415209565214564863203152316354832042648928799523877174778278679520747447432976658168656909056501596450918589856246982487577175700241458896655460786578102636192135180492217256350975597616404393856163291077164898346720331463455155218572939731883843071328091886539234185289242588401826215576426072860220981910609939585683772069927592057129627438923321165518208642275802283832877106931810662115165646789070432358620350248722303297672086831189338364635073268692532303272914957906847237116843560641455781281887355438549162246400003207232406566535682214334541758137175045804365663471947710403054049003766355502754564595966019522583933640918436836353553521178682857170128240373922323367997636222625406940291823810813889557739121872850911832222757005745474728101979922818626388306181960879379196778091354410405347214239545522342672137330468094450100165596683759625211635341600537818847040402835480034356228587564293812827226356546714784807017592791759910332673027391436135732227027789335164058323269022888279938049614925478567219740365700691504904901048186863470364286802438920420474355320638418061952106025112027553316794833396633280272922361951817345452023355689681305840842113986499495401685425785041756657801628282781542537931041218941452243134979664742170191176693108375517769513751702490329607878273606301620910983087800087381985821733128955216805782676747117481124263084526286341504341827882429142700575414032825543260673788859016763073589054569243442527446375037331540195072134320832219643028662086040707004618435926338254083155807217835382264336317187110006919186174308916806007576953791147313659952588988468683275253627487119827193400726085084798992781099866341928482926894133141461341090814981625144269735910143649904342584892992663172215924720915910285153346718617044099509298204233100208463936564218328796140277237834817035163346468911590698214976638355042411173093202482942268884270301679292453873307120914644912927935903354194832033524487958724021120129686717016780294628980657659781247704907191442317574548697997074158738052932212266681508290115099675085177402621230726080604335061865493782906635713386630724898686019124115121234450286707440565351815339023936526312641874175721409838242635836488030784994686599157917133585451974907676066212306761970282082176339643671633920044465209341071848062490377851397845988974450127975450273268592008009109856322568359882509524106794320684655136209350215051011600124427963719809785940023232961564265390858454947197397902880892736838707903302141410394143656383906953872204234570939302368077662202078313183372096195716367393089111299360895832216271767619835683465794245406407619794388620122118107266593027972833719455550065305716476609562616368604236619433536688898051493836777197494076528393492098696697021461012632481458796601988499984291571669636587088346184551482985609438354105948330365104865467894715691305553032194249692656422503482856907648252175686095209226219211188043261559306059525108556070896180189413983371860908567619835936063393301043658355864852278630928795784825512218422106004465682880119956668775757523511922129782856482574333947790831771639068688161061085614880802920502936442715903249686830924782136815832113937365792625462415306671728028665108768109445017555259888186352988317860141653254190427601948758072439949933848955198528792385559968694938537590817374168403241949407309748214814211131356468122669446745178779897630029927514790323739345369315035706604309594373287203446894941922011437485751323401004993830720191844096719466907149702175037587617843180379213913598871786774760742670221648451194030329922574419239948480096408892621132998662495153068231010610366473832997626020201061510813579172884364418459462970016204514
break;
case 6:
print("599236705...406666667", Num.power(new Num(3), 999999));
break;
default:
print("206", Num.evaluatePostfix(new String[] { "13", "12", "*", "48", "3", "/", "-", "66", "+" })); // 206
break;
}
System.out.println(timer.end());
}
public static Num fibonacci(int n) {
Num a = new Num(0);
Num b = new Num(1);
for (int i = 0; i < n; i++) {
Num c = Num.add(a, b);
a = b;
b = c;
}
return a;
}
public static Num logFibonacci(int n) {
int m = 1;
Num a = new Num(1);
Num b = a;
Num c = a;
Num d = new Num(0);
Num e = null;
while (m <= n) {
e = quad(a, a, b, c);
Num f = quad(a, b, b, d);
Num g = quad(a, c, c, d);
Num h = quad(b, c, d, d);
a = e;
b = f;
c = g;
d = h;
m = 2 * m;
}
return e;
}
public static Num quad(Num a, Num b, Num c, Num d) {
return Num.add(Num.product(a, b), Num.product(c, d));
}
public static void print(String s, Num x) {
System.out.println("Expected output:\n" + s);
System.out.println("Program output:");
System.out.println(x);
System.out.println();
}
public static class Timer {
long startTime, endTime, elapsedTime, memAvailable, memUsed;
public Timer() {
startTime = System.currentTimeMillis();
}
public void start() {
startTime = System.currentTimeMillis();
}
public Timer end() {
endTime = System.currentTimeMillis();
elapsedTime = endTime - startTime;
memAvailable = Runtime.getRuntime().totalMemory();
memUsed = memAvailable - Runtime.getRuntime().freeMemory();
return this;
}
public String toString() {
return "Time: " + elapsedTime + " msec.\n" + "Memory: " + (memUsed / 1048576) + " MB / "
+ (memAvailable / 1048576) + " MB.";
}
}
}