华为杯

有幸参与研究生赛事

next_prime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import next_prime, iroot
from flag import flag
assert flag[0:4]==b'flag'

m = bytes_to_long(flag)
assert size(m)<500

p = getPrime(512)
q = next_prime(p)

n = p * q
print('n=', n>>520)
e = 0x10001
c = pow(m, e, n)
print('c=', c)

'''
n= 28576274811010794362153160897556935178530640825011441539841241257190782139295561904323347128956873569754645071205043238985141474388531008367238218822591
c= 49502875285578675438052554215266678403659290915102322948363030271494959804587081871467110614683972929037615883922743651431683465100061968204901334627149795829429950385848753728500177164800064208215503246868631076011505268371936586645321659884527055007299822625570713613996139223348709621258028349513737798120
'''

注意到$p,q$很接近,把移位后的$n$开2次方,可以得到$p$的高252位,随后进行爆破。

再利用size(m)<500,可以把$p$当作模数进行求解

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
from Crypto.Util.number import *

n =
c =

n = n << 520

p = gmpy2.iroot(n,2)[0]

for i in range(100):
p = gmpy2.next_prime(p)
d = gmpy2.invert(65537,p-1)
m = pow(c,d,p)
flag = long_to_bytes(int(m))
if b'flag' in flag:
print(flag)

#flag{90b344ca-867d-002e-915c-4a897faf0bbe}

Step By step

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
from Crypto.Util.number import *
import random
import base64
import os

flag = b'xxx'
flag = base64.b64encode(flag)
part_size = len(flag)//3
part1 = flag[:part_size]
part2 = flag[part_size:2 * part_size]
part3 = flag[2 * part_size:]

def gen_keys(bits):
while True:
p = getPrime(bits)
q = getPrime(bits)
n = p * q
k = random.randint(1, n)

if pow(p ** 2 * k, (p - 1) // 2, p) + pow(q ** 2 * k, (q - 1) // 2, q) == p + q - 2:
break
return p, q, n, k

def bit_enc(m,n):
enc = []
m = bin(bytes_to_long(m))[2:]
for x in m:
while True:
r = random.randint(1, n)
if GCD(r, k) == 1:
enc.append((k ** int(x) * r ** 2) % n)
break
return enc
if __name__ == '__main__':
f = open('stepbystep.txt','w')
f.write(f'part_size = {part_size}\n')
p, q, n, k = gen_keys(1024)
y = p ^ (bytes_to_long(part1) << 0x100)
f.write(f'n = {n}\n')
f.write(f'y = {y}\n')

enc1 = bit_enc(part2,n)
f.write(f'enc1 = {enc1}\n')

e = 3
r = getPrime(1024)
m = bytes_to_long(part3 + os.urandom(128))
M = m % r
f.write(f'r = {r}\n')
f.write(f'M = {M}\n')
enc2 = pow(m, e, n)
f.write(f'enc2 = {enc2}\n')
1
2
3
4
5
6
7
part_size = 32
n = 28170615394813994128829444311922294768047711140557403853945487107089509134737767942656361548230221829951460844271639575394883663959935517401286468610803533794281322932272016151070004303694003064267127894498582758474889399072435632149814773794006700377495059535551601562497404157228212268055301420382159240876926718366155907065534007141933306379265213201601388196980959461243178574169497366868119687674891554278269534759630337252574501733517956676373291013127781435489132751470026441547613876124640645867844110455115246109355929378020562498143759261535211073747144498765678339037517382156239422037334011910477313579931
y = 159220553107177193400023378107257900962478698517628796905876914005522464561698874246291191230998317763194901894991385290134307075261722076436131488895536910117912445041560442858379826501161163372467275224931272546634069502187842680578039864204499755434023932362315829340273816781101788682876410192428287564079
enc1 = [4329764817812315828446029000904364191239990958949637574084938083315209184240421156324999952393657484925498565152021256494607879128908781983114161386773233877761015360983150476152188879673067820402780130089700234129678611683354395212212616575718773607360822879598080203335407111382268368008498423027220051792096684674912425386483869259429764331916468811184020204779565213639519259278266016641928177176668484572535689566444224491072932507222288855987783823718650822063130328026187325690601907181365773159771647515865731116111372566720244303612037805449124454939086529470633611352065816971120268530728617860742920668013, 26668102306639364855135856355763651227683599333397083188819835683451303632831224609344031930961740446795900402520462583445400552909615946843059401192100910201841816229508757135726985951926987254237392600963224841455347415104392678060751388564657835841678373873209753477434733262088722901011893389887593511574052919706851005017073735526827306446891363250896007919302191459506719320391480012172844938736519505482481406503986666696161645192008846926597435017915216589460545777594359492467091985478709953982838302464831161242492848401325292544174501237871845069969084700905686488816372729433646006791567262944455367739016, 6844078125337651272775424607620668866522240485694693608842649470742610100703425439968455577976969394181852381193846044735543995223768807347325967616379848732239727126570457351656175240931305247537451607658865181607891575819762943756479594541607562994075489557957332744121327416528927981226677030790670370640078284587335236530078507373446459043062236968758547005348378476768772011619000621368672432728997054226366429816199951693412308899897968044713019924726280740771455976700359519568818130969138209012053461667209340382107028989805200907615360055495697672636347124990777030067436694515895639282902832746618060610970, 16445916587011829288117477177744806954591866562333561291832896404767183745244588735028840851831708196817618686169345759919432768858117592036431399504568962310535059702868237188826277314810601217464923182498196049452748354829783565314615454005459893895098586259552023305027839163986536128682806093761197049332210752980672492994539760957319570771975078883263186215598624948074759626368175827647426656915331375203332203324216346867563573977484890640704861986659613265604060703424208018740052203374736459826889522082329823305009154365945214783049938660165171170531461498791201459397225185841341216331874697009036199986145, 22211432664265304825402740997238420168359181441282545342939168479723537519183885648429179373305869165607584021882005663420276620263886591107779135608972968690973425417716026815718229937987528308399623496352531489877608239338522248798736082632701162005616072647430047387419780667327844154816381472891171271106501621739721500965584580369568376933265860654010818096252518098549747470761119348553857928221419551983596081363326579972596648845402599354997168509533057268732555329346033143960638061942818923185209244429449278676686606068130877402399091827473858206997117238285641217592726457541201204393326812984144130286104, 16511232779912735072087490417595658551949968840055295914774841388154482033353432639030993940893907068034497970839592131576195272005629158445284845414139905286994063469467030298331711589743775359735931721642462645226340648278173659513085274755670895169310008219251006975203617791469761592470211801182901548636764670705016760114196708237453754643250912222907150769662702187456741276197200957629587032061417719824875911805802895943586708855675945895616117452718265880493364353726225157794273382562571497564629888571168472410804997637794113489283469847358173166655086168833941157071796878957132040997623213992744979717590, 27512480094103097276307227465314611547545346858211648942054525881667004167524830965569385257882995654409585906198988173817349347814674260381899986053289145982003908272056309665692702173697240608733910614419763821588941042143009788065303073634276352996799620386230711091221131240957848193094545073959784199926078237201427935735886744019644204079278430155818821118887092122691263007926633695313048672080827413326406179502240718781369712852614873058209447394875677790270956701259666548396273225360873370415081738047237391974759717107484394752280110411548830097447062784942716689970058190244679531253251236327882210489795, 26306532550457050485448815474301792204568917582934053647330750736906199558569339168158370210379253220431750531157286197635880817765270930826302265678510033908447481720905618769489494792965215447236454399227671298394255979900552517351237034015364922473318355366879192522833310772714750870855033934172693598635789568876667795263771308949609856175586072310213554484941517625618519654008863414698486200041977448647195631878675272608320938876533096920985369764810030732738355440108877024103126997372154602090678286147586682667933869240139315932721357276712877773098745428930877528886970034172240563829783902676727613469193, 9131267818786433114599619311362547055465175530253186866323428380004866131594635843841501249841686261174544336816994649394164202586959016200180745975746879086950709593786805148720138317793246967590914350437743731128046489169933445458607969773360388674060983405855013901402342317088931405101510475629583790001873450975810616065593474437693115366974331785770998527841784898750879578507668774413686200526727818846295097955990956309484172671784645930448294837960580539186913930454225187754163489018439011617635993103588325075527965649525422783908235490904887449991172484278972504658230450046804198707099537114621447899421, 12203699652864825912477971520136437121937440368649208171349786179885623451564743111590364508451654668415829793824178163535126143117530010798374620309649791333088807035522722209672161559755236536821303038837056513142962599576414048713872148613275313274094015373204422422010829484890388026088104989811785410352326638179743581937225537608450940852337069824236961553572414544157787927022837631664099139077640024883792378914296516636418168763906671141470291816312694962098415800429405553157733772735363984884052938687786734816628224981471142107014047349647001951529180497513120746906941093760413192282141658320585608311139, 20977447534293715276322934329345531084445260725534334850363011767717308861013736268335771084266777649936788312260818595161356604347097692475305854167279316998319033341373603164873935236410761117869000195922009064006201892787553151581326191897902679997662267251908210137505970942448675483263077081788342060104992998849070908987922008977597032022005189336482990484466887978809454188927983073014275289617432582859500906765971938594306218945145383348528551465534190076013646743595549792039933969792206269742981822765759375071009861443178831540308439073616458887238235174195573698391045229138378919224657930929272515335658, 22465073906413630105458956774632089589417389129704913381392841312216966186401259394147394213977429057445364385128674471768933060295390037913528215759779104754168520958835774213657359361109700100921698641908933197820277684740882703632993417153477618189682678172762980997612715664629128999735441370810193604768014394607142956284212757223919494092945332063152320935929251843951667193532881479975015337690687720466831597364201491667928952337934460997039749620727908983165004861946285560906127928264619049080114676909943356028636243742690563678521190941460525004111230626143362841283846412355587570290111948658430017336183, 3838517841103502313572694492344121913369386246866103636988930210837447543068679013388451740353238379111571560759447443235817506451097234728517204583175140392885192525119360189802153333867029331336945528452982104418420831366763206726445685074593701656215707559430928725303206313075557995703567722978861684440582728415616935260622130187911162586241437459374722672189211143848316594202032823364580311345618679076959922039906533048821203766064566438185775049012239074297738959103662308912079177329511839300928122806467173940092484304506640517700060614287748065375591705043074580786103438294126051507480272484576244810481, 25778799676245427936212845871451495109416323897589052712730145578317604816047290002351007327670652724145604612337696606722248647444724138285933318742143106903264811952002174815302602904272730010223041065205557965825809931399243505715420876206170035115394282112563224384973067924656887651601290183158795508195120376726739465841565917122550030616894516681404394386821072803009811236181667614684014469932087649651137775545462109035794363756847852660718173602416623551981977991751333999395943853629114614792455404447490778064387253000235814200592680174827990403705004759565664872486103776345104110990635045788034766811080, 2613327744100828691384465683450050784456977599449080697275221441118127874394066169654973689195803274309024059311164914899548367985147198106626020893082144268269471965928080835260319688707048473242132111203086975235834058957411648177601833134097201544818371911824700034562917634312861128370359564565116780710684979436532783465953695955186664908017546464902395276058644163756343220285168692290448155591910695900300550470656724061102851678767233939546189979842525853363169638440060571765241539037766577964809698764769613335701041335821466628352944265025939561051520179826884663371412524267975807120517099832505831272890, 8989639114313514632532783540841758616251903100393942242943730381138365743361262551964894081671051660442517788701470267404594453329426097713722427693818786657203082689609687724664807011166787960424252077447470730374684735267364398370360984831744782515142406080140650630689145450036046559508868465600446488642810839684800782567706356452671502541137116721915293569415578030248844485929688557064554336250794718659133841520137958208377746215513963640163185509376518508409399321496795210376618137754008925636840481296572845076452388754525187133737784949050911247591969022911646162103506046354544418545551873736720925790305, 20931313637219439952000007290536797104514079056746727100484937472570386795649559796480449298187608020337162216072917141373541903776567767352643461461722435081621219809478567771575557727639489055363988083951715025470493386894402641193480812674359872478330461782650878426250069953775187645254397593805069845047851186217756491807206389754282291655078325040960201809490814632998706189272721567824560360436626422612598294621690767073172130888170101377477859681488846626725401955404396981426279510315796212493622221740224577253830123735128030904246824427136736652039335749210399118009396828005653130298195221359615175268598, 7949279045319911820097441951312300779930785976399242690667162876182951256987415504736581682705035804115839562053466847318940146578889117539564476374799231304182973445573067897633397058123635121447651674994316238288055895563111254285684259601062397713071596220630489560726277659319157689038326189441307341158591375505970642111407531640054819328746280444660425381200050804453634302767778665434501644813365868515026819190560586573465107050060907215973332177239420429003914320360922959850611354243078821512191301076507207838574469529678065178914123960199234213869330792709700704776629646031888226416059974253098941809739, 27718427434995587916886703338452332174865252003660155612225708821755742468376323383404928220635551239723191212315945108304146835440700714329695577263583174476207090309139597750314014961613611619581959355337746870626258052841745664441195506484736116221222983702013786192061115658819852655053980190201910912091818852366637947464854229913713972820307314882855156784606400847518850987242104202449959634171223565572430889409902514591697395015551248756757786233719671753893186210607558083946261490323161708016165621086066389730908714651134951339190114075184266082469368624917783584183141752781797306203517252572348410142075, 8913647011767229054262485199804973151893156127440063738628134944908199784239723634412049869550792942391544599169370024025502343844147081452676190712534771312613457855865364324812684151798735372239785030559261681737709483070734038752902370003417873358125543955016115302890204432477578538835848762263320000649094452012566488760374141009316670432438057118591596380193599255070995815293333896788723833946322614504870396774306482599913489010319677797813475984159716493392314281392051842269287964441665480744908615348863904060955924809797319682418476115215509374358452939616319916595409100076347828470806108254161754892047, 5074253918528053953609771606143596554586027947842237605567537902638675417289397631945743807620415200078979753038623410843891913147617510170357031562570888242156069684897821507858441598732015048765676411154433397892515778633743597429832354210316560443581815256918249842128897473984309508497731259670851342726444217112696790829241339940561108823165688217936825603843449868045321769033979946301817735902384815914498209712233914580544589729684581110507789618169839332033578763157397025267750965426110724120922459357247102200489526516453394695182189232857820672903155093318304843162647865501401868778915222350934686565417, 12955068678963694200124556180215517062087568040733501314688312165084418062847011131962501151071651708125218858643723452954662439757196975687845017674064631785709480977841671976713397154346241105444676345356194358174552391568529167058633038149555505016050836173716492756026751383442968600556493633451803241120793777071495413583315251094712609313212440022629399210878124037634873051272132342201981914640923216308078157170848941934612035277678943264141746645828135265758363820496424016637846770525400574680805683535686783273422785309419988942412353839774688124457978733785050115302334852907666944287354771884631119822043, 3642460082158592853776769931136726272962424189660105990994792219865551895368327828874648776449478250244971591793458438595934718631178602136522988245339893704644186636299083478282241422070851918888308942581777650526021771192906502759251761684239927576394501129999872035374114518911128175033431547349805204011057889667505799788003346979432691635346577830612910355090901888253067870969375784335790728709957579933380861257833741224157486614239289893385144354262084580830094799938160992267265792911813704891469371555477517855272580327925799911118962085878124362604681360072329410595333081110651192331390822728874240329397, 5166750541605161816509347461319051246196828188598313556384772643738743990361076356263261095128654246390634842568011900472149583193345591728128501268693534936493235958457391730763572960869841122765738066250779149480518189223416475264109774586433970717417623635455705671807416161914973362342686251503521716942940525181997254379373186356976847612806287432776139012200933413881593373721621687694207321390364955296734863836974867975577780864451253796093164756185549394979118848264193765644307097263881956289444534936268872884309801160842335305121014166758954356312873779887896207277080613654470072721852802698373511200148, 6093961619594833775221263098571093663245595037087631733811692201358413159700381422981640080997589780579201336475029669984610933656205198826215611408872773565637446985195560594046065448747898702450232707029597320681670719653890522218541237307878510508477291585164645351533795600297317807848631243866576228025374751881954227958229116873297138971937614123309808929391165552633558297615290551850110925782947075676058684907841873435618731288060401562496873598845178866282751959923985296895411859203966257489280550786960157117247672716952627734319509782897748031438066395942842839143152175797316547241379616365084779355202, 21455802952003267464531527415990439491953063167864525348660387781224692299499911555426762777927278620148928006696821885196185314946262826401762163520774308918130643557979470423013016851168148536000697942754068103415105207061367832097417129557370046524575222644825726775799053685384914602176070127514365229914161706441809669765602615170528497758435542498366443718943620579582024720709301004986900085265543725030468140393719039075883840435605126538335859505420727999877176343426743933287559764510940062835545861427122983692065712100588567248224526324308555058982291003837737800018312818046265103590208331068188803379205, 9886619406464975116821162439203665144760128138549336630767651231502965119225959986657225909264119421700892086154360893315660606657515619175248429402120402085495850956721926322630459966409731052577313441904331794958007781098961608673816691365977303126955850227849879342250902061569708333862362725039673345380524552237676311029140076655861175405673019194902854804795708290709371382438545056611529853993343043909576128240363211560003782134240776641891811990335580527704091316107583017724145287601960134289241241236828089220360292108028044262083366755606799975881904832157086151354139067311436042511741243526675413427832, 10543870043145184589598135994189204846325435698717723919689594400126649136437303037438842775386929876102856324726078932456048764307503896456931579507284923270960715914050584856778335167261492857616666785172920530225005039483098464292807273070807341084496113325145704973409141290652580584350070881743017912724850431833754382210887218056039048157775159533144870239204709888934837984292801058937680157091954728532494672660870886686280921904202901446236870547682725708598050675704461192959430105322430548846921860874558360174269682693479222305099553208072202445247544416492478359837800802533934040587695103320450268350056, 3862789116089687763271777668069568090699261546216877884587184367602657629577062191729510959704603562749367169242393208996995144782782727547300626100279078317866863305847248934030562714901279695998489192766882643978237657012852698396930412979467634862661814667112891842012124945672211146123759866576681338450336868429530316030792157393591004906680429057987394070498553664296976008114473641384985653916669354004856850145606144334819354982313458009312997556165187870202357426251549829211573117823450362406430740520833360385900537691312111373464399028288005800592685720544245105483678676512888440429001960886157153453022, 19422937240544989971016075745123272243575865034532093638601568117378990848092067776501926269219664362716977352964171431850476509677841175911264311638202958787269602430985034928217482621431712987362764128097726538371327989834560056984460560943547037346466905700971407751223199543026250738702042996773665753691786149939215702946509200567509073553003548904354591211446418314210790591426448369133939937684035642785712730826482523597860763521558122428425575506501642139963921470109680437286142212167639848665254669765144876799009843003666134359611069860186211646214651897310219709573278320953254450131690339667100194179978, 13039631445387105446699484310062794799138291232189492853933743242003584379444356985823361780310710715788295423840990349747759734878046259432175936582332959437707616389785739887338181004561546630771848569858805640576111945869244529576942228055393770981898926871473660087837048638986310598964833959107577868478414641803337707285756855257749708699275838820951953056099747563406492384576490331099552895304664013381796568006567631326422378482946840065205655781147751770018748429788323738217417717442989318561283507796904086887086703075701369976608396766293347625287160911224046825488081020435288162579155450225796155373918, 12941976470609893861458984715589269870307271179414842121441943769960786422652134875942453122593819450230452121172726837234442189555186400574762846884398362530187253523036027884876608477434854415810087615876163935664250685253449365098784445717304596516714508825485154853931043876556438851800144567010602350584634595185044104941147048885746734288979291429535865151023055045843686913224416341934414890136068659392702066253724388563319268490386409741839354631906979873433040597413944786089170448931351419551456274785959253336300713458973918108079428868036398788719725374218627426148854705949903219636891283670485882361669, 17059192418742209540110440610803004367017332689815981838285234302416943715610940509925887353432600181892828159654521751179793810701018308539180274332798488149053363770339048721517205078721793470565268874930318758009892049886264775952994722139069845274599254967394288107349209183369977938263486285654721141697350641864300431572061574192903962160710197726860015635563366730161453124080744681476708620988581053286372818027532588711664923796604547226308688216049418729804141189950272073350475186595689690537383144670554794855015202279311549578948114549496640406192145691101402459636503051804917919632752170719416666338687, 24483487005019952063092904974630311651599954798139598954933184517291521147237054004571507610663313616731613892186410107871912549077905874150305560476736311617352834528041646291566324344151304540651773889798511003379037570409502674863353856414885241854264593587858757335736356637738000021741298499819161723553915730172440351937854508566403943082317717700415973475312133415303245651387250181495269404026733885921604647181882556587765521522077719591141233664439202763565883311357674505268512459795363493717529768696120454275519571028281232577329687509774132117207123429343144531562947382881460601154902801584610067800804, 13834989912724533598545682746238093531359563869308503695212481835831597862145243782961184878389373071977031228722241722884100634110344088995484412190509377400756857817566203243190474815942426595892796302240560174241012033680326134210222521796177819062676127225914638754116835994423155135510996950809958813842227486123668284573773995786748972365362390504447868641531948748446618994530060209402064654951543248722758849251706483570500947267168279640321089546289471774661100898580957231213532571391102343590120329576905912690308561102922580749685791851542383338447686079604508866910977302418517335162793072421985642351012, 20539892074054957109730723471250931250651403162091355793468909858320740901018845346338614626812730079398010843547138247222119489396799804194528633745930739022034469454771979633745390791064862901984484710871892684559503249922407525233215879531661629636499770323378655824637489913067741978083441493010268277257632174844046983686898969010445746723227245924176165531411189290705850313362548616476040111635215397881138247916273310154951004382692717028306911124573110553879075134713158740173257441451862023089724666630938456678373104308707156916449022798339527510664776324806419005663505567897925148018644676253125921680051, 12298536618150676219722059226807103901448157840354776628163581898169085530234194647689648179745460165576083827892392208574129435698753998200830435178051814784236137183727815279135524884152773873639273126781088753833381329681751512986820339944235361375244101642904430898208509102692158455195109359121935507259208291443432324864554954454166617881831565940853142934739377016668893515849115156361237877577982728356810583866216894538630667527191415502202720764350878850172294706700288423733130268577776451638583281546443790341625211861151195874361408168368350985419722596639470952509859011850715064482072351337686110995734, 16451959737755692861441974344163583107033119202323859115077739555237207527986305864477283285572361788198715591926534326480479008753834441167229455739851755944213399046694183211577473454395523536050371898905702318077456826483996286165790087312037110797046080327503571048734280508587179151442434628596229594131463943095913162945409956822272173368654259613677093429115421290395908779942952392385583850091025225598010572565841933978529497323836040272663625798072164497749187168173299144316116567978967400838588810183416187107813714108315060884773242396310464872316643609792705096781390597728962618589398264546093636161417, 18292714258467659909962112396780549598260457460046744933968030932078648597282311342069588838227241234014699458965633143878589105107593099562979536289488772671125501896934299687063926112094633389298542355843723863621686173623567775511285591173336689480705430195353170265504001896770283950114579638192787849850006891411686409864981355947977087744110852464193643324402850316726378982267232274124180792950060041498435967507735028616826563266845534126625586550734366255000035227291609435571384234798443510659538469558670635878299407671256406252579921979997203552642287142887747740385187313529682084484293187176926603526413, 11947175014309930243460711562525752972551280403945553320089168750563938371993629613287287430302199885409790484384034746455963237692316982929693810225468687508511401173091040095741545963363577595598799146682597983888094052675179540392184017410806459566469369708779678494087554626305412450279904696984088437052546561147651822427798855537859668447355171854745888335902707459362912593851728312113035743018080557752710494921859035315504385225746236733811429513175871674676624406659305033511264226082960346234660769202294047545429696983186577688269612150748780525774879486633527533847350917969874353742659093571624635747901, 7523731393313857905961009157735705524362919935213253045769006855676255490002634136608983754027761334102742947587971363858915094399789397459075979917689883259764092235483425158739255245380562402494562702400021734793758184374579177969048959989188346917535110199161505454866821849183959342644404743034565742753344285709838915843201577568630540364392561605382208563366040082331553692938039782805278046399964455666473498057099643953064180319483046119328440881603149968047883229224123845074945192590835417442090398561772103835745066024662528290910259970844518693341876779905253064769500441940439840569379963015453498148548, 11387491549999282604473026373123327639544347269145663100284694647732742566207128354972945447384764959041021769136133767859956145124185632201178445596305402385195148578957473570452265812135084980217279491804345119219899535598917540403440805352356792322782373870976881359664217555475759628714393323565418669357222204725226602953179506953444632617281581732443392771514644735063048457335135277888885998253585140401393483662262918181734687591372021543533079306380557236312058969160494419058669083781496549008087480116151293341081306396120179498514129869123550083129850283703075652642728103230590213195981650047924264447762, 12960813842809939694413473065553598618005600913521088242956094113367962581176805671584311206293236352262318456776365952208448342837829132941611025748509181895250696992599826896991348907308555303504472000956710178537466316134450364457199922133555867358592604121812364955693454201952600315035058778411960225222721571369310644131699363519979929343590101267204883661314114432605864665622690374344784319926111381572617392359088117443618722563664472443216323525356972069961417701292966992572738576547965839396557464303666550934527207264955836620340906742966866710745596496076850448057435164795636542646715043051425487453728, 15340085496132082317796322660450658040422692974957680797453670937524963817286226018085593715130008676428289815097283794065166511342319866190920859763654938113556187119846209520035154651521665453299768531875912522598518112437008827383273054132354911401134831228357120608537083381662031584997002575806219586867072190958556145707457893236947553857060437228866541815625736827959935753439899991905153130623957566924027234721366619205241931245697748674391505476062615283747736676328521634667214794085850798598738921499243454424107384295914645270074245150187522522189695801348105167858980744286852379767977143544012095820483, 11431486122537028552973820592057387615931124673223903588515291969613945399068378273599744852236436396511555555804704677141497497471022750303687426308463961697914772738039963301031667613634584676961717058628954190709284989970094249321049397134903223159494819459159955301370181032145021782781184243212660312108109342495477858146284789568210956652198170266822233213381031858324801847038810050101845946541760477340718433316217656138342319316719264405761066200926870141651738732774899369093547905760171635659640451523315466561321609067104444896994423648968057120169347266443048802902253400281247140012238713184461525482339, 13701313919957104438975348293448069715578284892105983893763943107039764685543313323453929075713811974408833003487716291990653971731018294660859463684650253936378631267502936983929420095459409139636148484563004583040832806607536250689480741548242118266872702824501739830107375479354199992671875731527443878660256203235884692240623686894460888293510039048591965240841714571037069026381490937843112299450446511100268159493059821530405043155562073153885482992682103847682015304144754362588728500455964337504426609628824955547423708090171879541145956012278276726344396315633053377690280183575254652217220420002852646166363, 23653201980406821060511574463469927286915811843587244502865197528731907767997684862570049110096233093060913134085447688115097350353688693253610377932778179606539140602982802138381988155036736183812356573552197097847137232543153831221712010051293652466788152887211522778621746535052902675222348395816127370360227008969190693932278632449916286266037601666010666411532759202166602209851650340081603866925535180230240994799470598221713669331334348945312410563779657156091151600057115993769512922978603203881795273627039121889992229719256344000254637720346071672866883420333243081366835074789208301773562539148270834545741, 816953932336804343449143333341737489487723611801566598815287965084690708948172686274378426265339464347318737025686195008676751256968246117079246731343205279089239919111050564795723529769976846726554798472972458921182487930936075429435640820748595501645516241618899263870960686423283858254946707378114852998317169501239790561563720658733858979878493499585391097344844948000619720387701201573416703483101890730904898999633137286221143694379203095854434533624614745314008931239938727728996873602107776472966943422795908048196795438152786861388160004723609530958268007456820419867136853247532453257127106298675988569857, 5944859788885576200475703888722699697574203982432129651554047609698247337343896325978967201485439963524225439852512922901796441253780746334614838001435833678445546096111035046046055819171482252031912233522810576662293260626112843543509633123118382160551072845518865430305233136539111251313169058669262112075641728734931037374956902850368181478927587402370057285006677872448575415070177181975589894615651075673663694670611633346207701352316698240925885850988954639170643570910740323202327847562646212793876009814914727396979288451098209194220219824339916899015006363819278906424227462446273294815874545014274673041507, 24427738111434277422590473670818387851876538871403765153461727290644497420789576448474761755998583109264891844937733350303730997997163829853236226467419015776924903419427006954180902826537880606001845186771681748165277280001819982487673375819222934157234919357381108903749416577305464520621179809519201700731534308373222880106828366146236781740291172953968568125773868931708545299709583724682908528005176506161574968235859557307619131236623143304595092593336769265754509145869108972447335165751153657781460251333208494426845493664533161383158440971463083438599385907890207568512220382541820099378009911324079698403116, 684712598971276613107936330293189204689268410783857138591625317046138995169260253189285424377730691473603282716561322601164434282840602288991190326456823386369239741359236411961591963011366376627520006367076197958647521619562958560633528999696694412887147793388603229338592066018515505352599628782243896672931009436968535494621238184276137736145842769328322229372617074994432251565144165324536674742375866156440655501716105813657179143225691281280508517970757749909758947789029808895867409286736948046518942867197327045913917865628336919931499910688910535916602309071706753622519926053513794002475167869682157890352, 16636194938881213830177271590175850044166898631952946630176580718835146862184700385532752842836031631025594030303788013850486575735772857667122219847112784559025782784554803011398699035848347539853167873360316767693124020459701565964622373306878626821223074989993197012815635181713087310851421077726362595404723656490217022848330271080530099039734653126457363463410234630593559095110998745978185991221691590037863939139814612781558013359439171133024661109070359675641150303632482801486680638673301548023352244475389569257242843438611739163952452849345468642206786992045456203828933002077639378670750647586716131057606, 27324681317898426218323838475717291035765262696669638541150817896311489344001203350666885542822436814966913425481097323188283276203075270086615191390646585536460852285239371919471605471500128539502098833794137231402517334081524522754969916626763358993780584817819871717779343024605784513864330577503355547001557689507204516422944637364495252902633338658436526167121709849818096900583253252070578603537422975875859278473425884739097182816857580283834922402170737644846506849252125858261484059273631119594152264938110307520803190906852348529906107510482363755546847289391333724985572793433151120633057194317248805974466, 6932986404564470389587133605835344896733779876300127153975082396142691375564097410960084304884693961031209316076331691047110974927189723694534566349740947339139545107490856155801774856042892792743382166400631981048750820148258664087947120684299075861647325549351313954669547845454492285251950575892256515335965137403168741011055348166111124937139187079375905295597694058552937503093037099146266058679363640184385207609862719204454593354148957241698931843717128821147584427303042231971395678447400989721580022738964070677144475279737155202380264271118034873515370295425767523736203797172913770077593247283499852772285, 7133656668590082527273064383813601558404554318298066792395448037157723981169083910837328677797584817576112057031407702823037669087060528114080148589637680418443812394474830063026458445160512920319208023670573049265601492189427280342471551024100376034118954346821361424768528031392385535889445049100910814959793841771014020311554495158224169020253362047980885712014741520352026974223809716033327211574609193398207905955199850445480283810591672243098360022987732750808423488362360091532542106346377235899391780137756711039722716474271932787519187013197533371668582003656453692600210614152729971653522386603615254395080, 14173614704960412308407652205364320701885213677808904239376724663019068987497361427539716306909110586451786952812322891330526172884789837713200288850581342873201716583433973680451218130630761280978900769041610371823441280857756719423158597268080841901393373181626228902035642889247361745661341024971192946867810020834812294229688125788517906067082732660611495133333389724950175580747493050114732775460968282442719709255675512514710408432301572925956845086869652980112315221221512158056677477073589747843933995946995092961267060099690024315987687597893225815646294309471046638883800405282568722646771137524557900687896, 11046785263286603962222963090984604982099694631591596186952374990026636959121170369451868395939013711107424193713366450174086413631423934307497925626870708009042000266022583928928278041004211623757915918952124938564754505437260795542911589917981554066060352211464178093774520998687567085884065235203681915333403443538214020178475149942380830239943028894026423092860790183667135226762965594220203730483246064022889870270852841695140419605470933748056126328006389038861845411658543797597332177053670311559750600247915650446385164543248230385522678626169380196130318748763474099271487023451479317929388300487700069711868, 24897302153176208691546154525087706752117105078602929046549992427026297665124439323400414065625717095084046892311614464027195008220004831405354521838132769561161864834080941650680504840485164907966905497961943572019638753243551917410480529174804958477514783605137933733462733324047686011172902900695672010570614535410418922811055829777964117231387532889791325259400395567729897360192495151245661957274264905217987381465973339274951894742896240108243586342979909926092502476976372650810236755527579022098082930202342248372106928225855976450283660443397267578095122178349107521371202093711487507988320443050273686845292, 25599469696366314882423479442058493137778891071280123062481122767282423920575185024563197857352053783460173476661414977416131628822635736468615020147280450061707807978109529012970234904176848947322962223150979968402542629368544410520755754516726919896955140733741683506467667822681899791396545505669309134240179806015840728347668413613942187420993670897816661966772787020188255686257835139026619994395984893698409929310995499918418994207279928042469054876252674389698259884300840173365294428563663049338496171345611561316060265465190458795929384558458538521314091497831684736929607863700583832622225396309764229422986, 1756278511126445926049024131640928016968753101820672715449129906003877792210827960372686851275989207399419738488031448295411748197192676560418792756199390092415162234412731763412369901794559730794206568517029099540928044936968680711406659408889446047542101531880777253563387938295439776251449447500222987896199131499567098918631757829807947151501363881557263665565372065436528927929352651466750362774953245745243289189140131554324285120599637089359609551950133893519757757795568246192285783010941390837904360369214296330802667931469576209456033223693705277350223965858261639844289546284022908949973584157558413509376, 13437145063162592732569412728126413847581331925638236914038522570871195816623265841481876960502591368493877051569531234844628672428865357687454517523711727046094747386806625155107943875431777657343602548706423099566638880470227712094926168077326863226349662084586388185370048416633191209936109943087811620429238601642595051179157836659671520942415724887296135598454275931001483201498903923209530263909854841625999643454181387554126062235547089879910875743586373229810573034134110981845472408438072573170667681937610068915720545709081595945895341751479551762132561062942117804079201925254806259837555777525272443686172, 20818832529184391009004487291131730168676613474905815164716937044798094819711378180370815881201216101580153768128934868621533276039047583062562053273467797244795023957989682011598894617881501454149862075344881293358541344465504033468253738918458136305435224888296118879410252220919674466690609781104583552063347724548191167359817523352872295804948170198472474958940741425623290829380374897608432748736562716073100776048404024153433356445339833973156442560298702943540636137601508466100359515620292368805688286142868051990737697634500685197413303380459490302810110537840620727887782948999347981343029094796478303734808, 11836134440596001782394282036155393775718421551147088418328216028553844443475930123669168890032375988670935597249483151363065124888770489705509326149131404490032896237132181995028938129280109556953807212763353805737483027206843083279456023810738241218368882102396643026633175764138644933966094924212794574840646413967215487173745992862951940806926102588015075801058507266594151774792477147314949532391930988625125849669674137813473208398476096973873711839716501921179283364972307606436756895875226583811330496267010204220680370167447868269517900801486700436495103338254732812207922895162967326098087038549707058087573, 21882161899886189603169623003385989579817932169525961189819249368264292348009527514824582971274092242897810891859587084460522455530435770094292339151136260355367267438267240608347330881330126776388836510457406171297851719313859598516078527689828402822025182013169044620045589432285994823013832375299686869717145294374037491837132489548206156732875322275747863717031408901700585617068714142441496685940428947160173849873270398108387062845427772332030657956886859437333884768247063723572597587915340423215414485854782899009639222680231055137025953174604318099099554925423778263718526813680482091393365033964415567279270, 714795503340941412102529332171097365216710060715697569817109218310200050126278222342546882955062165855740281252683155631488908697812547318607451203785207292880827279536750941870934148418014360400298143048274815185700224561430276366083895986107939063306347848011219324948724570689591046127080650326379014258640432157999806201886566552657297365549587746135859733660783469711164672699791994025775999573309845621305995243990745969023435987639369563829107904016352499288219497688615632939107076381272472711709724662834320437030271487278673706222034566211816555341650996200871106461988430454062664884187133136293390016975, 21522127884551800491726359181600647456956914793121999034090173813944429742367405401955060770163234591094601292260987034534330584876284913005341333534424057877158369787872682055107726736903614519564294031037642887810636789665195467898230007379159179311819007830628012779690050388726014649580608963926723887085947312088311060544466519794921279619872706366038345097978329227549252968878809921912034527027141093762162457434041188301202834221682045701286367700025529188367321092669040561511449724687379229199217321037625209256994619584219902211511693906345906998866718060241868106045803145933990446400095760421105538009303, 9339102517425115600113256980659933692971379673966209825261314308072388658566364636640010428590611644269923299278019570342488062455908554998937320790725012867016267036756890166889855399747808001347040790274188744602199784085486929754696719111259191993952116390002654344817294584492704633647867390980340625643181388188520114250868905577819988175580586106016904003290289728356932326528448835372050105733542236134317013412963531346057394505973598469301781488087421756937407266266750522182183199681195244787405269292918356741486865145614524898457588168617787930755841766205231150101247071261298321373129173865295720022538, 12243839251193940925639495601454511285201532844504728025564040176461024381774024812694939429499860735297357891516126468321356988961912335397340030768041350509769833810067238571754588055173477931316403589891631064621077852128582669956522213136243525888884734827297287842859283066691488426962782190264046630270794848145718640036054763372412503206359244945726041369191574459956739498746114206953279625641359792927468351340788802571981133181827410518823031204448668066385380876145599077901034288062069590495277649945710373557655608895072175776005388233343669627748808103089308435719375202909597782115797164080427936308168, 15907359151477343642605465276361830747679246283678938599880917071588058679082088449078592827058262281046936301569000711036212167697435415720707444090881878193178880326261625018870703858200071573750878168459671151820893051902364729368684550746637531398540031496923271744043026801599361087571876969901675350677288736938114489159800039072736576644198764607970045204543372424655740359823322540666582857468987670105794676931228367892580001642714730161707013455288871806183681173978475928551943313406007701046042700272371525946426055027825758031827945462945499260236897229109176885516580912316727542287369691328208139583601, 10118031262175796753455980862284587830651571137415064337230749641138182513934553542718411849408662098819781064513838726661774141773869663860724556116040941743423350402244434881177109834558348996244222751748400531780275408188044809590988825103963706769333588390445751166218613522283007945099903464645048052092663933814957352708299858347918271079578212237554566469635034229567810695802137225099378392231340746856191381117328974547608756907377105362729095472731315401302054300330158093340509476027440243788474974417184824485370739075249922373932805071524442892151377244532846795137735968402299995331137770240305040542275, 22645021465682381913972098084309867980555223569389427147134528497757769324827891740228743599758807977315825655117598127588463969789578893793414482965807520374794071258658415278713401506932184291639727959355256566921589399641892144109925099430010299345941852138890845073077154779030288380184958363304751937212457974914632805294778787598370899904913035908292525653081661470827080054183421979056818110343945811530545803075233006531407822008009396228955512152166943403962745216494098874314659639195738126764783512187090979815342966933988370198181679185910484129183813009804348274690245751193122709605749765995783420754058, 5917262712792988617203990520402758271272100924543573547921220991485764235118616234028511278223629609802183291569802291375836925476616176778564140404844263504219623329337097286290799277177357607103128934616672083287902461702592149582237746194125517374304215688848041704463458969064971488369862866742757868207063523684470214636075306907608154889216835439022701182544122737847011326691101512703261035928967050332597939739166682582348112443383703143861300693345396934544551194648733787872967591631076602481396333361897405091744534993667042793481484393866890392163513319353168825542267658510791222272731036886098839955824, 22200923609187753188486086735695114881430731376548027149555991003936594620209240893537588980806284786437307000510023455359946976346274230845459347249984595716225743204530925926087364986158736378235696629057839214962657669191618852573447907290489450311424493811407635954841611524498410194436367752075721799325781888086471314173028627869417083130370095917929079519281400345617592782216333559582708630721536077290766627784188003662708380471758656020101593353999394050116479909704795250387069723953883102662627932123236752985149043867559981896360817766105425244365525307978388553158665661264622645486985249905771249466605, 12128254803469893060614818928216627564056722435231881409617272537445510275256438965168757618256292138041725983087518432199631681639053889669992100179859425395510759128180954788655519009050444002658080996202623210582513226693900876415723227833086563366120275115812045312143288062429667644961562387213542470455897226666739986360245967678807199959784158610137094632540777731478482172214004792215626608134695373075909856416625902875759909021975308701185475436274922898641454038557946771739208476409691748824876617374124260262228189876081219378040275934923843941127101585066409447045553637030964416463144385747097458213887, 12434913281590840433874450376418274592044682439099417576474103743448778229626764299506949725671904964681155168956420791743412900162939783466919696333551155522728950890045483934761451055445831543044981959516972932565122543356239561366172753118358163664729768685825199329956528159025977985360038376945999166813170420511587499652099661615418138776976200282846009279339147082221356788779674269653905804434647490020524875020628031668758840448970668940047140194332854275640258501398490495562215113660302277892671664398665924947462433162990158045678722325476218837517721294013034019403648900797126484377159577336844801674838, 1981207300912909845843267885193660430063257718721963552951846473709628499632835399309461562418766225287899574200983659819654476527110152124536444222573693821002709144700191865313035896136180735849786720937809195408274899520444993641641351753570343524888378750976481185650202092827560361481917593867200717418394004203810575042164041765334470406948760337436759098846550090077361703039349931337238793087952687243333643091176410706793416548495471119775500995768436273388727753601270412011745598548413274848309701889408601423403159904712430678842775816668679426258640428385447579233599501329466800176976439298544862296398, 16018144871842652681165738258617089986702006223292052704961687736189985247387396261148912089615211018069642146519525325646346243771579156375073478999474696977570262990426040167882993515565343818571056325715244695035002495204251584514399375491982744727488101954402036315590216253878538411159725817871848638142000223987296735054223103288130755974213341325104132986395501417077124910065318867524706906232054989368573822135236293377952755266126772319994790485302223586555478423515138247102893666541841000281057736364489151662132005757538760720614967005462343862294267491675059104488203632639209152962398840733618186097960, 27898261777012671035990599293836467073153972471632976324708019637834083321524254178036382696158977643306113010078659086613233035604383610223166834427960891490412103328767979030547852308627987012918839495355004385237294087030815263572028077282042949550250920745903352873555863590792803982544668367976475905266789056706435269603255863267028525423005015100489180636162683095314929004076476206324073692819965496341485179528557668520363968447938016045375494094882062834940818528306579139184760355828342181986768486081394385688776957816025895722112124403734753731140239083664856929640913883932299277927059704733383870781241, 25963316206898315830036446641925689576648438914384584217197172442011276736424054282425053529412234795583663212159152495421297177580669212631662721843537928754129872974856666384079715180294262881950851872027715606554225477902253556842570488027569361641148748262975145839903867089010696537393403960436717689023989237359450761826681961173109895968697916356486842116792189273737298759883613397955449007771107452315187000727324164014668274561164282427713135622690702518481269382339226876323320207587816334860799029061526417681320076124182471586026390049531787254653198884765332690438295726684630537354097316171800997811224, 11992329544100638860759411886405094465770962037867965195986661716647623366630640212554899049074606164785795948776431224368123210754305965772042214185503147413786824297358405076683682975320188616086742011635421736205714082045080081666443822588823173626042526423698478101685503581252676725426684884218225366643024395943226141215745048116703879297746327720686060280862279955209905660648641569299599458904187373624686489171025003821631700676944141920990597097081061234476835140216162028694573688267446007210640581842477348586115041928876771947200118094783914433175250503842521808343714479683152163341707316307716948059429, 23995678447633244966005009840800559998446502614251911096054530470989228860465580323863202465946476462987885364029078421647915578578759616801781289087671262795394052665040466124481106427997872322977398087700818623706888431109341460092434141553919453664568991836538537560789145876694240322533212407966085492280303926888036756790445486432435371934828683137155340797717312123344248103571622776642733539159480716267838828976018821148808393412266074614063631776436015285645371803999112685991470551773489500317771952065892266463049644918344772401652681651071862229008482642539985541897094648646958158934837311499005098692628, 14527089553162909779090273852005842181586512028523092999721874296699513271104250651010351043650077644815845284878695088697198120025882685653564121519871864892273138718213266149522660600369932041844615422880871233398490637753401378285632710183894094592006186876655075071351987762911472134971662469996555197163869347942978342374176952807882616192368409851707605715215619159893055362801133206923691427775089659352780756859191374046990878316683715699505062152983085677279081946858472976238130495670137849343345672046920781531771798147103109963566143978785032050523016124532369125510411246341356345346702778869280582994280, 8610783396637818967701568331655326479143189814919392460232837600435237987730234656995232460736296575711006999636225863791905694525632096589073304255370318476002608497775438000705813610937426494996092725426474361487108343916704804364634464871195809164721272871532571050715836753237308049718988030287995558590897199099187584886248095783715579905938694550431039923147352521775774552935338940295447359969117675413813339600284610351257998013817131455119803837555373592076198002474784040279966165475064334583319015254959170685199491370133446717508577220959611016697931349473966951629991467739613819675985865719833973991960, 7788693329377125947842721047834642703571549910470482836382639737645031678556792985140866500582361878683163690437565921668887520025180664668071637220904270555192360983265956847567008166011528146609905576163713725600113397134415944614141836286732959020228855253993087111307430313154040523879249625363755750296288836620139682334281219885530203600708582939845741105924724350246205966713656644061924444910727551045075093121298518605585752203211976010897527263038468797576615360352046497317975539358243696972083490758090088369947487239141565456752310521099085662079357398898356731057154754235017757653678383944955182561887, 22506089329043990515612188809085051138283844763783748269122814121598635626173611105234158412076952704737606590159843773657272020348205443954972780412094496013656290794698305233692278333975013818410716263446778270178756656301334619398354212324891275617576396229248245480082642097237190659535457394689645985102057927253790795274214287339205760667924041203314978140307987989939511012270892268601879882970337498417142953862718349759202589379381482903879432463116103270783063969819859656291161906348268081801852690789889858202548233876918637215236664774076884245912144205165509251725373118408080507541462236728102146138847, 26393865457021841263606167658988912437977947754488740169081358613278603203731053187786814352197578145268335762030374164577496674215303376011271554235411468260855441993485788238343045020497860487887256005901528885780393343014316415685906701884445450118586864198965567047640610753509195585957508864528910425209274723936790456224059537640532623970388576343295593897134285505771695633509870341142918578527189094856241884648067249229846724241565678606316439097111560693479426142384722945272274667727698742193326501248332037857892336828971823049093541424983549780578571627459114433119986957091317256774896657017200286368295, 16471237161475508655582729528127180862131345146451549091738327631552222445805692166488036414365793628278574014132406257830581653095647064741500278709884572510614549977732777387831721301463933220381584636534991912395953978696873830727877733878572465489110023720403835828042111154509995085446771845812913813628558316718960035811619205707886339839799847241482036364748282015273821884642741788330373595642400375235483829521306619164130746421243793442077439107236596041765821373345297548501186589571775287524720604773915750895721755455354251665288981740740980512855044625166323575995830402824688080357589483027307113985527, 19838357274663152358602269358774057003061213815925654342593918274513620792249367818955208645495758194483147329540754972143378655595944051835481757579379577911658510628429154846761210899569093905956129760899172238068502375456181667632255335137062844924672988077534483868371343658882673058151684101686381330643404702578077464893169408399263426765349614883359511965141810228150254591166766086857047258018261091481404935569034007386729377916216451715962852994330073123598753027132250790649309732138782319297135705084549306286175588815029728984898824645828234875901511373270019247719102063096288697931177869763843633705155, 22656270850226275596153459179418929542134730746349633940658149105120544710645455654970302061883389437001122462865494890806158237580265743282285605788788683058815372622855325214564733232283225973611342245954195104164209410258204237497057472502564062945382847475767316802413424492180633295735785764108633850705784593283736693468391613196131193522379171289378873867457217060655100953599922050123527009815848862676842385891199147931668289498668715607827836307214598197101647154041685242699011706103391889189235219435070557490843701493851686771051990562558674423939637415826779289547753984626367038896860077263628812183384, 25428235693062300625603888702037260664900578803888777219236749986007594085195484764122317257887565621666729739249808061795123256085709142021967163842501568106294574873751823285118390200088088300728592491380628031319230010703192332371830530649931251342052266552227748708589161442559169626426085228900480974765302199372726222978582589002102017148438676313724685045194995569939507744682670683113720674690162093965253212770960712292515393317035812161304708824010159647900658446771106685915294181266056592418933657830445696790781140155971307075826167357347348122447378330870017765478235413089146649053450280054601395045962, 15326474566270494163231420750249824467090803237364103835360777203279083173975991377918724750917262258404487587152470129615812330475863019004743906386099752423784225847506401529156353421546817494329053924053194644714998950886391516409852923416182221242190213966800854151743114366790521627894724783520561070050211542365165811134341268030903173786398776853540658514154656597164074555964194594511762123861954251158785824824692565877982555042728358641102494633774050004246225153178308394925153307069700559340358243438956768228366640137711069765272910397933650308239625175742947317542390004668024088695704143459331669461741, 24765221351512304860131044348226710693685511349818699079154586327945985534092760019480083063384366524628985062493458509952689109302265710381923831348100122831342958202636084247355194211643538187518607739727697811849578292038421897372068623459414040510190496935903665107932807243660356991627049464989496051761673704913349488289662437402144528650417727270587687709282732174676502236293988416477523073012105561556377019616174595982122535298073960146649360833219315172086328084971515884928104573551477595259456731087098577899749128690810258596992113900640558489259347465974675807144270565442344286765362973805762749957130, 21239590076578992387700180434997992552265400431937571701441095962121807224647749825357949831167486883609241154980742149476904650336660249256029485355143813109738802160028911461728331560292686686789720115328262273503143334436220606989766010914882823225859925169874141653126700645733405293026240138888843265309807888600775994035290986598595392903364795827214986499747984764494576605898823233869664512517534577198989391650922296501546385655485522658659077068832693945815863782923493143460414158507086983644948490494481974415245202133183777430890431782451388513165350522848111972526575659905806667665315348430382963322064, 7225702668132147494966827859227558795567840968841308998294405033179492191144096882436069651800266762180796547431258827051969419212534988299984096405455086692994519646990829335298813016500927798707521293796101683280910526956985498265435524550003652313703102783644952310748268438044760129875505037706022586214811366575388939114485934619635374408364230271856998414159076081451436427856117214276186281131907566337193883080234531636619445142010443722671716788833825072272509041940156336940567522834716948689460429923699969050193489104798366339120609438118995701104762698166436414230508525270581298340318975141082335530436, 4617491755897506978599298066770311573421695753748863522395533260038336937046524841480833979951795645181253299256777054771496815697964990712136557527624061895479275131758110946065106707444264265349628310375805092711590853286238041466845062449861498344964124859455380551272808275736976078896314820447559949034283010131958481403638034331796044596644521482980454639010290280695963429663774814623387214108825542616329195155799438270147568122128890195232766082846968643794452900469958622264563341948787959199836768870143964179857475625567666219953175691854346861188206506821940652502917752151214777356448962035760023184688, 16717393813657486594680886765026240828399749415965965966053296983272880221758017605784255498079660847331835975172726241129975333434478550227074438593441540305475485849097206481615599304917309891544195683666411563745683379085841968297812280649280353098906282819991910002029486274567802373206733501384152571781736577504454886359310482572436276013871632517606183492110067344014353249438309357398666824377919112673724357881071913116343959577491724900032313279716000617565852365835370106354144039356317424701518272370961201505355019857575720783397082370014313451996185667832294143748923492002472072006840989921206204057206, 28134021743434053422622700713163970763133083199771240886358639537329389110968332341641748162806312401112935415675563045775778852369089677486150615244968755765947363791775746720968638088698750438622168475804799786419655552202609507760867340323015659280056712199210784792212397740836267016053447729789034344433665335673110047683056907381482297699859212748523649408370023265289308449893969552075307315677276253726275896199157172832853390229781771724617739786135219133538415886593497924186044304327882440887743950841231514270635607286226816407054373573714799610271299627758876179366224814508260461080887141578068650839710, 19226153915529925076803592096840540579190789929735106306853965883784561049681986482857023238995781851604619783534470396087369223762461900235665448821975173471089680982035819379882363286762322291641613761727157964412370542467594042214237503503284831071640604259384305373156222719264782888879710262276940798021743230953776245581242928437303159478133336079292248899529158788802182984366972225035433127677094081643774999691641453587692974005542322118853661057668121189259187823162543141429569833148084921146688858713968337802429707832525031079872740648136887945138796731736512451796305097871820150085408550895453537985268, 6132026012752355490970271369864380735174449086713331052284925412666291496343530543169333875949215723437717388507391160960194795373214569515209484694917505955293238896681093195094001026874776310619757753016164098350877015366870760421730840526428041470972700179486332023653995137984934244004221058865476138531782477035485830111579442888167647112990288614256667199813195811911337722563758001778839502542983867178966441131592127863023057946070973123851228738128205830538750175894512825025532250959719349130348069824618366813119558524140717804073495589710973361422091659630789355533196073870755757007198418051713101702949, 13098758155129360205475954111288719739067885898010130786038151346096831783086982789090184050366191501473934233567313492009573222688963571553166443978713700557214702376270048481401285726133866714588058615957972726128070335574620908140215292377009501801385891294861672677374034403226618302998656363583969666034736929492351910810164259111570064070116162072428562240319853819068421587233089648644374842929379021702876463552628453805795714443568561761626252602161509069214628469062441291775853957665263175100337317754654935124249355378249954764857091742077681330532369747712637671387931165357756336813621378581353672030756, 26542999689447305919957907493821622961164172065668810714458828543883375437812490136095092139602654017934749877511953771560133352559595458374601915049094917558968686939804225656427708946262911590147503884355535919839902185653082429516834723397268570975568720648488113862848023337995900798723983143805365468120584452731650379048842955420286880179440249129608058748454459603098565038657384980071851836228953340237117664409745673528470519687382889480171927635159918070638155045628112345800492824403920124085939636673351616808193225843536832505486376794798036469142956734888306625648391484011979497687590125653425161879377, 15910921333782905184285985698882825498813694935426428161604740807033205291899062993000789860129728657378791079218757043953569285917252699362892254360766890575331475432295567023716999042589335204106489733203896467967533510034867160905287163240595208128849475049702724880470395309053136275123766356151881079707447541605142732238173656692744063152801800279848245357114041394538982820505674999446635212436368181243552495624831173267855232980547033563579178629595251258581323518092862486892250290570621633229507913724619673288494065137690655016476621804896737676526152179561433859270928991760171635150062354538795950534001, 2934219715941826764969979633989166209781301925717344972178504194603152258344017842601703267061463439635170622709705620509939037496130777792533703047681622232686391841418329486715886544323083606178207335733376700964199990049593639236501550330371193414047181606523731521308569926528227222493653194178910561081489300256366351400553394398198424860561181464787158472678361209705022203471373010858171252694942910795090954395476977309379052818826724255148716255148595199289436433220046404967942373103520659790499779444765713613000617066338052995367975661176840236355664016019086170508519319583396798302620821736306055865461, 1791135171718240888931297913211778905465179550224476295279759369523182843035687513358783781014052854247571357855249708150646487106283439344020384104836802789842407141051267292112061412872459847750009248433676717214363678691523929125027560454443131481192667967883634158843803202975279516656729668767584507939987793772542692610838710166793460899073277466513600106927978491817681800834168165821564676232836186716710695644558811643465087949981818902349163904522357558120038416030965665243218038377053473723050933675649937191513345487761394372414049390729269481437780540946065634168478559559102429319879396942670851936673, 1188609736407921027916499646564228769742582588528776277195090477210438809408320722370191982234438475225790283032231015267918493064209113033134145684319614455239706387552891329895560386632750542790143920899235186825836852348327471764865884755544975041557559325423944933435333305808698309225177626108456895169187224214779989969275275296372656615253698102890680743822381582534672418533351220919929608819542400571608151903297774050924543300555715961686857248635164868797025241674416002440562486828640805343673272086003662722035847893784933741490533870694311213721843871482283550603363580447953468535573978163271376619639, 24597269303908667375327051925657776192091743499475618834126256577037826315846551880904642394401154268235370101731372777624645912175719328583258920684986068594322934299967380403827874880164016665402560730949611206329546221067293314948884243268057772516888246607048081663775050602572184667490888589158237532225586594401621597201242162304928658104183205576637989632943465253230708215028156974661681122239666470446151416561737388345231333493934948350378215775907289720626265634940707195747930614411162961609462775551611941714467138617429977218879680043854891688519841078701531836511083609039452669756420612574944013996444, 21820531503513443982834120277891043746325657445781715620970222845259893590884322768538352503248204256683651241644429565941980904045737911888074905903980319509871405909752673621495866219854866253263761453572866112178084356715358501076021583226520585878800357218809289394393617339485486276161516564014041108434423757751629502975797844439879257610595798490797476574721824914646295346182137523540398488621840164121396711360928879517751012852041902835203486061399441788216172579236611334065526141684707326667161379397638123180740405585413046891899348402048392492673418005212582072716369483380724692046147724176014362758899, 23951478899466423415137467336666391522891180989367328678009249267137269486486402687932028162699994094315641584173257267339723534195035627747760636834583445008257566428457027447656308717593720607611256047235151436482490489139491588469253322705775386779520484556703742964329467209192190075568295425760777320884772892580169033161399481457471618692069845243233392776535933546683839802716025012677054984721531428653315164921202570913231121451406164209426097605719975192578866239222455060049825562728976277509280596634476124330119443954594885152259059299772397317328791521037445057457164947187040771255391055992458718023930, 11275800173426291747923369810815277873037845163739634490909926106713242752700926493840399185286693635815973755385128436374740227605802286040542662258277169566872935070334570934826930767236091789874309553177063049420141466112809797136529664733280218095344467942350257603227084571564119174102009843587902110275933570518444844376002864535999108964261707570848904184036020576596095734980598810351041456400454733443209229166313152141696078804365053897050715066615156650630875512235977379623968922782082483426555137479208697007596332601866054747259030353774969357390367423257278431938848608642253101330911549966585352465354, 9824130094038964869180975306400534260825844005479151505482365357016838018069961141762627054590897426001301240070593856421709638684566795738023236142033489597052089624431967989903771172729796465504765177841523746390006695665433791239307502908621492919297192008017759699019437065863308938193341909798396245912019754815638768772056718152183491299433864549150882034010559947019685219627676220416601140211530200662164403738022796126075602346597712896305725557437624297722526867082662849184436817018677717878607551141675251837169760722716346965752160351289195771902416628617255277068500282919961983529333398810082746335677, 24096133473569088942128598273457194130413127477625812721049758921586886971879466967335488668053481225903224990407890073284205809023034795465306391918013805619720644766568395910905268911912034700375585404091444453619033561284990709967662065550105634591419280336441916470157847602127373332329403554220930559603119233002475610105109801957472578411422187605373080539698404137071528714636588186183220847535808737951361706545760810411173354234496422731369976398540968803815302153515488158751498478805364686040377535604249314445319557588359752543110578763472867508168696413059929542355455857568537219785625787038302880032139, 13509222392710587595030061206648505008253404630588519573468273156222076313100483391102951663156772510364399315611551559843750380352420641832195823937221567404121698194214527140567326080626021798285982451317132002834769704165964232788299196072980593230398858686263610204172178522408762031367557849422467001122985014822561193610938315145286155959302879282823951141763257195470945789668487684638864779793064442452609367353295236851453408535284878015210057682151541072726481810348272511016830622648553657329913449014470932720842641863449259516325702234978666433270267444155444508570436441309047995506624738787109999574280, 27005300694832578020194265930373795369365987768293528950637431192608651091450283811410188305844719944435640951313629927544896698635579593272545657780628644117141369074425432176406803772573253687364349403154270533703787611330122430361937559602109420649081086844570749551230688271575357361761236424355925922960845186086523898670020396130002595110203816149106701811737923911166331653978493287404642013448282640791281024604048986563039855537796621135324396148989904169009728862511060900519706206651123444935767247316064325302503460589254491077738370563008119103179317323811670725616961542028399582123144469418803384946625, 25425660095944630873853100560644393489081375355433959724998386718381621497549127528068699012459250609990035645863750746666454402819247377597581942409349486493900234975724933626266717922089797736823552810803971620313142820419700973290583839478378104490125796039886611928922696592061967493134251680110942045616491809296234057145216771728797596806260062555500529284484863122722484831497845613721941948110718153414322430939932022739978343321499214095610942074283140304523271170534754594653919135293102311410509529801188958061067399835418840174872759036801568164812137831695348374897987105323150380562686198887041242536151, 10312935059494582040960620471627669493116282335962586231937041123433569297899888065038022431535543257523373628732456750029425401554841529525314645635518368536344721979327248788862667895900864053301973774927001438855055103721519339080646670396300738289327093036746400492227495696202448582939149080941642457129335364625390129923049556086835503656864837638761483172655485061855867345644772533960928885495687078502614704245419066172264849311927525147741990939276675852266058085869665245416260116286866292927569054225137587348112615393812644769068216116198684484714575222794400645254481063604936861484819761640553712786387, 733574902554054488058061803487643785303822716757252949172618951549388912520293005713841616304728552868534343108446064001603034433684935968432275583612392224594959146181864002127891747910158395433031859872202767392463336835968770208000465868940495359618352504522035030004334676803165234569021306776763508898590540531629011605496527897862738588612568202833450264402189582312545178855318866781139295514429552117970364827559392010520619337736998387599635996868841021556600134039059927889633622070455497107948393005379568694997678617525125810923535783435018237895824311891967697974577993421050581673073716165109391399365, 6673544432922012099903513736663524364649485709548329797778690908882405141621877610384138544000829471662780290672965827176165991203700426345049827058350828200418013059704923961621440697681353263782330092618616439511030309790901094153600077412142227694236623441829593348662610831946346690355801231990494531468792853130378933226607186966349344822035433828998483548104978256142760360047806522071511629241018106631787912490416993542331092868139157615363865631889398935166973232683773086010375731539782341850527688093046749926416728545547430474685297089682657484316307665578211929587638006445444634221133225646763479862805, 22646222935725765794957627342912292103028863622588467873182633321675083537146270104246090298168025371577292941225948299171114371647533660372763835804771879996186357740456230463646845705764080603136363044614108333319564315226956178752347987919564427457359727958412488498406017982387343983003604016416957254211659894546511507314388547726252543783824000871091438823073276780529458000324514969771933831077501162230948508199078765560873504166739271967102018985523214282959829482923025562520694139833335201579076979996583625979519583068047634372353172878369415884271519124056441441262763833816738070963296020088876214933543, 11816875083696368935612044983341927310608953461282081707642780617744815190934964511473171944450003122091418037278487131198640166216736564389110588067969909006479418388464192722883129589473645198765027514398689045892599335159612518394407729882046839823090733684325613948829140342905057855679836889586336388445029114117827662105077512145890094636132929530525315033136885909443705562038740944070752611492154334210920317496998589151795393089624105222138779121382175423352565731361232608100311883730292243024132813043261799322350639220688912727186844100458073707603843166978511960569605545267900331638598935395542320424442, 26286202380611826267595099143353105563584296475099760173023244952096317613524168273259549288601427878514222400847685610951236867694027165347007553771487538489111358570327941034581470457537658100295032476088252733900054111454207865320508092992881057551743314949110371037585787895088583411996689844001746494045696946081736993443150894300748446803757100236798425921570240975641181029553216189930929994224540532815477176039477132884886069503947978292526346758488704905472571165649762365734382863237783155792281189743872534902401791207646494397226847224588647206783066261736205074284068831693634039917806044332322791300948, 17495568107345263090916685711840727890351545836313090176438165675137194943923601544389670385213175014284561144803146595485813084370743493620963017720908208552269970783126100488312860222166530499435116883099753245574362236038672043581561971350875661283006212581581339423681363972873598509438674276010330947926270594523469051959583258154212019284188817512551012501657209769557526450343963392192975044711751029244140904224231257499314978842461689940965081133864876125777757676177945013462876389723952720278659193919065694224665656925896166255359105966228037825458249157054258798357805251277594891910349553794461788458006, 13717269992424529596293011341517548838698239654399027483939915425649066658336349181512439093044202308571996215442460174796195163788672759010981923722288132804945918413139444146560711746822726482471696572308997303524695239557342416970397997191472037804899395737201230072985899759045009463687288784327644148759141576460666293987302994882690920029594262181379724175129639375265849052639014639313873114420072122761910099104956681602419182415778154347466569201743734359299016013199145734683011055835069219167625094301699438106572257812630132456523493127209097333043300084635631014614567218548733845228031509314798680865161, 2760604977931093276492213728465131191109071832244134869977704484509372567794705384082673244570868690410459799832924017742047271318938954020125520230417630529920021823896942185016650345692944476965283516013566816562106220688125890696642959017098193634587417861139202892540052117666439392720179976761526319756356581005036883390429196595151978647806149300435704826909232496447679070001190685961960836895833265716445341705797913809058812686039327322738651836588164891408641200065552943824684467234519189654004201958614026468174225396033581018576415989445371294146106374029989298722233370790268688189101771839019414899566, 4045787354298035725298340969719599720933457863314414060226420635667537060861716735092020994222115387664424423124721513133113909040916618436964405200985445242140613136911397590475854630527121064083544243664074622662351794486104089235836448579241708556091786450610987736350550341794333028210008326520552844344703390910903958708282230750925690533497586328593098161087800566801465688428602475127574441844531909443602177293110276770212113920015589758302649342164524875967976071958514707919397726573169792088028872010184231770263336178537688486740512915918750787543768181286161715354278624822172151773452361519924849164658, 6933763877016907852593292929081315353360001071490106161464967798504119956499356004270855328015756505681967727658302343818047493174409224979544531738656749465907840865023086951508914381045225531191020890227947839505169614353052464095059998293056680194607011802397083959517781763623365310427787675688616506130689774273037969850864803602002280257540324943569664957529947779139010877022194542172204757905521718636243044155483901070591839004907321368678874197057183288886040276056909906260346365973366363850397956569028198625949981485393699432686786642923892872881014534260730239058806701087314961088574127114106920930364, 16404874203551880024548333721182518101154526572657613094355891323366711733171960836422014372983730034587731615641167172059663127671179316233447256739877874037722980305409955290679862147340911299108923869338110734506499176774325993033010702857080434652122388005231789669562076480857635669876639278998434242762149004348735653061335815953066292966823026105225386049827727426861332902997840326966718434778082690645407097990890788241679829136073027579436231759929447880813057819391752042075560682326809659501480054782218168737910475341961756845586497607483095477735648395109327002093145799919590541915716562207665676102016, 26816342547690160288120575122622916799444253047907754523689445291152246682768611444670772461541846145478058045436085093621272632918192429216315312794878368601244664890636603881139718185879312500956210754078321078675317681650968774327931334236114394526015564008942933794973454163982638988058083505366905827975865794186519591748777166854032624288005678207166391846836010105558893272621183847227307387256517736508279507453553897084860459017090857546235785772126126296847604065971926859054374156670291853399205496688236313326443733228038790588976545188107437965601552280423960953493184383426565193023083689731454251146952, 5381588196008792303859303936398084637025653703662783739429586301836265216626866264895706826871417035230010228473381410283207176321140101112153093903198968639820980551816076264191679560391508240375266846335869727356852609464709191222183676468993524650223888303280308939638379622708711642954239229923510200730254430811814980704850079037624528172311033310607608055896129982150611431682682880258808721307667621585974477123910306746541486881123507388003037947049296560212760168214163398951762600976305214619206656723194044768717138024329940051772025897813564471302180441407773462986644949259425749447945382630514932050432, 26695054247643287468889780649951969482523154870233180910100411533398453485401700761238766944010737736647636776198805307260098835434619183741384617855097143149656128526477801529298820227558115453042151019026385545023934701619828897524258582513926933387486668815864759200077957888891204477968905265949725606672822151724441895655583428661496505356351109196304605771294852454533042235467474642343796893090095978959590442404545583320748613162818125455332250525148390732300916525993966451618186453444645926250563454266341004622780086824910983570178297475760809768526127740558090305046131612589282501949049614548002431673909, 7667729229139116055511627568537593638718647498032929028191394578131568187157233534564262426318192820117016145566979179857169725593279048769744866666672086331321284576516300173676788060487637047944238131581666455343402072317868441305284245815158998207915564524778066787953252307518634471733183514909513462093715750064450754656696803339025035830385672919582496292247761033800142649413423571581002619973139294821302352475784952106035345615552213324816331626459088587796512241802026754777066842380536872029194447336805857247216622751181851902368026692409436654430501993282144873721360862955911307706566609476776711232514, 16592156564488574380352624023135324860604045897512670066669621897560639341994085466519880862423662358800161286256363937262455759540318162219516911983442468097087918681345041743015414309900421375649568526237297170245416983792437048050375255712673020055554803370812741065042353389787306359986746536859318782002818921364487267799936181042609507304142088583321823543868421037700739324269930103234201567530417662255404580488676335079804987074531673838636600130629885472102701933894476353475061907610139589877319018809892899885139651767700824604424080496479206967839512914680630061715030566577795118956608694908436060537203, 12578486790016994461157748069667745388853345750311790074747916416160715888574541871863253277787284529382433510295148348522849113458924109621410016738234722886900366085711977562410715490672862377527268579244081891905501824295303362803044874308201888895966228130668853161513435575778618742638190766716568737451385571884921841361187523662475584320032182924893780117311327347391146906818075242145683211733974042372895873549429295637050151354097126481660945729074682333786973939124152194396259533276503452100410342299326744560977089947238227269493122860383727289001469097982254568830872291351392377796624052984295867845090, 4503233655291552226905300639139039024525134183763759516843553472321592782895275708064714669918606973831517257339588416181761637949092506127031187742980933462533977683621775722689563764358364250266159580621843891715740320965815183034451230879556192808302188359023032334205578009771340194966322023534562459091140677055414724197982422306472930636732068839828379830323150582365881404149983317724984300606162228107473762015093408032585052939057426948177967193283431050797035598775426882275897998425660878653561769365157227965807492224711913994352711404791692747818671882092489452065176226581899179713881073047411258672971, 15219866440917088102777156663268655157524519410622106400920591412478127221453155614149066125463437219431121591689666303920935807507961192406310835911705933281702001548556572101218680839536898677411954315389715412529019193703858494987649805572689303273925484280369062195056175156984385953860749653717480849301563498489318532115660340611187560603676981789089840907887580962824004584909646836532807715632487320164240825368912443929776711250469632006901037071450947815265286435119303488978106907171570342215410444864631920280153213378993338140381941364777729894114626176967641273268974616334263296824028270677462131591172, 9989776335555526483415441852951567180058483830708552555181326531955053811159228898684757897440101332896030167172270915200233494479000939251508840729591447796662052228817313202296072936827466878569122114471022663173374693778921642739053100705860813781462271968494192986747842112036702848822266450651228678088444566945884511074097372634426529594646377934590955986712219309913583171068072865405663728260915698860684245225007744190861657830320492143048658986022425284193635853596808798724921280635251661289411366439541515144178185137438562517524654592636501005402477587953565245966062353937565908799984697286114357720927, 193557968287654855103438829582741459346661749467444799612729868038745174003241540603696560042683870544137896596033270948172653728737332737932929156957483070877539680095727271244887368236920571547695716151452981203126562489108413307344764996551358157383754117036272048035187167035454577244564556696508224823525535820010406504324046944364857632257307728228608607950855516398541365140419762527211833772530306284139936393542841601600362320659868009967452413094769434433980688549842965976542550318976053312136079503454929690666712102708765783805289780210374248589529876808903397143726898209229361726497545716202219877457, 6771567955976011923852040665854322359323839227025038531275025045777086828725069527113789824530964997682029464001575908915288271640152744322997227259033904388424957109133063268170852998741169375806620977931003770487096379512742098871657997950049888423817821439746040652830994198020654942662160572665139340020761599176489983483218196746651317142801276266266278443360388715255554268592292363902073937646759900410245836617105705475058792071519545168244166378497067496071653796670770619854744061192257681746521170729677122198644380163391561470164439791727875333660670660038687151279738694950875702953498341597473463421068, 138327548835608404491976202065945819962044803955049139686036181449062023318780899323722260599316836999939224641867986876725694368046746456595051356673660514190794414299679104707437276813144652278635740328848855709447927151843666186462205194607480435003536707981018864987515494618887753014750318524931012532449189198864455675783454703858592626164675817468475542163819930304444723374892354804700493447938104207550684307191248054491067859868570503495611085283187601724919051979270499196662655605284935438183781410923815004479517338919672852931590893187992346972011179528746551720792602564960126301826645394953879291405, 25486418087984775310183936248200453697530173232657489993172466374249886438438265251702178114076415995688131488939348424783051331310811415266929984113964172031487293540804769071508229322670105987501942855811466014263257793381043486960136187007158393797978389941560210012186368242516778701955990931843126720502411041785284352087660769154784187925960965484686398777202804112953821908077612046561941128856402625704069439477270941475003339766201681420892337689784498300757778397453842110027152493447765840087070924761610082369787144097423328755103924909876906486297711456139904369973764027602859990852191410552173365004227, 7090523455582340798136887471779229013703258980308572406827844202656315829394792266632051005134242842779769703085596124416723101191688318139731764075919708878265306292111610278374640497602215186501359188001992541532301784441456760777755496418017976060395163402041292081560589812921209404981167173896590249076784376708859070014940534221347972768340566081478873999873977627335100399896598905298035733286134844475080102885117197390724364089774168588556583614780996949495280795619260961418068028090670178462148126698250812785671457145152120207736960494605539298306941577587917758222863988180245513924426638756146159092192, 23667295328946276613055324586149564147577827966342052245154133784552006846458900317468275237182264861146576242659046896866197435309142082949816383537340596370318351563776312322253371969941367347024374547416842135382140182412844151061085714215285609139158947329677826909014917203865155335793961567048929091681982326853929218672283009607688628559030290547428271583146679897799701030252254082320943050194422162711025859743515564725884781212617172277319042541319593965129125966862730098474118277242505886061063816537864134168670459739777583107282963058305714795415915049875252002186820633899500976832056197117917338452058, 4962652565444622331867819947333335276072229163132428939403185594217766892259639954985923769150183084794955838537225396977204810213821783946474745744012960109016408261082396277607832514926782010237771099267617598966372091083877839265873248724332192000851070295888955907127651670556189046348219749047743081965103385717124357492165729835575165521919039712053281071764676804857929667362013523114600454037834489663006469704571415605962573388771217242378222798052934590319488604924705210346399347985448098845139001901284680193708118562341786138643383139022118935233641632278904815095860655300106987321374327807109839778206, 27143679406621572216374300089655935464636775593883745074541590741799137009571447942193452947657280486223141579714044057161965025677490917042466564711231776127135583339254595454152326459236270594709852763181242658818491119858141856391811575231766725427757521512783668118924754040052264576944480377797127027631281610266554979572867560077515793929574614260626346041498183315032234646679083638590781110743436164155598259125883724814772187468153030534774344648069651820833603440314854584697403997666424951487839443549419841423109587441615040392403683909342123168590829409217069958881811209295232276451872949361071413145417, 17068652179504265903346182847679786991165884365498493955059076511417884443066795215623320879711567828502579368773660925465112511783921250132051722510900751909256337826891971652137469678541013158600707517609200470574970962814768292600843520105384752698963581203524486484849748134107024767294679306656267714804249352740691865565922056216719049852061001682847254083886263133773578032752854229093377736747606436503414514507351685585974983185817315681296680181480341667013331943707496089850099246400242780627091506691723625518477826609609915759483497728035806171395046492806512811876062277095085731077291713694940193742008, 22666809328727862457573014572032610368120398610398316230468303650309174974508708975402326808120500522600372808816845726497255848337046173076713432217266630673822650225177417244765784386586145216268902712894657347314058341920580122601811109601074170297242667464193747121062835998332160873427884094279787715965382392373572585758803960054852619376786093055339969227974161659148495716858515832948315320096859538740259642796822805566944514335724703096679451155092897640139821865510246680096410649014778117668289184567997278597522903571094179280038044406596085346086738350971048324913767106778451307727461215714912474500981, 8229154293230133402742379777492862546882607683091656776238017493777705440455795935431440946490809617821715514050084272305517850675671069660697430534841761398710987196327178523190330848786231946108758276906846727338258184686512128886468195960136375274335133650828594426882026721279240075554996771434856759169370327451529652735326870456561927126798856895240234855664125722262213951406167235607451352967497647440586180130873145744627223104169919420538176653701572185631147028177333998142871394902832536856801892825488868782045075193646129396673692988801557806999205627892719101298932399031783963785988485495530174087990, 14817219564662088105413253654686598360644318500841785465916012868635572086799048686080425899416482676522354802110302837046995609215516225220297631723239454324350178344477804242876867609090766893601283858708864291043650921051870792131846710159537442354596351203670003833751416348231631431167462342247890756210053684248588247102715906271236827074821653631393134059686550442480009557352825802531096972800140184634254907930410927711789926980101223950018236748945260720536651901533063821674697180051116854580775042671444012033330133944245603228309828342069421377551298374334467231345199909631092973053556955953817797496563, 26143669182342255853219265936362906419283356554965128625211816418180395625967002393553516256350804301266234400954628339614175980045666209676654990776582984426841057095700162440794014105048783838479763669367972631418372819882502931283602508054739311874010052053862614259087842972348846781970419965700528049402882813571301122364512053713522760035446340285704084180504610778875245368367884628940594479173763097406090685693725027956905000937024080549813083503539722989566235138953204971306433430416987919335637566965139557034945330653578424942061715369154488854863672727851917641079202291844427087144260605266586852496961, 8793902621856240065791631431329623753897557848174159883422102042496572273995980927531015293553552263133897057409746715636865311828803998944416908113409049491715504848537512059953664321655575107580765317542770144486800940988012765850584941305436493636972244283025904813355969094554801229119261716039830551362280969758251956314466080113852612711559959645193164267392077206445901529482311216354106407517832705066807283044716347999996314914217190004633931088306908092002940651718321441214691824840397009461288933837415156277197468712134810298375250776427259784823889434098262583501310893589489223629045587517372752273971, 14892680669767106404121249820129219941243419138960677555175796476563377095879528949948151860242578159972029717549446383495321889814686194592007673170188342386793273597537657268723564052078533733817300614571431068190725525255017150858174893235643759393233373449493716988284535400429105401328469734506794337871260157186497108488651120252648959976340450278582745427400262750041164888843760481494315213074874557928592563352114802739525465930043461928150171912301833831782796065890429744390281827964951362665296312080847980894602739089961721813076411136574275839910746021905700248361087814530330065409246535566875842732420, 7555306458477834614570741791464881836972017326457833445776431276591970508847627123881866747774129481373758842189193499965352048552719641981522526648008013005530033007337394074654599895143355523710479347600430267490570759245956529808762522192589351545349151888077404256064645742094214790256807481553423868588189342229170657039950151991885778782659911545655613074870088063414190113123588605690683245173285627434934272040560375386861296299743937452116523067994499172889732613604226474381440035322219796407695412997199976044441693181137052249191502626057228419420001482482032591969041750032399916060037174745548738818324, 27753049013940809974797416642432623421718650357500174042953108186728483883904917261374856800547671239010546421731921568803698754678691504967515932307384019922733092283764731014777750011445813324819270948941827414453557029100414188241210790892701969561598877920707592320127532048451861423542945825017006897117790196522254022648033006089315479129520111627631627539661414287912335392042089523454332669151932599391095410861686942424081012667742183493375485930933955588321467555453615677457711880726787095417029849460475526769742774316258936895955247565373276080304687489433235123219142573964692651746274608546228349234880, 11633083764695977730569012980073574256501771849186660604317191257574886776959525919446783901920954367575115822087750675376748689398613378772484640836093050162844925581943512858913295974277592186530895613978482510964991284797141108297861048078237631398377844682823396130425953241760707179791667795251657182149693051708292900789818168991239761603917214163339839291785844537178496051458174354617479648129926572902742663271119414557834777085919410225060698088353501782807417047808464259079133614327726159486253402733635758889999075215716609556653681000398315689510180434284254538941597142915614364577002206688044615948907, 14356245846415433387787876318214239140704353238070358708358444250232978332880074581566195738440489090348953376869953631208980279831297491219456036974223338614757408387106761280143044807480742770073281428064150201236873047229192065964835485430241209877848375285005023413011611291305905754651162662487602484715810732822691804192997118722182187359705731018599204892553316792817687303472348947025997450064028087333492236497670241126963304654659593408098452128596078323455639780184830634419368152371819714156007096050879159622361907345821665304948624888387435120359416742043546039736749014571216667985512026387677365511388, 9745613356768798274197589843795010260315822122923011282187529082863330295425251005202273271068951781328178058812959373297319207066866005288063174449454282783685548340394044188708483110042380118544754485733988048580022226645618992065440359283399897102406752359275687645025047242545965203992027716749329986431681093718913724564736705867059535053683131537972512211851007149971415383461456889556589279664953428318279943943912846089510747825812954008808706269640598069993635638614897561915044556324329934245706407992558213816841386671942050026570706711787757616443971449478560980322950411951740173707205381797706417303120, 13074410044619096795953071580345231323853876024418598606264365173289638829909745305045486910374784914820344563899059579781082048693706521831736576051677589246035940923295539185027751870435065869452998660203162283981122489027414654200429618918473499871706868175063550117323554780679505032933249439636588581459708392274052552891522750180773027184704636683158507843646916594930046965117746906619798000560663838218685926121832314947640536724847534761179749566113441721477565325163421051108295444486572187165314310902728230353153565667936098613694685562332155209580291342030519064864527857791054611514547914554319151545786, 21082118099859059200081974218874330895931896188742903098265345912657892977034070094840354264230717015533702204252817041632236788151656959672632102373428720331299260966137678104451149235716450241145471121770994897229685660012072153138401205920633599866087426730044061170170613867999722715055058935264871363850679774763936111445451097120407818046636060892482305269069223852064845639125042335603518932729856302940131749153187825925189900618258860312698739213772221354640164907803146574720660660770597281655211144721155118996345694134990605870391599987340997695901971509317164235436567408104248314571258511814495277895591, 14118326352139340974045544828174890946184860043309198817155329881671840998289129254630209492894228948118409779764926585179680131620829382713665945177925910088313996045346878608308227933188342614305996864262444887550761371285346911865490642813584000554796055465166826597733434007715435343687583471183815527988352107918529034905635152746971146761828096619418135174531038674974072733796628265306163906370331801004774373026475559113483512069890418232233142688467238990853402531817788574608792798141355117185624940181324158162399274721599321414230971072402435187072439972524435221368056216549967862211031860190308815172807, 17135860101666533596725703145870621536898264682635633883044358920414851907029799837354971782701685446727265177734530084602742013882735454640133874728250883102904486619744978677460186708767300011435955856424075817925522334105335228293602748038889750843043056123238872758444289409127573565674935410167106422203543779372301417983101015004707453953661145728093124826028082171765580571503848065345977718195428290373156509577063914423172468934586676905032043820237667125018558667049592703978644215636212434645109257995472099768769551180619662645889572665186818916497022536541267034944379157730457467020743879887350378227847, 10230092645466382284797265274724930790216403898154392286241546921148160280735045500181767872568751916058957139995736145814577159187733592120736147183929590911743676225273535324642696750162462015059919719952657772376671932744931478323790765229071447104227317328225339619525117026536615000631431279726968653921924024326063408877938084854988029135254444970024127341684878463968511446866529879756464362691724713083088577976691629151765802212293938078521429050844796742093975440554901420412129593373949637069291537839402050252594401749001141363474704890729812771850740259593203314369352800891371534966690591918849934165382, 18451752966977811577586471438818286705364312609405074615965207396914349793309828316143424148623074164958998640535852677675373066915923384470941143598956001766510600134036647261651486138864409056849493804910055533748386476785218338105050612580576587274192651396331631253514419568838557055448945604742417562201910355410119138612678682387615137612089478825138271462818679243597120177312946553762623533507969079970341430825918343241807031614286380926310649426056864866257805985407003599536367995317825331111153435389935785838142143604335304216172169794035359370210380218272203822093952644569877534254535101722383307396008, 21262313535757497067300540374126866871878319425218941288000977392263540817664018212972640293722519465367738738479103854621382029652050909180014127162004124326094023114438163745770447452307203092714411191770481679992163827261480821883267279311492385913094539053442609973962983489678525592341562449907828532867421734153788355087518067908094417149957250114158256282542484193961349148365561037653070371330565343353611215253927004715071759925060524768779477508936167966781120503064169785503484575509477573559270171328970503715819751235829623296928005268746375014935538509637030884359046182970971712941532638039365274443336, 14216142423971403024784527731692845734927650986092387613400676060692718096553911580298993813817083651596494091984500799082028719317510203935364141260314104931784636094509489693005130353230971635732838143258386760421175843113317396328889238811342222343542532564695749423157384268415121078853095723093754493029503617201901418120319881779842451793366834263884452667082470795589441479281212366255750551672798355412151371317919867792650803726060555887402079031584058522219335636562369097506188991640071274483678119154601203031609394529415558779733616966736975902689426235805574646732490712720782473495446711092382737239841, 28125855530156848233959297766909744558852850097229609104626966259099826231226973595149895575172325103194053084708479506234734145098725127282381931348820532536507740218607003300594879514980068459757845229140307498275061580921907780910035032561858907374812760247137626962224812873844384864880539483165602327966473963297411296071046449687000725379813677581530819794919406237160792258646665323139789782742231457777048900079366432830942562220744272133233835803656118589888773755811463943144336653724879902375170699657116833836817814269315249832867991284083192281716611159516555649827494620177483055408715435552225080772052, 21744246506054233397988045508729748017946188944616325376377076969022644034492469236887620985958064219506017447945513199008124582665907062568303983520453658080421945751070057424141644118538323198076123990649930032528390510918675901993193619542333156110292913664812726808528288242738974841802453271122359393149915020273462841631186925038625172559420715368920337945167195491246189286490015725771475908344600965611655345907463650067728717549050444287880415181322915420464869069645562143488471813036685436548718974520115670229487167874767920062078610810611535512240082829770276639984624032079650340811672057100188099339307, 9831014383414970869422845188318826211798801182480862367616692810303867253828877177175252885748418071211157417174858473060447743818704336925230442300567812662303693385485235462167227489229731959506477720845342023943810281418553769188481669598936189607860838901999528629104110915099412450059828993686142323378456686064952319401419282713714834562279238021358095793314331096546730840805281140394306863439831077995946528865750945049449151664617561260714569038779714151200319492218277544850499265886433672751516848303158690895630796162415702430115769604369144578989918312894065036624689613249480534428415156083055373661549, 21951639848929388461230874984661107307622324681315817285888023816699139745923959906096705434403583950322503757145996921529313545428404544517465925898185502245262299364628857057496857326953456894289275505138714283767115141402129168110793259642375011757483024378472009080437461965310107125706273480586330321439518274863347132834906110172650324409313140837507583012974323115599019924244088766364916149464436169757028403106430750482936041675570975029317374705919661580637701073619584786496150305360659759229067940732794347790321666706251637177374833845773449943040561411515942267539173761132340656917177933238305377910628, 27282166646374911543734744435770018950130522840824291847254224118595463118913375958297087111459589485092639117503091653526156276110726846760530783881681534163793892700332508810543332697674423487090474007651569522643081494293248377056528349406341216575997995804987577268743355660120434122455678138846228380982588090010313961926030029930729195244520665628364578275233496485066742550250125922846216002904953204885304266124387995518913718273219799645643483130604874784071018998852009633673846382700334637273689432741176475455902545784986043511521929455019874361695641184302971095302368412074337404873971351215962678860305, 14234541514850490580418846976629323399159290006417291277586005153483776368376361299526117356755041783164547723349472262177443793534921593011537695383777912579588644111796362411517316789651432305359157455220211777852653988909852727886714228145678666858614455631360304128991071064237622929279592945445347372767874598486415956344655151133864471286663094053137931585276003472840882784247496641459892442383246115545542151051606604193172086125545509663548813812390703880697964613538658814744582933927831354693222994243718082417298136860571854402699441906041809675411813057922642403963330105674979130591661701651010683922022, 13207757965302258214166877355659838080740237971678936175277630213935014895994142413157911470595898219559992138440629341846248888144344656446074806622819543579008082320366997838719909997770609686724637986989475858437429725756213265917711586866764631299394045921894194929806003631323871812614182527553251687678825867698675716344428388075710016518824615966750559079589866682382517415825781486151370861078987958798587026964714079157455613704682186190589151823463578436638876350068735977116927685149648109003445848110208125326828806398652591969943102859349883282905787721208965727559543311979036977739752959228282113529296, 3279759620115776042289246771240504540019334337934813864593273613773419872871053358425960362045590825744032049849674484507185497663278037051964902484189551867642833748949762262134637823153698415040770575254958339782694768523892602865721628159540549225696775996421305370448644959119280235893687566045241059417657139473360432050520340257908317067771717958904913069139579792414478920712977369524887442949884007269319011625369649784129146810431846462466649340515612791613792565849981801739356324964100408926354298561272819093646238453975502294684731717300990239225495790063718205600805694163912023563492331610602945065858, 9362730119042940314233383246810088609887168882898238606774947766744571650706537479160785749609328101454779252642618932288389256458263091002055629032866735001194688468172239341548438395852546377846631099319935593330617218440229480839297836952534477175162111118775382457875604389620191779114588235775319304771940517116986396090423618123453901869140251216768668973045156257876180528021373777961682320241111739384298655387485710422973151246009563143678496080882308705178588119758966512382340970752249948655894735446340791633218968830964718832907149785373591653445617368351341392616633282908083764422690791172303772674934, 1122331994844179344637772355337215494853057789310908722864275569520424102342443284318409085459076893683385958440797795887729105981619335411602569463917751124433548158162120287323719415900373853085894166448690811077418131816118533889953554100854420280196244039753029538801906356436387238387000497747609860890847486227117635108791930480785901373081530509049041209296030414665466423223354825602064654318183594906726366167469450977106140456070386453976707460149424343271235483016028473636296090794894726367431614338455468101508794120452906864911807081077413126005609564016495112826687898659706373991852075102652047021958, 22535438150133094255206218064298615404669808620477310473618781008113219356229037606999317640829627282629677311518074113784399071298854956866764237488277432116158870823041442143625662063555780680914994677782446464253915285274511874300675946528607141688137340273563047820453464441550822132255872928469977160883981290034346631404612236252871932854420873018331850090519963987251095779926569367524596031280765110247034963238031413153286723269536825729701678975480516020642451526046361653144795770280410308769601566770608559595824304654716151674411315965629376829641455411364959385340930214749224662746784912444379083040027, 27108764684214360050343624743289423371308590167109157341816098457955287626048255698303372900718826266403308660134360434173264890953340864859021798875038395925294913496003834289583676005495113799591667885605066092102923548574414936342030956824008848526483891765692508134824852650702580222978340035735296847410553208317349887672112425907752480791687405799299453231786378158229521060564790436866716037345189096845655558209020932457764550272907082929246250476856656374304192414555803142955645377588091434240725224279316894210422501981383634770499211820210935585794908355905333162019365658618182695415888670649445584539874, 8559958537332873537894039279843738323245116593425227592847309780495317547663788847236444902778515917038261003391884665007058436424867078949191680922783489602742982763759147340518856303300516555483952653519485506576206103717019239804254366127465467567970133138326604013803529318706139370578439390808638374188262174833010533569419442247241974446241747780100936008831170324293053887284879962393885565272710856894758247375944095319551526492838775429634219166902415991113177313227800702353129339198770198753512897490331385862138982349984852039181121616109337667298804105322557075594184137807569757471856849266775339843251, 27626838561402701586706090686459848728806005207196816004866060652344101352334928335939636005795423560341318654947704027040895832803828435019559141750861442412060247181112453448367270747989475150100200965924052872185985991622846392482630579860918426120140368638779901276053276179114172856167829896515512931276647031430926884226008096073002161731762645008889561663615545118758101010331076629989604903241638684771792893541056975073038506930628429219514176767162000491211435997642172466309425731012094735146167928119787268061057824369699690072226210771724812526382542853294467420748632671841701103024454519124900369591943, 19345222174574486689463938356051625776503444622091950083250608411725630954275803502029052104526881464341201143690205494403097859718028938086882221191135634938744218057553694939485690309146321407892426846781856877003643839184484640868433022122448281660957706502237589506882304726099622656380493364574526949090612131708704200883879594689296769905700119539988680662071932465969613669253383206798945676398839011627069715523744603052286078814343689219402223029884148881214187056515113213703686867419691165128613087556019806144008989576043190757673841346471448492194965877312707928206042864925570520435424351859931342136586, 1035884263191670762751701007885736472153174395955923268959643053140222511549384926855716853471055928602281064059369460795421351841501442868224790727727669872512347501111384648941493497444036730649695718869609870226041000265121843340801144561494281065332674418388804429250282454454542246772607629897961215232154824248528120295001350755568729810448634225130232574046261981439188438830144734674101969820305269866195440167305359212133832904191258612434206179098933716117764842992497339951399238145666065870307083535653277008325874850052840769086240577962373489330854801945542133597284908119351448039968991407105286036547, 16418451519097400599340416865375667330832198318008688895042253784283167410578287057408555576614509861619550260463568790922536172670489096236883873156764143795958052724804622494621269107166388287148286708092897904742051025811043138491514081955068037170774728997980683214240590247612173254897244060962635647145389544835821975113644965877817478853245566757233571601068923940135524949789939834407492339871445531417743394411224685200683974266285054703515694592053086525718220027005072311997098877477118558475907524578159251942667009998727309627733048866816616640322865762713569081778777415870877515540284461315275029995321, 13192469542162968906334035790249481252226694762299161522575540509396528876762286669826777898084347869999882517577050099981233218064176150709724589746303062935087939736419700854498543643074378225432667504019295360791343131826641717808234690081515319500186406458972955356942092827119412830074237831326620961747180702873859084511608782685232852176458374889065054624814624281246535529677041063018376367543757045125452332056583150551593604550326963538951983809891443012752792899764188830162579955401375156689643156382507977853000753614279640213393453671898679012692881183198135931436570115095900648348580368661698916467738, 4456617429799560019467458802874565317065690246708918651146196568420064367233524631509185582757281190625693475672012780710719157292319570760069377544308393310777168007063156935590505636338017757804189687814053782068638409507952568879871960468785449188563838318837652237617288956814995925239914493312295525033422687719824101397942210448765216195758352858659875354263758115275198722790549301656264931801922274296804483624481267919234825045791728416783815930802002104443765840255949262149064590864265463893007136607960107117406484825881468653132125653108912746984603892582815539441708386719046762293907559070176387305558, 2036306619714661975208085313903627253461372571556329366837922504159549282574356984264023676687318246603508092126228603698622020434136954268839347158371760476518458109358313308789424692542758012751537574052915254401248600997033650664341157016081271267391255107355410183466965526854007508116650448623433825745306994021900382265229034311010939065542392460294572016329923961436928992864443401836566735449339286550378325729316363647063663446607005456337986033608671779846101207928070946756410835749068298116518640317046530823612162599942245556503540057962029451359027650677830840898369551644809141118092002496203928643177, 21742675039237337032242744374154974382209196791288792156900779873624596165312937948586317322360479224825341583943906562897820735778102416962891531769079305300431702453459709840912269190560177154072792026649678689360101219143349506234026827935967988321565519958439239350115672968283715660789354334730981866135357152642027081226945379414789987849760945106702024419157128783890039609461260527890921250284238500044531792511784709622179102112165963230456174877091110174050718540495262460348626177982615458821461855368144176021047152073136860231726897670835047288754869953891729863150285544088818846703863180103417970707769, 17485698829743330590136014868135143449926503021735113783894947342794446692018124727529337829872591274690205812693084650239400588472971004445563061980953109846494064672828934864525898142275253823174217610636028808154286666334773515495402991835743395676275522765188931443977881669674335777217851264538655635008787270386374701050970704055386507485084831024959323374193108522043921522648827696406767411550868834165059770056658778082972024644436285926576271000136481058818528828099434436737415094331438970526021284345853230304553075416356028532775248439717948654874712762404347824976258665820716424989761259376776803759168, 12619048262369913808290997420968422727037640949354467483103684419881609194888547956737529747571140699122170157566675432916854570522513911439266726011836288899172501945653490395519932715340026966068085472771945063539194493083100335359227821634373424463102116832603253934032714369969989521786182218795207256140176875217603341864947910016883948002051489594059989685835494511935473499007521483669341681541787998263985375677263140397443398565752194559025085233287139697334287951474161818756832573780611080062280102907614041287268330632526084398411667801131640771039477942436777163316089445817338577404477777974745598648216, 20689465943712472355257184711175321302325472932947707209674533194782938228835784795144239883468822544988385098401170433414752296784854850024486790745877388625260390640131027422920809493932383438094707246979146711821637088930976510159209181344282359149088712891200698038877852351617980876728264802562458403063152707154340748010817031064960638529065712192526491848759031219506986481714905845727963212491495967591928355306911132583271217750085817797351756835580872211985600357096701030995060556781651179625628696956220061851467198684766390344830397256496882560080354021760650797077330642490878817053661225671025836145101, 23516918039437692907870603829024828251571998892910241488899816209961364178942070652515829137295359180772966387626654910408314634302580347693783499392366091658661452579206291452847199132149917573651888505741860276549548803660170439810829750728084070736687382793794177221340856677970859849913168075746032119667638384926990610346124753763095360758342138277979776833026765167699444145573532460344503978988589470012241804793543925961469420082152885004054967296001963446766892667408296257757623010025715241834111105167555162067680459995749154650479214411591138153256911764360956141088269285362124601255385482807899373700737, 3422947011776485064276097858224276204483964817494032275779025329493877405044977722544938835374231238853577501208276467690583266937288193222739651248400886304418302137315876043219960202825641183536434700803691767918226957094070124906644611035071917157089146295893565642048833012800714350224720813567415563513308778524344426497864540849908323813694057256217209250761827591097424187122230358872942248210895132799868831176917966535204311164795583694633974668360518448758865796891414465575197048083615184301012766865371122877385941683573419214915694473478638884845845103235764307786965256833641677855394886377151900094152, 18175742357200085111977821836048532080199321036400144478806045104235733584625708095735727247216857853823971322960734495498679598866082263220546195499240803039831714588930925229464454945312200930736438117720467435225488861659497200668547337742752685432155802323183643167013716961027551845805652922287187846123292938274000255548511850452154921060277439182055604889531702890203660162588673635072575736009614332071580750694551151648061632874224220049188789376912733978982634421346461703078324502309439329092829951115015396408675543380489276227269293144639396431923702096325108938692779912354893961133270809680637191193685, 20817570777682167773730428754157903475010681466290222661910604828151972009421736702969787523720332074501559220789677301721076783893778155522417814498811856255716194339282036203012090693944545498482985811456931030111673328318134036244298606383077969950991551966648140170992659370934731615256189310393720185806554425017583056009553624832836012873707066089489124123920412464421924440214687056773615625683894471250635354912756868137546362141362275450502589479047176154124104866637996836021462259680743081958943546214968531106034450040589961390288931351598285568827169712380529712060582740810440451626437401143421580073967, 14251425345135229012483383762134688563346179782044190729811298426821892281664588367041448830542661857324513595997788188740760053720566548803206109623649692131962163992842380603008761564031916189227552921793667315256415574282088843613998360788790525414947915079962783960213461045444355176447785226029634834941413329195622295667702568307772530971581930589528610652510736047715652232094959868355664380585620058532552972006012671451590998772833140376519912295194640432779252741820023461354074523609673850367142429398716711783017158871521973051560247369540190253383584708902024302256634328162613261800261025638268030267071, 2472553588550317315791071305382535967462184655427386356103494020636864001337243268952138805752351862907362036208297265681208455934756693180476407048534851320315913492356653964857864716798078224399091274210568986753831025338224777402329651471657223810385740906332083550196775818673987782257568746574116650528992051507049725303293090916767166520942588684350458445237800565321476607351549841752091655206552942385102661173498234278316850159660849953346084015178018395006310254214113291666031335415985636355415085411562196723651372784717571234668992279318777998329368027337711936371284164242673949941968573480590767309374, 14189486717388355157570518548152654165979888500953782046929979336854382271064766872419593110607615398251964790083448262851560957145995342089767602503254506283595124973805004131004482265713511850078251876828894933504486820618352030695659915023995780362202935904627673879228381218167896492523619627569213789818852093324803744283854039608612161974515363280946261595145549564487435949337179152627405955742778241989679433312571020303898564155316238853963755658850813333768350170024256259106425095583185493332627262846032951346535483072605698012076075276568822737746984601867453638402582324437378209934613079621296905982536, 1413164562298373932704260066552219138595631545081902756580114452114417181170905590533676008565515674837573602650777039660383078592288145479076514934230755325069823984608268926002459657099668719584051148284640627955357455774001096692812848679428278538702916806006489525758545988100095855358116289301707347944044044054578069893915300487844697017010417045023402593134488909649716602733823129440966620702477889461683747236557889602097239530932499691169199936752778209604366509616907358169396732918729744870852569999546524011484509018012766474524711737894862876277611819851078981124947868831931205226367306072957366508991, 12136321070845865571853405612753510643366279004750384666756876152876812377997529846474307370176999780989337821612322930551927996522584637925537962852434924282512411092078920666596932712431953040339433019999967287121741903392102928283614650396141600465389660310869463868221012653132699719316078628136949020887490205842604204446706963376211048850622533026598799436630515673868454439749319743603974388916531721471986348182616220232318097586663956982704648129614752903842650436833357988480194131729327548111135290302177336666358144780939842681680382002102863403074340207921560251132170523765736051911425313198354623436799, 4867895685627314098350533054237648741066563208379965753667112345089755017172572535478770289531717646830719914669023348142711181461880863766419879723140554605603099463614387649214447790095740099554923549397759069138545176968395719875693752606883453554247091556697488311718810033905971669152420857273922889210592899591391690223745883937172790007380929694176481601637642748070457768505613552423086361996738160418039053345535717512303012389529544330270109357133316494321266158129953003891890514995456168175987790422577062931687275784757550841644504324759968137858732024996721999252872044934397769392010101367782852566394, 13823617813035805778704190650249348287735440361294180059235674143591342618511535921652511683724868435932515287678817331400066924565516892600212179337146089321293593988279579787175198848886373991312159369185236190740956633423173890619735953661567028834419355137162424441195841662737845652382367317900397905193578624988610643156558688545454290574203850632050250169264212816457323399712513595277942519098453294946794744306834129008621370954295413548299248541796753894594347840725661556442621632930756635052692387931703122682381307489799672388759003851185260692705046687841218632295899694374827221811150354660862490970809, 8164402904086899989464358286497061710943062398060435054988627760171842197088745075117510239654030021184579449145824508426161337025203894655627680566067124844799738659592425866751581911937735419811776381473580323305993400796588830134324882199999551966982399813024123808524858492015353985025676073064926310173508018996377411379513055887822548026087506278670972754314225605874960301529110584085150565514966009162189870781829083537669763091316049896268818517715735524144248343651478291438416966960491977600587135485537174769118499677396109481862441498787202611853236480928398042706684987940311418329857727393118521555699, 7655062531285080613730471260512305630228850195599489765379987942817454328861069810106570645337456419272056693588484142873552774903604269741519146812986371997833118163502635909613783259498041678268113788944557189612666076806333966231681476780499185518244084212773959525150302636969914265768717104055524663236624319271666881091419159214442669820007979007850073161692381733988845959430736630280882005653832634328604316097775519768813633272039368921441661302986855139309887338091233180639459376122795556902261124136521674413646745614847022756996947811103412960833912595349529373877011519025016562519066936986460665933063, 18635210719857507711203086509743245952734543081314646065099714075240716269616692506078391941968662890977650042080229124184086589897965388046567988786760660210671472117833337157296429671270440796097543491740816103459743380937000825905070336710398137913284699156710443262178286360319799753757715772987137230840967616732512997325538875759417677259601007584413947172217070945411725333691491339783590340374819769247138787929655430564775645816319716601076270311935019893333173195819933459847530839595771832513666945418480063623704554705352669329545665071195819531756801720147518495493594510856397280727134107606289602649227, 22009490859045358206298821639355573515542887868903437043206720635025259243813006172433258448035259251462394929318853850304215109498430504290233713167275825904874765918310238137109450241399075932419575770937193424603223086075454256615539632778061772059160075231991612918702709161717416911299267557402443354144872290116019948316423317489806089101834136777739853120623526598472770301967724326554631213178452843782278224281351717282038309369383762402629431367248041647311835646221178088104048623762054881617803843581878746832691622259685883053764870611715340458072798382612677701580365317677518255812092491906405413171379, 10552332235154288402717561690697320254813629299654963819909929243796756467325911802743097218909522359710117790715306987398806255987952864906265404730916742969640868441292088842470983003042136924185385703387052099809433920492300004855883957488717581774017351845124222544143017354393591592329753330462277488136234342059860670663895663973480847334117012115551216300185111489154394991604308831397726894465823888382495185583326760393313745868157854013606876453145869480634290417834917359167175169214159610637493082753170429424648414061321547354928377802264215703086962721898790581452701017204205024362213563189877148101776, 25939543752073939595675301419888650723993738776229749563820050399779328806607598104646243666365102783534790742536516825154053465342019877527592071360927987027862194324522984027545996853916978545200675137372595287082244260292018237247525940786760451802839896112591907644577232085656154324306824838836054640497454805445094183651315677262271151932807269425889086130038988542992189999483205163243923366232937754834694617414069294922752790568941542046266498648333182434392528917718697192912512925764726687395556373945897168961714205467749385875223953193032528438556798251800753327866589181884491866165293661188435035645461, 6936758592963604962770710695663152410682364505667600595527411109117066338952871909376862235497579300618262169060077045889481785916505357161514906997050134617335220092907687453161004312758383034392312226330867884596709297770081885352990283398200281959426983630593220148821615693797720688402763549569962927222101722905589365565628192590923759389077526440569468069914414527947596356887389910683447457162114275538500313453447670604234233153132911571223416221164987868848316815778711509248151043218504034556636280158649183464419493760402177880914803157591278972785351750372368776003862118992373353103311258516004050850840, 2299423436244900878822248292364970631276176249215058402689514677526859859057604811092751113772948104500188305875671422318047401980418646826175945446227211302759291670597143219647307098834569752481904133973808618036307277897916091013994192893661512256114545802389627848508796183658177291685518990512944643930122303635939322292120112032898557126600794226348961909274651755973563762039063997881552017548402047947876335446363837980793163483533051973886570556864974358602308388473409015766343064469529765104711839414600053737097902553348525315995549750005200204596598736334619776341032377009219568851155329247025590878357, 2491627543539151375784542221288346411205931744578725597170715369845225287388919133186636916563721042389381977420678125981455271212903308157063584167046388981733490818830357121497696383918130130016237352205813999852719725469471103109327539409271025742957175589874000501968763114985940217522693802575165460333419367155611372871850273603667163696029906487102045567629336035056647718399093255561660536314903961808652164016200666786308472372675858596483734264467554473323909427026352255746696496982644340793646272466728412912510600933979429117076787403366917472871460367349810993488361912599752264457136591930564408783528, 24381226428568816120731289619484868364351694964151142981556109630040572798997016780149129475350337214788365396714714031425441909446887797769114305100817062998788969525089086380296104832837342201966267973087538663949334414057982678923810052868540211155789266237423275832398954304937628508188715347728640269814408655013207693443394992221324818764780117757122614511836010280566579580038950456280304828641540136537658851136604404483661616382204784534987118027906385913555201090746973986309805930277905675087491481967827594403100789580045418420140277935187888721891620508833895725260476199970110007314670240335190128027750, 7334697526453675587560774905362862151500015382306508928159641300120546553255665542963006340389489156749489873647937099525768459618174721572640748209368200145938433622952258799187350327006386615163117060212345772236720088978026010623858139732237149028710921410654553805830073301188197269212450933164970680509384982101334649949611937651180921875702475638735238753221678777316018988224349575355143127695673249472647201877917953369602145155853339242429331148630962382036229603415762652900874143059048857493304090675062260942256771611348159780535087701153343678448841709436643302430739361963186920342196846685219483973553, 3145084011914188080894894134413452085539992222726242278755772050609805265759340891865613862447242704958787544866440851547767777850209226230725333797317225802476038030228358683321106398510696417538055441562948785180059679160080727542652908701247599606121862953575374332308093513765074285200893980625934773006154189561422275138020385148288803958022807053495613639832675196839592968098448199317182472475587379098028360436230292608211166957393895950667204633991518981300299059173888003058280314201038366012094115026156798072057908572787864318019049936309353930724419997263170294092848446464560574931541797797265980522049, 19129750728406863878839692442134889282552613144277861803839960743095408590957464897972724742716763636653978646235058684881327511647254205088059440869289160144942896706980805047692299812302920300500606285164031239704262918311737560529834018599310033361663555460664767697148732560130444180319107764685440616361524072621252917688466427863419279181476158173048988846640736786729562206021676206653608743820317286595321958945456544254446098196062847633646762658861329537292845202083424472765505443513064004283020516471759288384545280801918193554436574587754153436578260395241436226008248789962409218666677991036875301784599, 8032841803800369652660373636976665111933233467143380844305750039841806062943807420044091101010155003587419330822604939303328848390224216847208423567607166847708936662640865175515630489208345040042468612881536155587129204333879123393567767958057746884141821510643749008353216849684410990875782957041478907992497435467379398778305325496632009965330240932373298085535760209499825039007257338623621909579456311119223580437024839649253882920421693899515355060358829649287374403141839876577534372385732999946970557115548289895248887979021134896327543691103606398388240278754474487283364471208237194960049973109804457436753, 17275450967178548220370935099764886305950359704630836822725296249434086353395776320389714552944364063807301444824871804651485846731439629267544438402544888066341731163446775738491423886863226207499842119135019868712912085057026226039732208955832159205955905411499677693694717442092996866539820174052833351814547070695741727706637940707671879862653254955288711290865712333083787053488026345330581139199061606175041167495448556134458067048062454813093118110283618890553346518335375364252086884654560643525185474179746412237538596773008910777762938399027760819097636509003839875741468934221956815639162541398023965306411, 17866773147598131255485884775404661592204210828572070427988253700167658787421976978267349624555986767860804602271307381699063951986715221117955284505763900820755137852671029711468058154730537259530198964906910355702909646645958780136273299824976439977535333730176023192508285073152088710066873885138853473132146832364924768773867081409714483531981381401370518053077852519857641980877963901687054347321385052940504485618970209279540441476630353088749381346861544830732508689029618936032662417854302957306636425158307139928461421755668305889967364758413828329731268867015432978330900978220022659598498736307376672546975, 23590673998574398613507924928195732206120732270474522469315711369670300965883620987654439117089055697959967127997619653994387194237051541479657099637472415023123925009995867640812500535697693095732628911471638230679537185175143936005753960993328483694814017251110143637207936096936201307797162751806844213383252006526826211539406379230517640988042139278731071689593049969032147409785596901236944575084768648421975779942269750523800869267685851250586092997541518489835350501082828826258931104383180533961925378223686772014225781931718004913168560156188586619468618181520512888565600480292235612430582281235345779824803, 1793737423889141761759924476601863192456196623721657619999901594813435073045736916589814276872179679911749795632849473494297781131760698210039646883197574744384058562556457765385584725567333705064296902184095718538872273399009656779006276293790791688814616994887173181277615591181712238151871427267370002292543981057567598677859979382963711318852757413981282441042966504301136825174750486730667576685065847872248865674208267027056140775884490226090874291910894994775383124686520693469272588786068934437869382888750766324841324531276199306060883494917753206491078282693894496825232909073370641663470423873711343183893, 4975734740918430691831148628167796443146013131364802182560964228406902821419943049704723057141553057145497085807809761785857686176805905448229415464004499882628808441993438844017736578170037322086623295558088256978568026440602068127860779753711038421721805850243362486743575453839729756581554871572632070990020060665840791724058428356518432926293408710613381117680135589504441438638929914100444038058124694633997760096684103872294674286241210810586023322118699918330610601096159128262832689679652231147415861064740958308939881219544828218621709418058214285307219831971916645861042835982398371718807353720677463887801, 25726937273457753950137390175022699656045307046146620764321605325481603919222037713801170531000468866168824421200974538308727007987230470123630255259667242477122214519047783981199312526773147392529394815023238608980167994087830182243138236927604473448955086890922526567312847736745722016016552312598225519296035575678112612750410168619283641979593886697521353896456195041798531436296043906526389395576491817513476264182244570318951814342809646981083231070224443680367938410132469028600131487237003992202723148517766058448817186318485842876641475316266829504637813226522440976057033274996303474183383339190838920416303, 22350885461855590667974015724593498742140280129294476825410552581380589615049994101609356052395164548267483395229130904196562011397994389019289106785410189815275370652601398314348466345552864736708037946440243296556984253837111085989663763552950869197864616420132785423602829940277183379858458054956217321575492470278422296678884936623596045458879488905917543614491185548961420768004880984011157845802696667994669178662054048601681201558012183869275788170446032946623515344802462821000639027940843106891513520411491825715760262351406947918228111352512136783199449957572211695898840021348439233946325079962809919735049, 10479691983778985869299243489762077009549514516192865640331392739561278072961327635588172899428043838583730708262963553929800850300557563649059867988373229866916664272375607132190089038639713056190935814275791562933814969466923167819347857315369925904463724279063743157428620453598638860375631306380616851333569467343828203796272935284169234353294355260388884118120799183886951674700085594220165724578285143375297173331493655229979867748760214324787031508066796345421212144712286145598132596329163303293582152323456785248777053507523778152517252857467660259244212625289548511083110271241095926442434488428636856998699, 2113431103027497205438939296654579310494763872157990996837326430747464502333160088817588816056465525508693326673524455055462113681578598826748793855727217746670744025582114152761722017125115128497608783870911341953304344727514151529131418516561164235523260396491331564146999694820293153162207934851984387707486355883017796822561433797433911681224187210006358992510899076554768632676474275059440722625700969411133445645023165113900539322360698758009425187918707149890695474004524909194575687349959086975391599491621447152452242366007791178192636283347193995948387691596109639276614176281276618075741167119518400592349, 15859822270252280372339776415268635032195190181491480977985915825121793186263423343463436038406869463864009749115856404730546715251066134820571288324492366563722337191144433865452032453848131594930587492115034276931326585687606552355695151388681281361872004010646132219524506415970786824097227983352246575683315205401348705822997948215817694589153464437850005539833810415911478834371171480515268353583305076910138184090427124267789057943195538110804201994355928465415370531829688685389600599153164585567849530040470770223243099191752592016003993917749082622993242652281011734811034291639296826280644963006840432733241, 12879596294708263759954798140990614730590766745347940529435173144510515921827087986158892789515827464521037345327242512768364043376524884022880416281533593704331657879622857512593799020031977820476676836714462547987391624375072171027285559368112962856530962323641879208939497802915281827005083677409640087967394417447638511807863543331843269811207901123673801533866692618075357439483502172400803085184772393911537539010128842778697917622254746004674228954957295239616676594815975133477273094722645244213591333735328876600329856727847212562182277655276648421564999671572993010559148403933687785975135954888804406119728, 1488926874904067375750484959152891272145455453083181163754975764555915213245246182810476193573817185405417276691036619111756908070052732655808053987666015148126796516421850122828684894797291806630032446691445560098092917026412919602431631671974398012398539654918804524365996977894330385285676403627858352641448260263943490363064115161290116366746958524682358122096047488669356975381220847628541855869473460505587976184706502787066466011699271176294676990393358957761117573352479742594465274557280825922672361313697043833956806174363279945040326504114608688979667640422943643308768408623173660145091611321083360836343, 9065983188070880818452426178305413215794555698200091841248077513593821633901321549516402600968124155262291444407549645433454383845205891108119735522543718560229737561374506394787469878567287995066979474617195633968051886053066114244319661782149626953997385663684137658029452404582045003886730691052813064018211743750438192887621447155326699767914249548700875102617985302085640305546792522685508322409735713487730863535056135531933156486667772249786632814255043194521174744347039784549770130839158613425054585301563593218656195250611235910653924098195655701652909478069828694198569704451681430735773076454953162806495, 27895046711741019858850360543103762381016645411688971938347586823508147222072571256335620040932832632847016074982868953565707247335049028683864448988459474218911520424409449629890409581387073411027854616674337440010048642435683977644612614328798406576948669035625682867879200126086108046033606312133832060151924911156797883715783945672243140207283862911531614287542128868297265918306495115946667812282661810883685215336349742709320111564399587497743755618876322820052810044200497131103555418281614853420974438507136752493780576453554212278337282804011139131371193467638260246568583778958920808944744927087045353372935, 21852737738873958738028027208395925213425587180893575510866622794828487527056251828221879486810591103374547840445172347882865461939541230046427268154026242819451664607689964345399545272992636495957348474798569121802283464067722180309289374347259783630859137900359857491671409211922329025349200328625751330217204798830085991021964065677348089300001150015587000326090540283377243346868903172520116959546584119204554914999658686555987790326969119357961968168904179168729451027158835444958259208110339256866213624427213858033980339004527463786675701487016103748528158976340939088712741479446759161582253074770227063390255, 23526733219863215801711786002214998072189689433369158491673660677177771068585244642012584639563250444525649988440721549014413914682976084863419297094558852732491215807040553671277633757218047191090496568326756324935369780996299200434967247599378169648667783388531071419296713082412225694878532532652906196241213523251365080999728963257040802300780147269999618484877705252091903648039782943522652719049641082357443659273310662377297801935252499706575730760940943043583363983865388909271904286762497228926092648887130309172707679391282753442139865797066435133654415198414472810015543278752806207354901074980425640477018, 9900538671827866715602876230752284531906053906291363053681149789572627223386096653537667454824520834489701395421726051840481560321548959856580234236238080493863619810709867197986406339718597158886749797774813747493050724506713102315210378847926997008570275785792810878003612097286024556030747030514787497369694310276267534164750128250423235574584478938622368208913393049429166903557187543775402572127624462514480482282890794252598885614052758807152343343331384376955707164506990871495359164708306884567997319170363241719409427109372481318985406714381352011028139375273531330515671884730719884752517212333955409137947, 13309062570006029078827704721257069621665581366679891801756885214629068724290859585063521130716737105026173550035216141563484239259729666967128733975423210003036075356471248570132644217108136987109172223571326026685892137538556793792413212139662107711097463223668191979543234123583510046139220785160219568740237163751290764186730288326368698371622316842330999659824664623378209605365829062106690574775524069743237845340486992803388433721094299218163304388348971239851037939852534196195049512760131110235233974748369717676370118419087048467294033090844990602900123341188527324757569258017359170899667129506095081683797, 10407111070076667043599934703233718453101422589262864741339095538340842765818128172514822650555230042194716237845471121548845610000123719808190745919814592912032241224567239912068343300102659166181979491854582608450007099354712202342894682142405884188288811842905454517394261597730942396983391253885067454184160250615023157253564570786826172122788005718451660612080581350675836642373726717029840433469680453285047888618166042113012722789891788880084133327125681452281252220515296812504397446813907973980281490544864898557429337697250154923628276561790510139715490079157790284181546251056484921004475331437621666447688, 23993097007925251432818485069238206556965703264612571199051193590786756889055386769848360600402676220634124608150292185778665773953211551724153365177826439792489322267054179590132197646317842030301895351757073845783969053757724336410054218844783303801220719761751117929339035030399311289123677319490327753171925319512917194110999173276088998368906287467103365349492755802060501257713299603920657284610289246343085876532287619285269339617603884003112663881108245059015942532619906799889861720668623070534178312841755975108228680268826803728135885558651064141803586807253755275066081582406992718919227944919055948130241, 11086745566745834652566478375028336589252778267664282286366923549705945111477717080716115520085894701683344475520314942709275861356186720792389789260468031667883043429932760738635912569148830308313807509247475049769118081220908685503420911371481761000052994934520430689776221120330131627052931990503333957341686052465120952122458122888271891995810206331429471319484448058323727336923326288895002550274578652209109375157569953819420148523797094775990362985362513203942914318227834787920405891176567779980721773774093950747349568069317022337417028626833327193815870840522409735787597982107668778770178800813996409431509, 18887053599016036121678357161013618838393027477952737533983129225422901498593774706591503749627038057357724024960765243773781100902858446596963297369789092484850048883861099844295538344292746703733370545561263374131944301349963764769740469957376515977736926873712557916908738253879575442321491457796970077764968278456531243925394677955662115605903720074735401626965418049985460169196982253113825839073657455341035479136300632177327555523616012963584790241214978897319486491600108762118805215237727911532443822846885857105560220986767737618878903107274042731143645906341952035407142186694743300414078987816163097029794, 4851078221144093459868367291594241467586517889451676720901174917667659760953882385846367980786456054934078963332795344078311957272478029033280910310472883640685284073845355080124631609021062354396043377607768115136682337331622403819220363566829423803941292866133097178855216697960455000284577237514853486381192308405260007998854210612686574518472621898930545153294161032189971650939564627905576293554561790694885473962121455752696296447519417139288434299188656874151017320942136435475801620337444048759678635288846243935566386313991067472670435609367178274562108796420562331056164444778920789629554600857024753950032, 12030077633907429313864254216950056948029567697949650433504193261205622454338565064966681752706340396729370608348717243772261655791134237503601318571087939313691503097701370376421701997657160000536130076639270854218463509043776949340970737629595194775342629519023734349068825347272864243880544924206217124895282434595796357868497560470401377241015789530362839184894516233709312905004720006458215608744676388507303369071681856359951752197720564244999968601772290100727269714642058960903349001756002422164855581057067341321089776435767699814559991673874384425748481465789674594921259030184779333796176070583011714244694, 27797602399802118830472025365939148958144751963507110830635099042873605389783756454420724248731483951522798207240273618156592487277705979173049513577934133701100966996850617940259019960753426321957548815373716079319501068218676913996914997627895359865555884174462132821148875369885121072493884888842559986915351004218403488366223255424002186603481592568981103596686809459705119245886264607190360872055670334753138388861122410053413555453612475921813533082530603914185680995619455999081820565261497709324105898232201777109107270404724669433055987645090004780888953910025635109780584322417209880244113068699529973204835, 20586928783594709807526116009860540482548728095832819817930397875016827125538134555539356073326007982330081197892815642451351965290813895476008692561693049433166898348304463480682708614765591671292825692605699322412861999382842996921855995950943700145140010624563329452510542355236626162055456474063094214771253734228876480933165522245186845361427790497450479197731579434741807606577507957937380395449844633313400573937223444644454065397563027744081214878813406260616272681678885423648893873742324947313781773447828147831534755875820896244761898478934754537183624255612835033466751897171258083448837189789946089329331, 11140327811294623263274042938381539686712369241307875075292387960052171853383872926659820727764419765101047061065339151660815110665926272344822143063631198279764530300286928317066282409586919743550837851960592119185170399849945799485036638865565297201724922776305154593653358259151394607026141773889544619804533138612156035434669667018515049196173532723128754441494928361870764609098095557597258483950533017127090540305667300740694836494399332885607314821835707501610894178433038383582120437250493736686169618568967312214651505240649082610679333182813668411754415508711148716531318456453615560332663738415368275653463, 13225198326935654847621094577913831505298352521052561037824230295146352936993638365310505229608208293126258432646436423283378768016731138787150950427827299253492105067038901300487419883018255651981019335557356974460730517322171524097176232523328133280125887902764903596411062687530206149451073108580598038982173274490715507925091181368660339231912747687194433559243414224981381403337092807193873589016442549233884451368026731545038576430355927104438943994355081822720884644149098947750494086501879635306432896897776093237470848493886245979740971119315708568975721631862798100411643824288056480300849040919640708604892, 9745084012670825207312746435956006624983675694719403682485839093226938209226363513366690905043956946268910151232468864739224303369560046587848253202638172661525238178581616027672971480122417437009108867810725406065548371250870753288040116322384366720135639761829489868660552628618161235588489429838548622367780768778323146900598356261305185941378764043379481157763681431118961764872440530303303387574345867598739180952029668237061330718454132524175349136363200725769101315848332965227309019331666170943402231871661114602708779464812780981577786932100863637303717025870388725612651983185846368854016807674508197430306, 18213413640193731293064744211234468441180370542033858354671888384831258869617634399035599490173965883137136265548646290560620431992221547553534767309684134097123550354889499198890372775206476721585410464839077288594525956162120780439925748884371214022147866050235610242818961795879650502017484135371926516512760147280251962242549686030022402752841685718465082421565331235417472982115676236179709808678959993462060121329307691179036429343352910083594926243442825666717450848088890238674656960789613405603132124324098540423523169518185802098022990902499990733552704339179545883212929026306134432478467184068498407727055, 20469809091903264716857290841835962312392258342689393998664076291386163043761307645322716349886708183640913802963133306298924925586901360503874277195552303219242312392806366017846159256583179604524660320096184446383291305370047208393657679101100684537776183791183317651120363627261121161989953881193756852914915177923618064131985440903795826008884672785454629415520109417629344492994675960516029651822765459565932575154321472078142968237253618249330546995723573021320938479542044101639239617498388424544183635546485647224824843020203393267556486191553525528623860220644802041509843810798357282947899108563592542086247, 14328482516354605011066934428912803230438640057111455368085406025872551415178258694922636859145733184503646620730368493697091858955244755258812111112843141112320928350518528591636880586491968855239449496288286575692803138551630163172770286583168893989619420111041730956519446920565691857856825663731194621720727617068477479567532759159943896280245777987382137367682879060524704222827324341790520210046972749345006669443712634506641442088883558935693550933776954487689356487365988173237635746119204403130220538514970583795411760610861887711931268323951403752483332896366017233573010404731798106542094530488718203435419, 5795060867402191176591562973885534546905088773475846480649270299410301249983876817530420601711504384445167873536334117750162337205169871007051434095343168889655433123305076901244850380866936445194089985708834800347534462092505140964448158159911893625978685806620812698704476961366503838118845732363286213359200235377005729274920693255210560143106958602798006717095870522281463341740974393056507532662050963801096310489678546312627471329139602668237783541214359521786063089192572896521095800665439303361222866285832851271716148230073115126273702880316120459679454453387046936678819903683900771302169469303377809175237, 11140532419998605957415175686088844375830885720297666477015001564597284810635026223519107114541689938709582724493613115589956687472025611175077934608053522684857926072124518657062942162644750808439204499947482912625254624286031812771746318656578480738088530253623590004550923066922800208129823285045967569753830836919094921800602608427603260941006981492041485711417365632741997969913962583907898491015932380174857566397308285681370835984789713244468436258287971214459178825128885567602272658034020705801817530283581323428086285688290234033935537204796928451280192612150283530370938337321395022309916226745465641658469, 19955768620912828769971038618040057963434368481095635859862059713148848683215826866557285002579580075034795681917743306610940926671359594678317585488167435846871386934193239897443744655872073088595559688263433118072090626728382581672671162151265348673895216952400882233369589042648053585916209597410517139682776206556680541919025508002424940461946655078188806215831172448835304371289597505929474607583479473389410500162979845132892888598167973115821839276205439162640542329713987468071529180279003920913591549192460374463176277259780223064340358184780616380152752281326892043208205426644090773657547786779360366393832, 8910019532912763472380614876136513758997464261747455398164477111971186655072344040070331482437378395099358809633337626327621816043182392645821213726592500025750500022018260567279073861734867925089111967277981346853174506769108475120408398276427758318304987037407082102955744519930832631600359982218788001105993828170002052565947333965914147249985922927983476413871259736114839646315129969623555195788687678017056772708868188696946676863011657517910536827738707477397381441227594327466422408811064033207600825090134014557113430712356101734568003864054010929380312694384197547560612244160539924622391609487647050115475, 25035702073785033554612284168061826658641057220805720115665713181128532288500278106049231385192899725205538563872512918745822353304790757873001051184176840736697792788320078887190942326624601353219026144392267270574682894758403021445763749720448642684229665127722554676636718862229465087277909621661377847296991823641584625068253706190803879477637370169437024913303810872295434331808756639890569239789019794848228734202753205801291203511196922195216064204133978667711666848568981097943210952801219616797738093232166006879408997874195836748262549907391017281359644369352708908571683083598402247855095215124012883085596, 19664593289518201193490275514890375166113391638954408949552627901544537885257299470814009404080284403185091292202650541909462803872278164170432950817181539030678528692790344569216072710419536854731804858565480261573897110697649589070148419499033919449141919709241862540391378514429900581916300487733232751793981932012735022029645214229153641762679185779781342184833743495976023429287230754365055768227346220102090180687236051834895073039442766493121632731614723884671965698226903696732050934598769999686869863598902612147877414344371626440872498938913754375659268257115499012463007943519724518959411525623995037740645, 23613609997954241324467366077312263058868722829267911053872475988595685489581613355294288583783070291097168240965991696020337583083399851749390931861700557934660891096750907574991952253216522488550737075006691297154261589123548036555115615492811003426887236325971853593006282703815727236329603481653239349174061933949031880117954515580282730487920046913283924048791351105115229999617819779336341887320403704568326895022977901859895615008384008878794553559026299878732643045177305830518071823553016946930357426672681729229494750872138777699223418992445407740519110982436234872890956037797231553583695323311469799564598, 18972094931497158833066527349147471388202959692586831768637494132580153605583562753909482798818124232816396749347286855378223852357629774568264410739825047391983296560502964651198867777305044718080596951350259795026669416401321035796502400608028285307006943841022254935088367566315107281918663198682596170952762169711799658036957076367358050991719873819355531447026053308975272372612882264793441015865749486108850862535704295780954617749320488817551146054484908016227772572605175700668387163528760237989586978241588415477428983938327503756799288789680721858732486938281486609210912609083890842259780441858656593871438, 9089879396502158831731746586832388209952005852211232094378510483627742657769219918092476583140354461495961215370560999728943159551102471980673349494391786989181631636714679206708456953132837156041878685614680717106851359825750608507168471283522699762053438076216495255786422223511478915854926497662874161372898564788838370406804423723590517352629066793394240993587369777324905259890850394347480952296370681683176124361880370499583573893435749769691841231242586764097762531660714328332861806532407596847828991738169163562467771859794373044187197380988336483873358875275700482927091248097133796295507817795003992256190, 21930398802769683896379173507995664726683086656075708580841007504040973130109742104263119826768693546078608188716624418068760445387295823952845395465332012201826158521632468359234399784637740941815545032078058934401247281751934613440912205877211311432064106295820599405281887700738514388625006356941400832139099797709813420088362546610753076591720168808143692961151008766431495649372345854475613765636522999442178381231433812370266605480327560514581579092438056752903045405800468162321017292955465809134893733862281043379001985010097825468051058560760055537646809446188489558535727033833294845501138601005424786093580, 13915948438293695431721691672451068680456285611206744758817419329159129861911014525681402198033408447231862197242513747817161567602619605590281063951549135404843507222985869162389996675804421732448908985646070179356530601811772574582228411154455218227846053392077384987381922332711930104004377994584052952966006404945999520380905313376976146245954196072110798159126675610129242028624351659324027227330024100848319940183634826731634998699142248972425526474101033828804917997412826939081940290586776897951226613200873703327546638254699868697107546304277678803913502948126081477985044410195251965069203834566565153816271]
r = 93549208091522943157523889855147971756339952408014900465237079549147321642184605352106076825075471647946551417457797445371594401297547607606554921501239662351004696055416766322360074764155873771691904894277891317076059387107629281872952247903070858893854519963946004933092428964179404235822710307390762443997
M = 41114562773057591509703798019081726715938195388792207483716010974789826658609043370184495922299754629166062481798971234172682345725464787827933687171665115253731281252387251668805119315677910253579731618701676377111463086179935234982471957816896707984220800374578967269143044956222576420557100741943571288295
enc2 = 3308959603655783037626701651449897306691054491531277011007239956503226856416291050447522118208505181328835654445067869891209022570372449235908057926971720202776819863989791528582562270047426782371075056370483172178853004208276586218043687123444373535519007051969960162889822736022485151723842157816601130568321361182105375979062860034971261145125640309251608819317332361754077108485716298746870151841624987872455719817354570871513465617937552265477428311051737704837212011740627884815342732601532604444076319807464313504969470749988374578293008881546119868431456512406342629832650219747911308702089872865087547016692

part1

y = p ^ (bytes_to_long(part1) << 0x100)

$part1 \approx 2^{256}$,异或后不影响p的高512位和低256位,于是我们可以得到p的高512位和低256位,再用copper即可恢复p

恢复p以后异或回去即可

part2

参考https://ctftime.org/writeup/21878

有关二次剩余(本人对二次剩余了解太少了,只能套套脚本)😭

pow(p ** 2 * k, (p - 1) // 2, p) + pow(q ** 2 * k, (q - 1) // 2, q)

因为计算上式的值得出的结果一直都是0,所以怀疑题目代码有点问题,认为正确的代码应该是

if pow(p ** 2 * k, (q - 1) // 2, q) + pow(q ** 2 * k, (p - 1) // 2, p) == p + q - 2:

$(kp^2)^{\frac{q-1}{2}}\mod q + (kq^2)^{\frac{p-1}{2}} \mod p = p + q - 2$

$\longrightarrow (k^{\frac{q-1}{2}} \mod q)\times (p^{q-1} \mod q) + (k^{\frac{p-1}{2}}\mod p) \times (q^{p-1} \mod p) = p + q -2 $

$\longrightarrow k^{\frac{q-1}{2}} \mod q + k^{\frac{p-1}{2}} \mod p = p + q - 2$

$\therefore k^{\frac{q-1}{2}} \equiv -1 \mod q$,且$k^{\frac{p-1}{2}} \equiv -1 \mod p$,因为只有这样

$k^{\frac{q-1}{2}} \mod q + k^{\frac{p-1}{2}} \mod p = (q-1) + (p - 1)$才能满足上式

所以,我们有$k^{\frac{q-1}{2}} \equiv -1 \mod q$,$k^{\frac{p-1}{2}} \equiv -1 \mod p$

$\because$ enc.append((k ** int(x) * r ** 2) % n),即$c \equiv k^{x}\times r^2 \mod n$

$q$同理

根据$c^{\frac{p-1}{2}}$或者$c^{\frac{q-1}{2}}$的值,我们就能判断x的值了

part3

解法1

$\because M \equiv m \mod r$

$\therefore m = M + kr$

$\therefore c \equiv (M+kr)^3 \mod n$

解上面这个方程,即可求得k

解法2

构造格:

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#sage
r =
M =
enc2 =
n =

K = 2^270
t = 2^254
Ge = Matrix(ZZ,[
[1,0,0,0,0,K*r^3],
[0,t,0,0,0,K*3*M*r^2],
[0,0,t^2,0,0,K*3*M^2*r],
[0,0,0,t^3,0,K*M^3],
[0,0,0,0,t^3,K*enc2],
[0,0,0,0,0,K*n]
])

for i in Ge.LLL():
if abs(i[-2]) == t^3:
k = abs(i[2]) // t^2
print(k)

解法3

已知p,q,e求逆元解RSA

exp:

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2

p =
n =
c =

q = n // p
d = gmpy2.invert(3,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

exp

整题exp:

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
import base64
from Crypto.Util.number import *

n =
y =
enc1 = []
r =
M =
enc2 =

#part1
phigh = y >> 512
biny = bin(y)[2:]

plow = int(biny[-256:],2)

phigh = phigh << 512
R.<x> = PolynomialRing(Zmod(n))

f = phigh + x*2**256 + plow
f = f.monic()
root = f.small_roots(X=2^256,beta=0.4)
if root:
p = int(phigh + root[0]*2**256+plow)
#print("p=",p)
q = n // p
#print("q=",q)
part1 = long_to_bytes((p^^y)>>256)
print(part1)

# part2
bin_flag = ''
for e in enc1:
if kronecker(e,p) == 1:#或者if pow(e,(p-1)//2,p) == 1:(q也同理)
bin_flag += '0'
else:
bin_flag += '1'
part2 = long_to_bytes(int(bin_flag,2))
print(part2)

#part3
R.<k> = PolynomialRing(Zmod(n))
f = (k*r + M)^3 - enc2
f = f.monic()
ans = f.small_roots()
if ans:
k = ans[0]
m = k*r + M
part3 = long_to_bytes(int(m))

flag = part1 + part2 + part3
flag = base64.b64decode(flag)
print(flag)

#flag{8f63777132edd6be6c6b884d2112229ab69a0b3d983c7846cac0b066468ba6b0}

EC_Party-I-chall

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
import os
import random
from Crypto.Util.number import *
from secret import flag


assert flag[:5]==b'flag{' and flag[-1:]==b'}'
flag = flag[5:-1]
m = bytes_to_long(flag)


def rabin(m):
m = m+os.urandom(32)
p = getPrime(384)
q = getPrime(384)
Fp = GF(p)
Fq = GF(q)
n = p*q
e = 2
a = random.randint(0, p-1)
b = random.randint(0, p-1)

Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])
En = EllipticCurve(Zmod(n), [a, b])
ord_p = Ep.order()
ord_q = Eq.order()

xm = bytes_to_long(m)
while True:
try:
Gp = Ep.lift_x(Fp(xm))
Gq = Eq.lift_x(Fq(xm))
ym = crt([int(Gp.xy()[1]),int(Gq.xy()[1])],[p,q])
break
except :
xm += 1
continue

M = En((xm,ym))
C = e*M
pk = [a, b, n, C]
leak = ord_p*ord_q
return pk, leak


print(rabin(flag))
"""
[138681122158674534796479818810828100269024674330030901179877002756402543027343312824423418859769980312713625658733, 4989541340743108588577899263469059346332852532421276369038720203527706762720292559751463880310075002363945271507040, 762981334990685089884160169295988791471426441106522959345412318178660817286272606245181160960267776171409174142433857335352402619564485470678152764621235882232914864951345067231483720755544188962798600739631026707678945887174897543, (19591102741441427006422487362547101973286873135330241799412389205281057650306427438686318050682578531286702107543065985988634367524715153650482199099194389191525898366546842016339136884277515665890331906261550080128989942048438965, 728465071542637655949094554469510039681717865811604984652385614821789556549826602178972137405550902004858456181137844771163710123158955524137202319902378503104952106036911634918189377295743976966073577013775200078470659428344462772), 762981334990685089884160169295988791471426441106522959345445792076415993922016249232021560266153453470937452118572318136597282436269660557904217923887981072203978473274822142705255987334355747997513083011853917049784914749699536828]
"""

目标求$M$,从大佬那里学了个思路

因为leak=ord_p × ord_q有很多因子,遍历这些因子pi,用leak // pi 去乘C点,这样概率触发点加法的错误,而这个错误是由于没有逆元造成的,没有逆元说明计算结果和n存在公因数,利用这个来得到p,q

然后在模$p$和模$q$求解$M_p$和$M_q$(利用sagemath的division_points ()),再用中国剩余定理

division_points (m)简而言之就是求解$mP = Q$的$P$,用法可以在官方文档找到

exp:

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
#sage
import gmpy2
from Crypto.Util.number import *

a = 138681122158674534796479818810828100269024674330030901179877002756402543027343312824423418859769980312713625658733
b = 4989541340743108588577899263469059346332852532421276369038720203527706762720292559751463880310075002363945271507040
n = 762981334990685089884160169295988791471426441106522959345412318178660817286272606245181160960267776171409174142433857335352402619564485470678152764621235882232914864951345067231483720755544188962798600739631026707678945887174897543
C = (19591102741441427006422487362547101973286873135330241799412389205281057650306427438686318050682578531286702107543065985988634367524715153650482199099194389191525898366546842016339136884277515665890331906261550080128989942048438965, 728465071542637655949094554469510039681717865811604984652385614821789556549826602178972137405550902004858456181137844771163710123158955524137202319902378503104952106036911634918189377295743976966073577013775200078470659428344462772)

En = EllipticCurve(Zmod(n), [a, b])
C = En(C)

order_pq = 762981334990685089884160169295988791471426441106522959345445792076415993922016249232021560266153453470937452118572318136597282436269660557904217923887981072203978473274822142705255987334355747997513083011853917049784914749699536828

# factors = [(2, 2), (3, 4), (13, 1), (199, 1), (307, 1), (647,1), (157259,1), (297617,1), (8452217,1), (411927661365999433,1), (1157516701716180046249,1), (1338688620929080207819,1), (58120866347137655341731972800936634809569507957975183914964535560035157289024176117301658018355530580509171262131226697952255326809332037614333, 1)]

# for i in factors:
# print(C*(order_pq // i[0]))

kp = 422522588482185975632147929645103216180089543839772868484032620301855259044079430236142637458472152787337779544279109415705783248825091269039840404202119229567311048216047356951966653331710686649176005328509793328313264251738045723
p = gmpy2.gcd(kp,n)
print(p)
q = n // p


Ep = EllipticCurve(Zmod(p), [a, b])
Eq = EllipticCurve(Zmod(q), [a, b])

Cp = Ep(C)
Cq = Eq(C)
Mps = Cp.division_points(2)
Mqs = Cq.division_points(2)

for i in Mps:
for j in Mqs:
m = crt([int(i[0]), int(j[0])], [p, q])
print(long_to_bytes(m))
#3crab1n_s0unds_go0d
-------------已经到底啦!-------------