Challenge:

from Crypto.Util.number import bytes_to_long, GCD, inverse
from secrets import randbelow, token_bytes
from functools import reduce


def genG(p):
    while True:
        g = randbelow(p)
        if pow(g, (p - 1) // 2, p) != 1:
            return pow(g, 2, p)


def task():
    flag = open("flag.txt", "rb").read()
    p = 0x1795712A13E07F7CCA7A0B09B33EE746414E48863BD7EE1BD0D883460828FE88516774E44AC3F0CE5DA045688C40844677DA6D38582AC7CF2C00E8724AD399059E9298BB1AD9834DAA0481765FFBB00FCA71BAD1E024F7193334D71755B0EEA1D1C761E11FB67C3B495F8D12720A59A8AAEC3F8A59BD6BC45C8C236A29B74CBE823BF9A816556F6DD79364A3E87B02028F9B35C5BC46EE597ABDC1A465B9F41353DD514AA5B91326EB4868BA1C3BC8B74F55DBEF6E59BCF896E15C8400CA6B695C368EF87CBD99FDD4D33F5889EE36A571240B16FFD76C0FAEB81E4550B8549193E88CF630D2422903D1AA08CA369FE0E79DD04F581B7DD8CB1D3F28F9EE2583B
    otp_key = token_bytes(len(flag))
    otp_flag = bytes_to_long(bytes([a ^ b for a, b in zip(flag, otp_key)]))
    assert GCD(p - 1, otp_flag) == 1

    g = genG(p)
    sks = [randbelow(p - 1) for _ in range(3)]
    pks = [pow(g, sk, p) for sk in sks]

    for key_byte in otp_key:
        round_g = genG(p)
        es = (
            bytes_to_long(token_bytes(32) + bytes([key_byte]) + token_bytes(32)),
            bytes_to_long(token_bytes(64)),
            bytes_to_long(token_bytes(64)),
        )
        t = reduce(lambda a, b: a * b % p, [pow(pk, e, p) for pk, e in zip(pks, es)]) #g^(\sum_i sk_i * e_ji)
        leak = t * pow(inverse(round_g, p), otp_flag, p) % p 
        print(leak, round_g)


if __name__ == "__main__":
    while True:
        try:  # make sure GCD(p - 1, otp_flag) == 1
            task()
            break
        except:
            pass

# Code ends here. The output is printed below.
"""
11458633793664664571721974078540329652000173198060387870805422581890021230162965047834907557593328106806100129534537689142113132965211275927881655477132537375636066335801350556965643654723442126541163698694640077491125046683174244446465808447655360233682499276315196531689634286081203361673239920530695744585998432955984816049448594928783978477733151296226579786516015917666481393360958099302267609141375512605364486138005423435952984584332582091145633138121792366490446068083882264291730873795810793290699194612764181218494140804680342513832061936858438676573746414312922449966568363220209965979125507119635057258050 1614819783039842002931282181135979846638110874919962355984540361882479700194448835753053156865503230738486370220975364080432880308773855801127776069525305953642128558778406634281882193909212138357264027819568441175750009246720206115696349150837624361520455091235334609254130837773916974726082390528469579777377100756632536483537203116918533700548850596185380791253423717280428472919501235541056318277773579683767377576220006528503426732338165775189808495258119385698606488091750602686442774372908654677574914288850093533435603737666397082943114930785232078110520242515147563783543964287111618877209725230179341779088
21513003198237597131857323684382217226257589079067014808960278012988931999744515428793220342785561106892406710888591086796511872726481547041599637806003294072151873556216073536279933156687075286147315874265997542789266955993068035886016121787560646287796418462257384292701282246917616517340761072461014917177363826093986432987223565630737590962621754092910159725440712395007245864294399074993091558401089998988649986096900462392736056089987836645211415314633157221946679562060151318293450132384008688065291849171433541748571734038034896800450149889636618401952945087598722813814942240399333981082292704679030494305766 20657995639265966100411507201838173100129455538703742398560836543108063894880859089242036146719248798773317794744963073089879234427479085558209775703131510533518827249235936756010282722812298588637548140214449879461237560494774522139267843451311879511825092524808976701917221596097888654692014520370400893462785484736656165803202684587197300478103015446051534416787387831852918643721751691878777363067071284800188847522207081199034100015756463980099019893758378163637736111247233715752465584999039666931714800613134300194614142679342236035921226832190295929942213779754797501798726758669979363206945813643063851176360
43419540736718237300774780675134480096450218757032915985961821599406946030516411052506254233629931410317639423720230671142492011125775585246331595304099034813416038536590173196428862542778992808851238264243065585243965519316654934050001461981960549017411838748754560214157681795046704667611320038699514466422667477812824226962461918847577887951343391549993783146804703043552192723770724897020634553895134927237034691485117282818877451594467238002467418067794927684204787624189225015292216289035498081382307293854986407132057639152211877437935638842301191116321928028407540748327371860915064080164307187979515971984494 24921268658674399310308512412352718088527826507215330535242412902731772132079569129652101497658016024909960258614645037525916307028704722297253389055296559013506153108092022520234077689840236480706102275670782674809194144796678096672290416764439890618673987293390433734074626958722728318499865682300179126886027024050226248021314376546828226577544167765758939936707340158847932412407386310887693765768138546730084375901955664717482142006126422628128840874507444814256696232468020148334509159906606286974155266036861459340005734541163081672121104362531655490338719821306381053489332770718033915575433883342790686113601
47573588946453502231766626786367875454924693501087425329399885291327376968929451149091299576088168756490210053409931901885827715177587336510927272255506110407995656004552468053503943832737515302659694468541014028068436654572535569793754583617211235445310350675552537148843797422743409432290907508750995482264517177239166367362060158207811879351149475646996053901426732917276276080133803439143161046822008227627871154963837509791548549320385021939598596577507294155113659155579310706829326847680380373908111767605406798668788528592780841542528523379405407608613730428980296002167211563310392987673750465815025861801393 22918750474519177311844721027326703455819436952545536678988419877623168776091638819747919193506839549275908285665679809002496077220652868202099248663541849683734110643874432177231963994425765217393960983152568295956293763620893776009711109377573239359740858349690727261304704254051659941673954530879260624495741035744427891530360429054789508294981094472834093360591072606444642381657188376271821616535712180082087867191203145196646982074726031442864284407847267968207881067102160783539819333344476912077816248717563885421091806959959938611229432031603922052137253274365646000311430518842932778103054932754151231890499
17951461274308950685415410410372693166766726672408381330590169589340445780903234731286761253554001383560468250692007600213415615898110006308593509241538288527454408835532314784887605274188766871559959130116362497478892561978120795799947172816825320780245940091786745897833766238916164781983596007236565701029695765211492880846911609520271023652527949778097452536552153470622669901314227643294661236820917246186816402258084257449312180672911501103869374219144184876424121469976437513918097499411337337537695647048730894950611740997503787594594385221549112640998727295207622801182406663598461761120593448081767954669877 30434732620848225801964515442808417004930070678710810590368281128185421000012618182553917214488454883456335652701618292181363953698105443974164562313453593765445509853424971529808196438581478230431653378949554756293672487097076374170852345116113493898657257866161813357625985911502397501826920834490228022626861924338674807038916678659465007522213238927834980832217355976099336017285381855803774326857601684696459125762149549171000406838025179131566543276893956483981711250710758600842568392037408815349011534863118311158437063096121855767618379502063571299101800197141079585663322962192021711705529582608923637465630
41388801760713667419758636721739712154173126124036054459594872497350684199768685655786016226207005796328765580752984759329006502510625987391091298593505105195664310543253769545861602700536947176025326868497518646679414016115927491776554479226165594319655902545278188118456168936589045421720598508739268765527139128007030363971017201358684127766601030143108360814683298999014078518030713283088289409444052881438671143434013682019482847950371102867487749254344826847822947003131422460090022041012604043010732401185316166671261946769429625632795391320691951185867029636817299214180364408090731289518312680285638367068511 24290751521441502645585302212654559772048121629540105831586831093690598320714305765543385214954127383992958551668596289437844930320103710523267425099363044292428440944203757651544709593257660348622150782727104793141383856567942210215545487653911167406200128516480717470460671464831548323095887398631411521290103612000834383297193099774591049991044435395005944213448730323683769882704551078128951079141685771589277476198508948623270321887998335071980237997932825331110701668243455679203820854602799436301571310587619623510177022108152331708146608300314551577534218672467444003417097511720307172177596785344181591435212
21247893636991559233162315091753890779366077909103578800692810100226778926090662921984418582771378035798940168739161454038103310194402374634096142705241683543731892625202181919613881560150836163278176135050644169838182274089021591707438376073275398140500597162045541263838911827920216034439718051437860010740416974710022110664263215675365305057081386288480418396119340628025570107861595935559446565695880091558673363387265492031594038110579733600622296399806548290922414424351160478747687489823287410922808225441588977348622472324729878504443826221501457165621900041794168426152550147508413578100385168552111995505297 638026935238431488846484728424954283645362882346903283817006011735026717663298264653712092380850818550070554950514073081747396394819333552618538303721403957400136374707095257908194645579325679524793891825820581546737441754780666099583561430947596252050734721117259440765593799913050326302808375757663775178411875606259542009254293188342852910063071707060845936451149789924099040557014658540164345104424717309108907410524836708666345821365582326636156434937115406640627154424239970091822844132428025606338337516824952795996094145232854401504141051931989209909407800633184166546539348781648790937260917740626944078230
41264112082602368858965716764743774323235333943104793771180651930054357253829802878235693986300996991281167380628769714379072619446645362029737611603411111791159198661170974499444047038698449521049147033787351107571705626852909208880739570805614772393676460882113366124205800648959507849716975165043055860596107499972623425309768867973301675469981857493132719597708720455103547816074505704273967901708340492993716411880912086592457225815126829534281774843048586169346049795641629662204923820951793657985559543357871804024018746481274269897867672329645171976503223050251361582453951170947300589385765788620894457100882 23675833667267457320910317589449117566993182251971268058611119297449709445951774655136616706759165888315463754864420182715020169184989689984616109984061230391136302646340187026388077553256025465946878437347483659002495634573040932621774291359757386906157912661300760079907116069989452492127723900236554860343079645847726412338862165139791479145172672639186427620108848835095937705339454573151125767602859746725666630087714763020773424608541669328117805412005545754550543421202340552317890583080098627679791452237679886613707545468088489148056592973583905054952677636680628419241943744177209481046446195464933775904565
18412066213054726278029891367595398346166934636546723591175205694904500511763453562633712180644921338074443038921388922560629518184226652345642196117912464709347834705935863748665402255977309902016692351652852653585875918100159730483226240176758340545682962919796896020242625980770980004078691575169880717064777927233206555859714181140218339123919699894431552984431783258814622991981620733274046355571512326150332159370675294759953195406894408210589565370032715267268643775503358741548973550160108423881331952297758164975002026022443368256791576917307871110032206109301190170737133792908378674828722691261988900521260 45890559998946289999865600647182546954101758018216433219222439972551072175209777655402708642940520249123544446940379828744819523346881064473478746837761338100937373964834468424891406096148982258164801272429959005489196381265949605220166133806782497130338593529524286618077478382967398933424575775804114943274832717224089327912701925798883275368371078592561822449992816976189854161094426549150077061690435499123329838328756575344928796015157306581376229346661910837901846250154645264873336433262079512451389633328405186380679817834670680090541527141148211423133717411324273261186652442436170679028840186849482287117908
11060412509254271833373265506285518974988345863675080408695628169426904882389916767665016438656998990043250074983165772616051035373565619873049068633250783851923882049354194239048102424231349690862218607667026702235138946514282543342117127210219976778622958467755437596924588225958275660824014237876504462452211586108419384586205507780344456425553979136410239546271836403669861756963379192286515330720802976932739213172613715083487651899616770891894676266432158479969494643047050504698280258702586927082635386214214158582300844165919996976737582166201727810758511731432727807815747674083164787316975483026043391397333 27597815487601197273897993926904168910271613628275209893588405757971370649558619868503721172909815598898858073262451549571401221138773919789778181419021307139305774316573269919020270893527337749999152070912866313113783113569185414546439433281597963242855729216502634996135407654885671777612652545393148408064619341683511861646979499902979452084193860858315781387355147753245883525451700353053885352214048425131246260578737085712541142551729464602905727446167533532464040170611930738769490197031009622572259795183981551428233796076623862554726541448470847584783372813920546081508074032067548528913893116822502039323603
33414056333915713050983122659951145779091000571475674704325504075563101378554195270941206554023495675161773465635664807520313767961684339873306205534763298443925642414297564788530096087128893605649544685106849447952181334022660966828875749847350468376611956757533258941147944661661713686735760682489316730004266368704684291274176331182305047607670242326934905908607378921107186105778265104393602644341012926496010988785507090630881454740013301332017150691667663857755726264412302146773121182369401952873248207188785344564319659205144745112435296556313995671665748657449696710295359082806683580310028767565991924677218 46504136583839943831963897825675836175328071779479166258496148086188482419872115231434031451496219726825539121217449077567183176066276779829971035813840398535494005775283200824057665495401177158495828697573314711740675745024802606491458133249064031502580157306412280650935351244842544332366436877596925287665969705793088808367691119767173862933268847834750205339658124442443544150014006021460971663674889490353852334494042357985238366457728555388976975559313089678693947154280657833020999580048573510763142820981520860052299404160370588232384926208018386567469667076223598134328080858633471623448819320609094814787966
11610006527949031735960999359410909789081798015036756122623559024730116836991500774984082006864571674648321701676559854114533277455799818418814526940288115133390809582536901841574667458749564457916825900094254241394527208348627766630949688953766897932293540474550811473696721448457708050790023155228787073285381716244305821412386783551119777323374890829383004169816874582428103291267591609610121920753030123355801716014194687061775025543589975566869533894573621761022971138524113259432225275767969213001221418974223549517506106415500230038488873915131049620497050627207317611550392163254208522216005910333743426620276 34737282426980330062915386971212070691630086334847757630932610984467142619606707023382104858159682455188223773295297051180613171911799399617181672265671057603872389709416840340578133308000591692344173801711724029328086500874915360259962606557096704960646831347940356731895790305705588923361240665420430773981750565930370892246005825995727156227481141009738273782299527887552847725746645207957045208535655795930201201912914468699075091620616521066996483020873998535819317402432621631146857424052423331858935803755489027202426828965133725314519206759044210353598289299709526903239444964987869340637334475950800428764711
47068139947573771279729483715099259935155007195927277470357947671205386897809029683475418362713959701214105705035763141576945982378413050407230970879799671546932296505386659141385507377577960007303538744660591842908765549294611667185189121369035736600301210807404301314252843245137091775232886955766477483109543692712085495176636564749260380327110529434463167661068338813960506905573324054548677113077818532281385763648381955030820691405708116629668826837500487741041809945898456177486863920521773429360427338720031638646564058022822849039113494537681233309267697248903789314742837827768411613403308983974983034406164 1174068459069492686413171395622526737232363009532641168816653488779758477986459305584151136862224791508983566328890935630807590542855696151673957090729122324134119893530856399852412567308595732813577676251906433067774449433880354247476913832786036785291769975943512683275102909160902597059497873894668068941226851872259182725062654206974069297288317734620870852040107189943317044821361592178748508175589570087066973032703932642416768628262699018945200201367874033779407227828700709813316761534359148565917285855879247246385477165650767414048693947856319917284548514646320321253435363379610995914705335251692953416635
37873369282887529143739045123656826700446389765442988934130576775131440356400127572915673364962214527824033040489163279007648854815941886608484932081125411828137248004877175554294758194681818364176942997211126597434330466970095444321692874827860741309459874627699582207191094092445191790484554182798775570793916738784496286104440005364899367949321096396961187274137490318104041744276557837049118626377273946334890648656310765228861829122863361651089418001276712458484102853112990063209908823930515206987131409711189888679356623974119701245065555957434843485247786474062705201201804869900517224604717703301343243211333 22182342154380085086263706696627444576401701980611501058310083364065995021919526816027616817443117345099444374070356835649116342264812475215024595715033450573282130083994056966127549668235941764418817781602608325115462069039978507616969840470809300962790529104148077250263252475923811803049893499379224185619196596878028512552632337175649856487947700235891836889990086749701240421219888032829319040240043335066223066671537185289638128202310477547984958635785534041998565677167541866143194888245955568142594667407699206309442936798166723989768102999100706260053801807820688046300898183770000543924185481895136422989630
15805529960511125817072871469511225929561244953057847180656742803414840341997337539310433608002139027144807826007716903043965684923457855226062388705087202715466199628567439055006366711181410825625605532036881899691354401765227725400188622925448484099989074771339985773764490279618921296202012332461099597954794160621620399434580345663136810242501353148618410490680724565189503458696439703737326296804212595218984998733999288293335755142231608048990800692186980159445354685864684273489470324415231486618945150895548740074452530226466895745677837634601677837731067682108942275476095235805638453934664911455120165846678 28424323901704817246618194744242087808986699565434370996246091801998894744793413108671157532967524166813454938450962530306550537335265882345897107608161286277419019279193944045115528582988254206629892728999811566335652169789294920865906769213155547200265247090608829057360607609608549065966047973085394296210401791754991619150964976377131495973237592459599024931565814182601015506321329529338765394853516984822080664444562104120209100572669860070620039509344017754791705584873592810860019765378932645057074739859170713416148435369086534280494172389388474448862394552723956616357926691870317665857508632378190894751102
3750487910930179780338776754514649152917719883657034288420240534585975119371632095867170464839209853522527296641535352240923807295072678024352569369094332205476742673700848457930602872998317290008540113864756438622667134551041451796337058397959897133422902507219032008851637497249176045435333755057189588900881947309002898070593365183881871169031504760683845440239860115446811069949530814638525837344470882590463728620169678844385877180881880810223897031658760376495273186600639047729668551240041204394671191833239655287509965685039140085534700587525135191211557743402675254987092120434832874531344500230765113216770 23036002858590047653483884464526971812746142148323480358640993797883601864068512879138475719890346219943380251877403428655779514272749733302700326685170365870858063815451578228271847901499815346400166055113488978488720855088357955514245616693407260661819095793694664435283927174260822608975870220556727181779961313908742369116781405457120737264778115085775554997783811858179277010042428834733981466032088500906965168422361260488381513997092750226819111430969348265667033164436891530640948083523057920837341622608149131400149774467697174837762128530210385927206232553173320368251265749489994594502203825171493009614762
19184974287161077295174859034064948692885284192020860948279738905750290640381014074036397722106564218980770569983753933317403150847965241770806285537532009628465849338772381437993345519125715414802704828554810348451954553091215027201915739198516105305678467524245509570954639520642085131350912639597894612366374955069689129727826955451939117326181003483052572423120395808081187534710086401904688695061444344358942945982049773093408441117522705759611985317358807270766570087686660424157073133487026362784472622394516315061694492452443317986138798983521849075628803226113475437299689521095483841902800010692138156822267 34804119349316118857788595978659663877289908978069473559519817540829042612818506029509067435995968158328961508754090800048318429360703007697782974118960206416166863081171968069956186877110074424216698185554822092069766214021097452710959955170852997026627921601825376358626589496111326191984182084903433958675817646171140752204331637389628156347419021707734512695440958969970329395541216376717943824038233988044912744435309703177785307584479378086404575695502847363630349722156088177564813179982001347094742971429977933018681461661039866845378800838243281801647240706489624125172085169835570407302283788738699647990494
22453450709852050587851748393087691827610380674088568589739934558362501320073344381438998032355648822790556306665100551474466674897479537274261833541389528375839376977284859294635175924646281978877576044530934845477194286743053476482581992326678193658499080436923268506870624758480929306657294035644240847333618752577087487424893352616465828706224195322494990096115645871355844469768426574324307202525076621518546793518571262605915357978554583316732458488718545226353151914845052057982389232015074681462855183116753391135144591570820991341509532484547662176270134861381022706524808061129742225770912996004985375687262 27330635396288745424923592026251994100097057892692545074870011760953661188835450304957140250996874903574172410176158477047897681938821576907889073908527517030224705722897034009059336283993319652186862192684820188863832405641996702050243917162956877269531668627964543887421850725512557360626703236302103367235288700217527524119644601324991699943621047729543750965024598606828150637099362634391442569970440163857855175717007706202186982406215759611934047288862587072299936746804686779704624944376814508803777150217898076095277923578419119648909936562649078981957340929039295444511863529533073108067138089417999164602549
17737185758876300308960488057400814487378772324704343002164834043237104635624019733441181627429670153931526566746098144028423240460694338915263880639118890206724199892534980611983618815156555266431103123844391448692219591598517479218537805622621698995934053665941680715610464299975879320697458329175813953995291472717232547053302362858638895325987092105864809025492082405299198106714018395211266422673886523879440603377602294160410344526670204015151720926730849170902414627973521866740041726646048301485066898063328511923417994137377347301693495968908472937854035141192593323407636661556009869668665500876535356525946 21075157378919297186423097193337801234422474926174153566624778467174398342831850998349701414159478325242330111343445740050291906646311182772694256229184601005206719491953349878168102893983842943298103263551075108523562770403034066589105060820652218181219799770984277827651687525354185015276020608961624930734893411174120426435514445522043911365463718122117521322898620470609715545116293419341344325284290164110779464298207992122241519676938059059998028811666500996478709316969538300103629002377072227055523797644998403402118734031441525872324958881183379692465686237064016571347397357704434565695666973566276465112084
19656540880659674823246115934965080673450060218290415127319447492470992686417413392721215073411418721507609776667188010369457710794450469267541535826269646596079982665391092831545333773528844292460578921726029935187720467817299046164686006533769241537693091268627242692885601304042326314438098425147089864161224851220486870102105288384810036621263719933240568075853190848830397711612666457922023985307318535205489571990705410907681477846868546256432934871724058708166908476428650771237410785854181399487408684973211602868522194261368415137950087364122556903356046538280281629188285510976063381975321449102106158079440 9453258164761164872425495118420054657180269152547774168708276057996130042196985847183751279520597682828138025480983997460652987468185273381536158565926011608121489768469461624395471024362636093691721052520393445953361041665032844584982245806313945029571204412623832805737205784244546517834976305600030354150826471631136433502201898420045077321224973599641575974721081629306567824276757382673121440581099385084162321662250583112772207427787252924700215760323646055358862322222558501945572911359507009027274616182270009667890186054259291105533810380270934170518097403257958921375057863864138715822520878849382373491581
32644644272822298631228848446562568355867508537165787395025149413215910059868367302923627698509265644773816424936289812102465444012776284687260057906423998297160928567981463115421532088688391237081747913083285711235681906424180442372408675077610614296936511545559678989197169586064775035498145207457582780333706163627303662430877331217012677026394488233854443400169874728676228617557728640530666412449313687371389055383102157121819594637898463155843965829311771179966231178279455703674103774234099174680496992022697970566486421977722468522857476218660075581901880367892991413632096065073548949390482054965485125517007 23888875837744209358349425089056046222434887004399903498622187703777503094254708768421306010939325539353584713412926478998196220448561308338109443558533566886591725298757748682375049217378632872534562873843265671827343224024577834224441764223720212263155879981240133338747869723553901551586959893977126496007719844558541673603473120267154469542656785286632212091429250280179522123064339586031762464265586717809411435301568654427811134722770312527335597239015407354128876322071656599599858097778726288920793388483627158120256764716180204118956604174762934972017672031652864953272901600741942798126337678192618521258249
15120084416512776543830927174056328881034089542021676286384295722046647055964558004550734450147815508858121996109734811999968209227095653912907122177206164837272262603282562177611628577360168455781513773236187607398331425910926079856126666751366989757616342878132896691944414418901921010039142174403728233627297045012687580751828602796798184636199292223149105327215404907704279097516176969066954052859034303092304203017673465269083910046797072197513021462525623832944740204134013869050139858531390790495647708915191229243398933616087690961836659003907332471442367030575740438562112659841943033559705567149867719005894 31750700531857206581249192870891508687363045256979630897531040738230791126713018965169463111383528459678080395127480831173586248257339900472869894834920128864693425023026563585430190349072807494789738425177437211847152180438571849701520867034493921168321413746594905579252017493891551052581056515243999850313433944947250137881280068711923437707882080198980527601220568901351602343669109820066403974597014808294243505043521720538380077658742431875855397523104401143078800318577734787265405103127380897283142837155372902312615820032012582079995421260072026057829763041758660841336296836012899427556873013975528712835659
33315991651715434592994866625691590681868752911868687030535034592072409110482628685486239588735675402503876791106651077233041839541284551583914837436220930695690383031932164236649802375119973280935056923644446791265568948078538728621708739940909701130107905180066844520625136919387087606025971754336141371712725034192061561030273112812367967284513964671528146538438448866572460124570739941303059469021431281755978931081854054181972506754324829108073082778339966095194765675689195798075576529115650254639669734679740844542916229970327119106397924016471251943787445002189532435682621526069166003435328851627432275674698 13354425381664404245575426789743974413162126913116332651056353809845507541308941687214133367023752496171040847646048316681905956766418921677081006271813628504301958860287808163134082039433764968490928787934609764556007752608003772882588381936693836443777989932595913681494372912366008112009652678988820503708909906447264763083408224177073808339770921575217091643753650809872995627220091828086725708897254708725318322615844514586830245981252051161268418636313492346563239035692697858999560928674214578177682880753018126484361404645027600659928308618804220768291931237537455428072516444722968116488091725129426981238317
31886854712591774988193993570705961148740731153993557912749296209236424417658665626069602502593249984017645991549284615425697719014920393248818543709067955940259889224555497021226999549092878762936231932035527836529227598690960652644501570382256258922303168787962137985412705148384235313819974986850184002374755253471388047914581182115914251717669923809056202543018521310236439680481213611271327723565172301896574240717482761058282658198109825222946113811581243910088812595582750312652415552520676156447196137656163918823221651190108265746806000283396814034990010679097127229504628863972492129559921709655193752548905 34395170607198952132893150958778367572252056471675581406733580245213168295426160011192231858429296427744441696070527044174482580580136340087718533312533659221057414491646771253928416298430978692953352842854700077593520090301328129333064940502698546805889086882331206454812797664237368000852351141472840552832952710946149363552176351076266849272775726964519930794097932610866500855461205491840480001385040886937153238898487802282894785701781767760103348622737208414685637006404330788151083856665483661048541568820059197471297248644579883860467525422582484651507806986391074520300019483939405987796157795784976589203872
6803561490546836359558974678062635266417338298866054353804863270919151759488914619844175113661896155317820914535647321124020716756308121548196563855085405165700025227679713340865949957446789357300686633908855817343317286875461717852996905965322990421460051322152134839133138078153533947344341047291088444102027876939572930690303269223037130014792923354428231804168392267539788493660456081427383352253998785971370101190552440434142642753313131609493988184007344639391948041238921744532389147071744739769469761553748141581170391915576437459197563042062626492572826598760606220781041389374935831118915478975916887206739 16428186742942678656079970598296440551782245404981121841773652385890603233129324741950363996969413928984632254994040413605825644902325164126821795279219465206797190358253569620021611819261276081142817539420425772850769469414420221640329296953246116980011012954096680255315425138259655065817427037546279293183015068572335499490702941794262048167201960794736643192432073721759424299281127031944593241582597207876368730097890855658955466624803261167033301677906133961834389542597946881858598347053322375842133500387890226151345738995149820373575153072287695703860678587229755593439795687645655097764344856361241029849978
27350709434485833006016420742124095208280179640967966994358674137545800885477709022173651293721621109105947054125315292475640164565640366145736732233740297382863594280988453284624279991317593082465612397166208712185139574933301823318660413647503671240631264946451886859290148521477027502481440474133370778783610824150758995239636756637888578976360616436388646526834914473035505306030647834619981597158765398500629838857747852842652609583911543915611501535557106850790400962231331267094419997824801352171539055656235069032797891066630479568627057260347599649230244918713681080222640888766576353432413470134955599077127 13435607982921401763667178687348361762812865184382594666723277326681341425845836245307190609301617990709978729335554834927272839791903290275229198541671528686496434964689027211599926496551330136716955113574635281232642116647708286124853837308691997701725855421911309165413568389414318561355737024365342009571058408240324469519043591206175305293475580062167822951705033602446571152350716420000364537633851835358795620407097581181510269830254235276764783676561503663864066155850331988250342889556327936908323443713346547501098082213420964682418107318517241674888549622296406120824103409048373958198823888712728621761646
35671386532899545488240770694292938408066210836957787180206750642491256244966089713474698625811032487655334346492608636011554775563035476786037556997297480166918221402840499371466163333922820200849291138607871085798532104863025295931133213187087655781157938198348934286494728437065479646927678902040090880288818349169965242349150091562196464895802272430691144980633919479954275713359198467692370108317689044165907503409729041736914278507928077187222041967095123350803302017114540335999980583451899358226323542316308825306403480450848891034654768490144897778335834448404543864336578759258097311471195166357234055454855 22453179044288029797751428598764210931920353449041479140153857500851638819483320992536090578047357540745677508735650433388144289867163174124421421299238404045306364059133766831327404071463154158591839302569657535417440529262188194328772799908464051331262852594531650100934085499402047976529375334777384786275468557248862654857601854796733938395662584242327718664424366871738587453344835215568851176514019713735557282950867168723058101866645641564995178307359436388109157374075861234631654366630326971473095025260901595388180004740179708905539201387945016548463154463616168595451002390828009288398408529910671026413849
35718191586484312288815117431717095200224792296014117245881297751052429155707288941135311722523637506999547201670444063247598510506117260379173525202927021691308476417115591740690054111914842352230232772561376329714551042491814567895989185081204389612243102611339112505032077796221959236955716794907595530285832370381325863163795215796141657253304892036996627015659453173263703934727583069163910331313001076562642853423331431870579583719370389895494862371614724046821045556973536505162139859510072305429898366845549611370074737034501110330533963264744901653611137465244593385155095090234574593513133378128668230238490 36959995194422760602676089835298560389264559442691419929278405553820475027621950936003627530527566042642776935677061442669286379512755680140932369403708208676890386002531181201596501066966850415238349447321480318457294352601437821879298880597539520938881979911501131956385797083306455222825743491722370433544615606013928813940289936745495001861677006977015591985437694067014809339356931642330920300532412602082296886364967333808391360009712445768400532132676657531044419891534492123752145663508766716963719466741930210211345866961241551521429458244709838929688152346245863331108134994679539937468482418834396256857077
3132685048431520944746812710794154677947647518494850937261541044142981177763973358159874343169635166909001632095580168661918929046291482917795036374101881420371016569999174709845707356370625758489265364974041466673592028143921896908794428312262206623486286614484134009159535541836361100784576113048812405384095457739875087839984003110435265699928688569793045272251380938889347424226465133017444243896587157229333937381562077059152986782928431186305956912636137509397783684643360075949476458845004563024174821147405469325329875487599495737742237770290426306407181398404768487599544522042464510289834114135520487891278 23206264985613476910442278612239975751032942639533285502426441578875106762756839194801880370263832826563028768230429091631665263043845893985842955562817045646995928151581909680963489718646903355171202917066275280411158711234455859993010198359142829695224861833290055453238717787161864078206935480308787454170394004152445358161793141375871293530200060059167116740856706473575040017925108118162125864892257809876734060790729654933703128909052717407248795890259974639528421558444560910643646271492249088758641728103074223086248000453488074589333370993215994117978863371711920929683765519036778892105063440178392994140524
37935052475948512364008991295868263936369069266065411738910994156194998497432334366100153286148174776093200774019667595901029943744497535140489592003676953981062316481984051233154915675373552881930916004663461244615868214835611566245023021479286345638529517160617866514767039022318119967777340206055250958707051388898657002828913490729341096684763805815716524108940209701686137997551461558560509063189632562722134670359372668338573979689346209881502636650102108379654700849335149597797749004149497643902004773141760979140259452315331804101004300662746842863473084449501092492751997970411520925927818310964080127585071 8638468760411681293443287087499534296558275502674733732005062502260680916432472915204142752539870727676802272958126128332917046651414163219982380838389382362901923147165245001742461331734324378093810069188437992113976292898159766082760042849237005169951041748945431319365758278712463544990494980174981923353871978247011574605804894184035514994414340438386695336107210540778946553512732855300399389934364991929195657234094958726358718549295157291762932614318707344028612285227412203420120690644194105129605786446898921914204017840908489809666443166967276960446064647657510212161268332913905535307009974046086696280489
38564320738496358077281423034329397308266087143995831451915045757846413082625469222630956893189680348123598114322503072734423835462300215303037456154963912485201079795307819718763935197141301320751385550394334244009112627233256082444798229001367124575658507703157263727011034026235377137359457535233749216192324497188646443483175217327776780335859098454245880730142254709049829506065086025178976034168594558567916087444450413964377951588162173311814983451539195516405999344140669031501949086191362952315234876867171811064023760617810706991628710485328787642784824079314566254511807983742454660153491008996049156020581 38063224580356709761767288191923671721340486907980183126525605774075546073715472036744468357435426162216037614679323108653653414671769206535864524612764440099846996300522933914783254065963771881480335510193108631693058556122431686083054214517809991049635099198446068376850856827954376666507713141001117872793428331426231348748063929825998014635227090952990565480632726847558041696165494945721728792992616014305078572347935823580171634594667813408809664378551218434667124824316091977337295813917320957304248509709207956211409692947600547955234558021424023985972770725818534540302918558739430441481125113518915232905803
42274547214377039179072406917030861032875446927697174943888677780560652144900132585815219473891352032776933389920402111188690909905100295896322431744686659989813866322092868509021337192808491373286381288058186323933419640401463939090739053210693911490439967796845469169766967313512679613927082575431188789317822251429137182967758877854604580694691223738296677650898527227829787854409925527310839157129196479471387588427697824151041666030598731208909036589533396118133993630772404954408274383881967374597906805814390518695043984161769185988278565402584750777412581504254034818151073292849135415697184848617468574270772 17190679531019717092609475318775653100713560977845389176026760172918533402548278156800580376325987677582719545328674760089701473994620467878923010614285865478345177204199802296720938762963544400306730998025558722895879303325940327819559414166029991935010046662584072158486391600353946157838552847846667093699592564438313381240723415997021843385192118862360168175887676171959945433876964057606693370725674729265569864115100960881733162443679934054167434746164193538935527684271155788068628303204530870962303538661071868863788797407765019332807217599838306668850931798746637679455165121184097649377059943349334985795404
25507740848896555992685817177475988133618773399794810465502378428411290892785634458320508771607806687391774059786812597343595556891839891450431875429306142768708267562957850771766284790416603195476093264156487787999292476353497264376068310463836131161221847098254601790157647251961703572752253687109520869098215370844913023122350108216249532350992596391362076766150508154650530728202058993239184063634922926852684067140838830750423394630334612682656189613011215966195164710321346682656682982366991841991455684111662800144063315601950182918709617800285589813183626271927517649790033757439637871046537907844922934035115 16153642699532366958077981575764040119061813610300533234151078235584390308794838456624270183653855573449776409255207350486429079604742588100963600753958764673091077446521591696907866539084410953871124261329947237155107012934606382329916879901001375118702906944812658600818477254240045639850209032124595954175941386769795349102053418233633758949928322275034542526042321306472041566064913741930917882855782443169318012161617628161740457434926582016991936828797107194062414393938686136309676030080142586069133666609876863929795023390418824889106161945607561352855342133126874677696821652263809291667377086818835202102543
39458639714306925469344734847773792995024795130743105186310080200403331963182215255644991298571378897099555391576386433630051500955525092739351751900936128107257518073747799756180441014636772332651662590203348862733645022970824909497637983864641311483944925694916932474078079821740919559291733221753965356295747024576427891132631184549434205154539522515406658345515519969173992102453873030066906784830904891439608927926230984804193078215229767381727464977380650126853440099985314659373081400573634683343027404214604690508667109514272099586777727001031185613309804249578960114395371066128314251353059553907496190577295 13114705649103273248930638484408822195394474275587646642505088540075251761267669649182305466484381755084808148815866578755803860931391691834648994704960531356370335012374897038553330122678715779645192400689876930492490689849426260217982559765932344689961525007685920788707161715926674486620406467004059999762135783687794839237816124911933892577837435308408461624823483986972706683921175440588316167240556816615981065366552420754205238560849862689296959760364978222202169753374972657328913310604586250973087767029062280700948928822251866052320033622848482461873734271992489602823846170884028289784084550325474116040257
34747145890943888809912787490496778470824714218443289427803499532636538800515547456899495990450116783519906678808387364876884084632373040049319467741635854225535152316081091290832233413130744104511233103868819925654424738912091224790284162052127857126860844096471613447830047865191650055946114720478417831756170567098397702282639224875260896325169134699945881116123824218639392952478624234465647098168371366884445200780782912305885991540531646649689734526637510337458208005495450284853960830720350971916520326592742512659078214255314700482466861208103250954057107966794630996593726037729571044151043888979809805064739 28676472844409674819211454043333537417713106647606698799451829687605392925306335302147558834003503209985415212642708554375907037741067740450304465816206887289928066940290070488973634834236128527514764077839423501406266628500954193159368370001786201724438953292896890687237677068989501822159195860808809893471341741138938831586168381217313979674252661151770494606188057099114837219528065154890352223326982606381123918556824532229373486450991804079581519272162432571415905649199330330841279133878605305158968416938387576339704812037850805890032797561183612333310580717047492203927459544995224220342105363572335886901509
20754201605549674465240444060445255494360019810054891850156483124962188673946380228812477885693787986520193496420983909288230448715871142110238055280416134911091206674193862621363520260792421819361076235356212801306588467655368242575458334370909527893723434235262743095397587439153712363444992815750812664390759586850718843605303259508047135464000086461915041512857709012127815746640725791046833870523132600511034409208231333839919471277845450158151537237825906478700793356208313951935729150356152703743001631392829317664210973862708293184862652412968301010996585010986802642721729849039935126182545558283670296249924 20180499883648301699484828721635927997655097600546348002051067999381688765717433520133644606624397479267387074077724427698218538344682202745655325327272114227887640922596442479339680011288757483270587948463002629379455261091240838167412475674192151294162688622218498836197061641792493827593761592762032223260475618582590693740163107288832658627913575151979868072760825229642462642520315041124805781983768714207539906172448573375206245255916774774719175547208973155628228707136350762188586986349673081822858751974361223679077686525903436651060128269631281727301767242695334160555875050947929539704724743067043430202543
1555531079788973196313206303031471158314062458073991644075788720664575301940932503114341735295303615504531813212316310244740800757241920397292414718059571471703823115427871197580326413937430824554009892049364938464158617219741916993428456707938533845124208148046023734631842133939081489618569393735451148273106343570435828659413124633455743763012458952338799594557869638410486425771513536531238163986700878873536838188286082326395072410411716394230545831369133690710056955141396189403746229463960879584466099552368286961860347687456587950702482060752953149045802564656234105544879309990481242361661742309829172893249 19018555321643217410745602538967222715001047633989482313692322581506892229985695539759536257997642011979517232604926254951296571099564730324677553743933878492443326579117110003170117583193049872358720095294678248940844504698848209856700318474350306752885874811010236514323265620564023210697483088866078671274404930136949990130005968812810106336088607991946214262366137261906057626141126780776132495091770481186561568755900280642914099029972773541353073582023538869745224381783198959763747933469240016483141503611608774479674079575244175518693797305660550184251180414748355369878256202212316526770498136002269268514135
47360006689123371021740910621319432886180183076290927991519914341827990487611990296055664588724048422138786975592909013826969664756580520218254014044194790764930884163425304736297549963794847495049996544335937035189916601864888646445792293386478208802593452979726448208835811538296897560014516412675582718240509861355389257964178709145307134536489347473242545580562356310525879023331148632905524463933016655135611549367501981340572789317086414981523064199087671497473235320295198579593482666548466694983082930839461018488515487229473520727140375784242538455428295198369103733073657942902222675948523127541859158115543 22460993921712252772368661311556430365957878656782427262521473585816981932613382273306809020226183198361382975471936456087681631998150752608511938778301159085429904234236504896140014543535779262677711710086940700185137632769105023384916954793569584995702186477666311324608145833913109573172381088280026332238012351194439382768216882595236396095741678493215739072718290258694200074127543010803030677809024554208360872275313853272983374414722330078980659082031919024504380176657700807361980602264725976059757047138930340643942095100594115927340488097593538189960298152844791837472769241510566698789836268529079863144608
42577252771528669681752867547946214963728101837033846189486551974609096056604654268209335063141106973166570908049087115778302243898640260918174270395755672245282188621616954328993712835496296688863735139201201984027996361009167097734997664917989265456572518559081544136820568498779787130591777151939594711281979607891630594025251986829414738518142433400286239459262860897569324029092304647347963095417404286158021944999478088492289885559608230652604125158289492045660310268242893309055952111388231787467397817867845724210511364313820283371945764944953310230031605853866194401733830385734858529356673120153393861950890 39116661013472492055461560682303872061098926474778455724873638383787935289976868104196227732183562046906703005824052992917237502137804195557395431546183828510692424568149715951587069342907039155724765042133033271237767923556688778032408235063942972507451373855354118317609055337499277569134036937728726508118962018541976368882441234950468557759346112567384470301827754140309566028394405479770838596211650066015759126053216431801231796974881955832560408840332832077946972389466761727436759994135500159833932395565479641233051288311070518613988954774142363076843270846879488897886787035049504428700662924723694368139731
20006460153216294485173134347307633858994633216408611150848783195554848364086449244841039118884159533527821032489886051266610495645384971021513259686644185897093397815126535767138141449169788007521645613396468177541361390709088551574847171251948886140930838761262216089120537713075924678736970809351790040114453313285321830166536249772488611938023800423420329864467415227484570437098439364242786599002441948016596722277236043140383235480172581754884109571629663908051366191746771800452246119098969475576883623370470723155913316225170462456101092589472899080996915829470367655770109925717954509942760902720944869295282 14835051112772440173615074090941271382192334689743819078659863615225740247123589096104764423539008003340799649405745212562909075637941444633022147331296371834727583749960652736867890659069431527586934021877767192968627651516430607294288957100490158765701918478043563250224625288494287192949767633866886552223555135159021905797863936319887880510671794977507164007094169528042005198785754614731633783630493196780440964025474028099209587381651357368627644342042259737780612840194151662291075594811266199866938327542293620551318364867632911323401491668295077914733305222505973095217359782524528496098336039126386412237658
39042346993027486808117292536746535757085580025628996590253915431835549560222676873407214767636412203479224286670424558844942940137702516318120193988102097801109474849012606770692700881364263034932348615908574635759945387930821005041625809366128297374885798486686074873891248360826829190705667070235684182470069371148542516991121981532865551864187466435447912172142546888800823175376389702361232147653914123648815154187249084767930346107483502725230923184633956324142861331922060646073238751873904202125116643918984375130533150913129361684299936709837181168304830293043697852369241576818778822172166648266261675995004 9026575158448673981320207784570096598203963935968402005704570537891310273913140244573721496353448585103240223970862189164285414759747221612374065315235290952931640453085172087325237824687371502471896840688339197939405656986605636571014312004280787054665948845075491276790064508730136883660544842024911811020232649034543295292681798947940873695031799137983571104798463839535362345890388140497555385380288299934678676989290616304831652774523335797412283672518120450019456792250124274383944914437231308227701632121251670927387382765401405015856876313895491127135550282203524517751659237380068738256619364159056437566106
9451322234172371308374613340558192645896163443009670073773901854896804798184218151750044624562056706263273575586382485870919828089462610340545622743017234805940962504595861879825242237262928786791604278082969445187917947552748576922109606332272192264114755137741882514034390950023478629637782399776249592331294101670770984880147394999369229230216669488965002010719817394296811905654309327325984090682732435753127407868168852994151667915534709423811188360926736392409225072155478082002869291734622410135280600256213351908444268845850642271096362110987241020592643643680831571291538836771087181799133446782846814087763 15700256510195686949913338482120674471258446877030401034111320300747165212889612627656825913343473426602743265888929674028002343516816013273490164154273822701133182750450639784697694484150324250603699818339120821189566505899936794164298936527214166316268461918789057333706198861476441486277544460211995390486246954103277541574517582775515721651159765477055437602107847385967353801454421768799195211093834287629000876065825833008459101229445856722279369849732705990644616410076523207011593962005674554417811748485944130137785883504118740446665899383278907379428822217817566079564931507865010558560573207665129751607449
26176823162327109944893612121347579084991025739965436850294123134909706519341804031140907199267726950207357878595106714889739457473014815338843548209725827553788594539149166264254882957079498214988099969072205946548967988363987160322727304139017368974094744055601962310557047249161074367080193916343582280807832717915164575096825532449498976009133557559598889800050291994742495124075450859535190569252584425399965751444176246692780638803685316866810100739429061736623909933118918524853368363797478214579951126394524425169375740376093381809700822229275279544885737880112076296748638956310800693935003393419203089287691 46778876081669163974804073046338419317782753483724342531783681101074958337225417792161490426122359217620921694951744505127695889226690339050751620342960745608672308872997300875078619183474762138553746639941584391445381198803683248733099011891809099735703404437285906144796994781954300745131997584686934807555092061303907189209414710707689614631871858486486922236007122915954262540061992716935186027058406597240032000204290985630734239407262863800077830393986182523488030866210122400915807399263153791913677727144069319921263293024938772096354952593843176234430466959510052290950786159125608572555167593643958244379924
15679520248082526557530839586074610043128134687983261924469346993781654438042028777227316565225248908168406085885990062041852598188111113713313603126144569298437457589831794662459317575880150634548862618530198076734806758956100653770590130272273718835711776144318689735432268953469515725861759292320040020826082851745573953179900205632409201787185249902572346901809156708107399800457383002840645579080135688372012616338562469878560117051973476899927210791425635678063568764220722644794639754578321532299774443432563013173784663144793295903874505565739534678422474099267884056336248240719641108679517812589616021508675 26735171189581706330432852435994737661539552125073960678508761457309579268095116918977160126563256359269454990050703555573958589421518345165011370600949823563849176829717954775250477966869763986719785215654186928264726130874910713219025343821758822009633935874541443687314692827809206903156662008014237678419515376023070132967711255191900768073991279515629808015424379832930429752390494230082522564451711350524207138881186691137368247338541268134719122265125102615868238444826303485363287649065992184656176446230512442182177402743140176771265456223157300650621566480745598213659709919940942289984828152528132780845919
33240486422539853372755709571320284670484617665692573175597608994812746114917220616157777007188645555258876046195540795643325226058092919112565656541893328748817563770141915625454899751105099032938581198358862057326700950094393664908928015254191691249065345128581100946177707498434296631526157914282237059389968882370376225530170734319743017848720911348185921083252478783543736904426328200872996841351823275972763355951551141284344435057803834852312169931738703482826181085027058514485872701082573380965760704536010819125689734651366520324440413007370692064530732206281464243098928297880549291664371465237756950038451 24618956964935155621793432374631125401963882855888999060888450426500317536156316233724572186378857906923282579277161845713184669837521990085880400172075489464033526691796065349202652928790643314422551236206982893906920809857237781151044706069735317594101379168630103177358407894615323134485011470653096420491621059777243633052465909547613344358305026572719221043618536753691450866949144517547254013687197858539237870313016127024191556974551568468837337020047964487609432769223071384114355848268959760532266255323205153384611139548882084443527685669595046249511724398040341873795409560716107773127135213430608837412681
9820587231156668060314305443407236118635869741077152492583696785822728644037312359799026904600355456725492206044624641278224037800036653630715959200024470956869577991552698822236161009369093631967238479274498215457572276719333494296774812930510306837494549545041952923109267483904769042412226696986477758733221207013149785048403455179759375641037204603572067730620292047717371882361259656205138084917911104923778823537295636859603798156821289839504293419406662413325237880245688093119759903477558535467270219502915307763682371092556395732984211929543250539560824351944238396538115850568654230542992064390451173062688 10546608682414770740741687867265040079737500037651444273388903918111533911919252580396059675679410843561629834799014133054244497358500693368356861050309006882916276933314185572178101363707464179677216501454270763673070202671603507769176097949862431133144058531070647009627267126462583736059794678046714290967892501064937847171971396108582237017095330546120046644859582447827987819821331715425876467473088396050998131077639696078307034904866741639898564391751584312341486114531473611026860916976094139049071554195521126141831346365994745397172234376660681766529901537219061778979534112410799541927971668758895844785841
30720624945510633196969447299879672705502859880315378765991825482151024787345049541772324291904488563028116166346788785317879210737335033479434196406890596105452807536451922541987603725195111051364261303119708018483114435091779413994247375104094805629102145999091751024410911893857166461871274082719833193188613102898584837484608635197873645891850102368002688919151459613408521870986777607539921942873579767091718494392904826838283717618530048460447327837119943595690118144951292840928660212789905049864317140721790402865706593452325893052339687119388858589557685348223679868148613998372521492455204832069753674698806 36802882485379361664138666987512016952657521011634870322191446120523670847474532731808625220255504165001784830682911512717028249707170114526548977996296655725710564948059058189584764923551317045344421186506442258299899836559926527097542770941068967857273117981885624907057914468424335436688581829705948411646092020142523161546630570903427724390982088674907845395597190517182267035427628349507874446947406462922866423155491336393190264444742171829395209890217466643944376657424242951824539590616909765261170732380543624589991460327954811847158324871668707111333220716434096154990592497171227624718575888106447081768174
9171864669282305897891096738293294149147701851572611219429508505763791032582486031822379181929776942326047964428052429913122031784003002289155234956671173474619891363581484836341586556202018186067510040098639835845052134275056737108886389294627523922905340413781087328018567081305125431528794244766739423369304679639604984858387183424649895084690482541045843008226056925280125310604302924862366035042975465881312152654786617181866006741909225301119404861653048876127850803394965600652906262458893777122460897866265372148090487760837636116966003451269026593439393479188313344024010472658813714401498711390810693593437 2330717692995571718478826244423308013071700719937690962366453190848847369926001891094403008741304120282498440319062933801807781452049531603841043546184562059684768147930340958013912460862192975849385353757576990805113772615955683040519768362014941040734529381979653895148703397509827962824324939021578812212064369237177233472300976314630387396374651725697699166165258031171800587311864355549996794030791461621357071324102470383954232135745466751343454045065099959075858455135539237563988973455528984455506142146415062650571937693995856875278209053982739218436513191848512804221359199586846347146318240565978585042653
40601093000177411547701336322595594306570877843707566269784057991390759277347333746959889289584588201925919349108042254746511777840552291145917858892166273747935111646718110991055734315546653627971599944164213809012519565439642979566580177591004650383612249366675158257928441121430553047253359575692517922918809867746368859032238317265201075453248709310014589542814115888645507151970061157942612512585265694401874942804119593426693124966109663210436379896810570694314147985990250980578606141449213494472497610674834921043761002975147500872047267272965837949191784741816122403719941768313129884242538266971440156826961 19844851671735501105397505348449700455373433063846623127984186131924550493391657858718315158031675985379808588169259808085098714933722219248582498532036804237534767948826070426028088673183473523898822801130828681940022786325727914218118761016793069578367691548324080502191019815037578386623203613924186544693327678212453142101463353370035512016930762297444871541226782815294409609059780367375438460689791303484893124709668252358534260005786487885999239262311063972369241383306205656943814866601356948833516053834842602926196876588509279159800459595372687468445567212990609588449772485454495486644499331328874051265848
42841946556776147807090956181612652893307080941112828593848755322204830959593774686195036332186595891056374431562288056958393317026153108430219915879535909111201107800072153405504277812234525511901172508809902732398161587141151525576176096321198663648412269772326482066377024883241385802922458695745112045122099558856190374268518276014862157444026368139907268116514071012015366912752378051772240451818734359176706197951941529689392218750941485767812203026602663613645818093171104541572473878746544620144243889861951116613021483793487709380855914624102182156785398732324019084569833803862606408415918003190542643994077 7589153613116975130119818894783944422353770814591742116400584678009358760450590108714118935074265273117428839263567464413544319964172191341730996824361248553177601200785567545986678612813326806622034907032298328979781103121029681972385027237006842514413242015126697792342435975258577199489374544858061855575230455388212923595962183110140009259398944560617506457467898014288989413607056639755151786301824064814664360056255223691955442276243721415468044125879448025739857705264664812703163788618449051192523636479999003871815292920894714425152531509366033238301956125411242195899713539001482520708101903971867781689680
16433626522518166481357935079972084587641546119748964572397676613615615830291224504837705400085208927083348456297593440821678327621603496299783130684764375581282016484755130564468708317891168769484219344193652305472482145361136394739986407678726560989351816592753556593276182112761573064505082491093571208663742593153847187523077883488309206225747786850306622827142833225860894595938067982950693813477292033574139855736087112405371447903666169670479882276189272200240393207681702467828295656989042938239006756715095579116933837552411764756518289044699801098147553615760257146649206912605388071208772995754418680286659 16392330992802251760886448021659387544892201183531162607949034437015120025272409481161414839332463455848873152188230295680218495180825794182027460333586708970403555592298540846919222225674238009160220794787327734854553441319094527424576993575291225932805174237065380725472867634432231520123981944789007567064294792162369109104231047520078242619394713520875963129225177962075912419500364678966038384456091687694852693995419877278203239439896971983201869026011877231309657876612759321765756808529583176424621423925406474845461895952805786627252771466219615951756768589883565773733354352924928161689158177311664316086426
22336735345384741243159571706148540992583367369136467763312741555817016678482865806031053587671173400639887210080200675809358637786322195300189725242717811506644796906603006574480894799755242760595114374104191028869086571126470863825301785314578572848363047053360755515310142605847830103632231366947895748349594430127130792852553179629412131245715040984550503199186038170023565643287540756061817121445413879879081519344492803685832061914011809645410419506220737821111582575894001425766816620835386391114002081082420069979751817624819879123118794659230868287070280529902589296803586349399300253351149511085200349865443 34133890820565217234152440633837864760957404343990116102030288220611808925053170002519628853387396711351302357123493196588525366428177743507000591214222624131035051927933205539888718714601386852182382711272272318976090772637836756350022705379037563315862331384587280089464703148641587602484869668883837974282216130643794305364396589509590778048321207954383364416904543848477837441962656875115508536684842102379992419744744447930248951252841054101697993053825917774477872592687398740696789997530624461986076292265404365112199285697035212708602250265526759044209530853134451419228655924951077754591424160132999212389839
36591208633611217556609240176635606766608639523840519839608077411508511852936570293417476439775651523952231388648575055912304017209143994201992473246543175036139867593532888678257103938467135800594130691465281530153471813043524367066886562476596744285365875560403497200686369500421114362092835993374958491400850282657050158882733731692166088908003238594652876267272823801847118721141055925882685435156501778726238379560236536015838329753395137718477312775568635580321602007220317033559950528639423806854255720057881813065054984685150053312383694324859930961858099283716988875622477616684314624353644860380269993457072 21650458619674528413315535137578361000280291684182594567910100809554237108836217593575365250822076746408892927192900600423164006967670982481811325221611201655147647438204735561251799934481917495543552033999491377390835769063048703259187319378171568470828113191725676887145938307502958904140172475971234984734719962329730950983243972764286288394383012817417220342592190444966971443363613161380035081406761923459516440190789740652411475166055560739838586378269608682748912099521968469863215214150358352819888020276206184071372933174219778904867980520617902922955944594682121164715570508186176312601753239340267709998534
37841973810795908795734778397839882083978395852279131056084462090781671589248278086127386206290078342626504168027932336852680970475674159671612742614476622026225227372975312009188927092879238658310979908272583715316209194247843615760095165867407366063303251204450537941785847285878453203972790154041856073112636548466476640348310831679304964454349833074724945252758983833132551005773127904241642759256235910337214532492438749045117081138839458421612695438043013074032503861764984252466343389277338509688510615685378477139035905984101554803907915854253766741179004072222040886376334229531323667381319096706285063048285 7782748046597906319313117022718502268728809386735535897315015386691432634379937580630999969489161991443494752467610843905831825214838818589911637632821156690115878357869266345707659688631818232985546370205701935571955322562449215457603574979964114902409632661077948942010682847474839604069797710821493051524255840800491141740755266704202858997695832152179599445275593789091493066182138918355399974192357510197024454195166910563885503802855890191865454941193272696791866279316495479220965609898101449383025222238758919098826471716666549167710889281159765890547888856923134279038956746166813692155396778104947542356996
24243683868604935930677951158213395919418406312953772098047680033006508633601210413959313033819092784101039912281712629074382423705860283448273672994950819409529867651904824626401321087195156973429353231222717543840993231563218950693113646048488896113943522254711798277402082257373334670305731186207150742427186616116495050923035957454662428012496642132907523126536154046551736872239611922747310073895534247559408452945390377324393674425485890780390203902894092510650836879329248306762311757489064454112302361244478182401589898365811860183002754502649563777917225267769155197363636489728644278554554968695448943262867 23624155945899499283063368066909226877097579638502383894318298050781467537546952811730058482216775062270289477563713975085039123734595535075362452670778758096786852086749002568519104446997457025793854827264938518604283965674486774190475874615832109935305067302944774542957591321636677370200316908322731212462682197622784875059468701984460457789661027378030732005969748970715868019982636949351810138640872800759018967539628212345587343246349754438683796292901324504503628056065208931542463308840157838978068814451932249453424492232450380659423100642021805370314662274543920056394494951112521345377069099043480945755899
28500161978977409269840394599038183576923832424510728149057308302547075048121628319199617001772789570358265343238037514517255869835622510884573006664854642189011299442576861440362504112444753609050724291684918397146977270032339872521806926304532294799270194303267014608435105455275039742437085625138205566354877168187622319183902671986450245594937567090593910866756477536938078589100765194712390242181111222697809617468513269695860315141537471272760854041549289935298941009691107870576416198692177530620706181825333629497228007989247321594138943542972629905093619641307718561870556369416442819939099369341222365089455 42444411026711949141192959484742734676112919065612723299565765075033734538284346775594298567300015443941457840697409826806511400621912152963180818276180640216941866505149545975021439441427257791990322373428536906211514309788974386792617796810277888581132167791543827430480153051016694799455005768419304616472696979946931306586245308339888886191285026120567603706610734345197012818627660110285617292777597994913256676677355709921418834686792678211497891096019239786712915629337953205076059549008308263193253322332695520349454133848013689655522804119302202732471012634393617920243262975423574698097558186237112316363171
22553311194156378714935004108503932855990941289326465447038837096748516731049076422764266614062247250788154460657455124052232695788018790308605343665671700417788601973316240246381774094671948693342493689615760350098917636515662709569304129697317289760927661594783218413337963268998457313580413087910946117019435557069206196842860964640271142620816502221342976316595898654654482988935176005597269917070403178378632475395360680706477065878641346613221063295920105838899596400814499531279285276979238686529972726999313251238727088541287805433180415255446046233861898276321626031000431708956965593906215106891133847122669 9531520025458419973001493563511761746964476752428904663354697419130780105564224074511533517673614495388049820035816304225943414275565274499592333909447740328902675204109203642029293341612161676098731900376053939412850032638709576112729536652604819852445984044472766135105630405529243777496756697949146606800214066344474283365817813130156684906000290719367406049724320891207856347795963132814581732076294868412359920247422735363270489930979520147948601764839819359976946468495254573953824102202570586401101452352433791585792882343714115208386571530443295364040731586943347697320187801775364965653660847673675600169165
8361821765715502336054897485627553862371543635013690972560169453207540142204930893334948185523969107281386609282600831338784266084664735736650040841861669949917648388561256130991293186832483017154198643702290172876657617122484187988662758793867034618369185363330973307533049209401872858873249243212616893805184561054308628155892104153705794182327871030601086951163307886973909840711618868817969279558872706227400420341561314412297289814132381154581877526866511606197759250002016015411216276786869471554038128716976715849798285138826627093722639834978770050491649028219886866155250425132963069640019770130136881118739 9303893227666191394135365423630786887407144678912480620975117817796813171965165238209426540983328994189576314243428309149781986479229058837783290151277659395909594153470559826882097255125988766217285379665557895899504745110453519095418891738125862306892649560771045882457152090241743093697314938051702194708164697269846811251613027005267906324276344700278082701316829376294202844951672672004856155158300306462350895101942267763605146068873002955851154470240483012693886162064096058665916512002979764434378837602071281379708312444218412296294848677923796942754465658209737572023406879024016500492411559829365686515140
17526632897269080407792304110366348285548099230273835509623844022030571700647366303852614514836477006764246446207608770144623101760618202362747232914353290810407872819810958777826897984291454706048110532649521282413555056277973418150234889764864963717433150239393886554033276378418629731413690154421426825836222302930610816499239388516250648557335157494890753050080665705306167057634754550365920063420670943284356608046512722238611311284772387884967343853980169422905690772719361771521397496411119044404101000926475317977281267560576027820430281545795371673385458083140307783540876659892836986006695147156495134765208 13584159323410602760439188922984581093926246979061197116081451017473382903420608575667150522624309967415212384347924114442603869979153591730708245886285160989007676866814266194326787402727695938950711584493001488483599086277787595352233681305513396424414350597715245017493556982092885182855193631792737457721424755981833865615537826767780047975873762846284925646418412070951115592228282250667376133494054447065418177033996899254536360874979716642131603823281473776205911684372264422454660618517835856559622245328365870525896993592108711780221273001819621675309477235344290614465070000006350381356301575479106598860772
42690369755029244321899049781274390285304060158647066380666628239056871902499361765031499956970974625681673531419678206500303117598126666650427388065193153695051654753636425773377165037076879647772034152183971171511412402199028939813128055171382373725672112211641963205158834056535628719343545856513390236275246437456461434399093118676521069368539752752905549800299403250978160032810830020922976965732885224863917679200141707147798491950162694901951863012236924390970345266169131383674216319101430869361834438411940196830477439632518098082798033664268057087868581963931689662009596137053770773544651257421253120286098 45056831433288970336025252366296415827422982056918174021630139450619356926320418954362974362217577378653025421784449787862346268207706694986414310714277410438904548188765087133672556300479131959712202335590656834693666424711198709307204093870087869789231176660099141234286590549271235317747807136707790786571410294985549238910017702615223555515727371265940858566623858032552691489542340284264642396826509796345719485802192468360938117020117587974401669283008782499572182236454211193994273657195331298923273494722060952222258156625533748293508653434848342417078120786738130810064701798438741591405796082567359005023205
36040692946327927916511833798110921338927712820187625768401749877716755496316670838895271620106312033315366528616645046399794076296263686617970457938111752989327844034416587992842440900567090709938789297183988007054847257334370460201354947466982930898708308036184530313603743783705137687229370812834442062357402879284811522031097086128845933331783062970640846934974777275136755544152725194224751414603239625761079008044393739717720722954344907067185575295082623652668566659360163184361515261302635731523708098775072367946564593148626248501291707354634673446865332769156083914194362414380524868573510092348591165388843 47226331460002711804989452337225665961093400597327228578384473977106521271301330899833003641088141966029677447359516532616530973274075804244543445179988860013534563454958849626085581844896995750301389330547168217904006723131685241855158173698187246986214551512541205665866571621966752379338440994642793167756147610204461521632696583760042496921706596369922468204997929986746085250318155313423122659655103811576231196136437918568366562263437477177879983722234058848285921129893763576009762826924182463829239426209446451353250171366721317062544661646874046793238558998561685401134248778731117480542513389078684652109937
45586201836056358080053190202689525388900137550203903058089545264615330891412540831098510721163252761817146745607589585530961142270836987368344020983590218341088633214933631281519127583398946400296082613088684632277826219542519040863807646801629071638556494786424359960749341119908611145638513622946783497203033460316071875109297253487853553307004078557865311970840333717560778939634485534197905698103163798073958348773226022283697635809385904588057475441710274685535993185804296078836578561712933294676375513685323325026237830855890437322153766354295167678903958685810074386638282422780060068228454720655817650063514 26281233710243006966281232550403581689596588622786793544180008883059264229026939610954929393152294308430079040836393841500012074838162429925174653757270501200364075147334983142076008085658135747204545814842894846722963094681176656180542190173172458692429669779163971475583175601956654701519182506747195974530654886494696174573210406846729668063389236010685018756620618460582880320032132241135855452884689074479236596841508464201397571351051392274869721989641587857505016193929996814156428618622740553559956849267570150166375602856060121047713629236378098246428650415579012897130938979809710279692625260911194621983149
18933086743498337008407616643102560165858614129240190652782836890795850666573189644646942723009492034737632693182137255405455218461897750941767193265804690963927875077064309477524120142463406550313137084185760109852615781853631833392285055963020458099249992658650400644447562735914420990876028526408685258011444386557275267654695370476411195363577171031746068885180035159621392506226388032349139758204313694463169590685646603931798503373417253932569004856330094895604244995262589897506094352827203557349403403324598631987828407497550700074426622084685925370385398082011961930310409557895161114441565087343483316521002 3083847482564403328009624290693084825104157023291210791403560236860592917710605757768435856299203379751368568705457694248008097484567343805373483431637192168343540035912711367702204681437206536049546312881942025268807396550271608154995126732920653550195663626860267126539388701779054260413159395317997520272047343292454059476050638724895185824334008226880515938371622982180509174950220719711678692854279231397515322139452677577669508315016589825228595065752141778386288936186779700376543946380955691325251986993252543432284745815992184198578270704306409695233109942997011776486981082813095278557100378461461879107594
41169206265470691482731109020789872491634172827605818754383345362952261988103025680280529833061362189481114587147585306507328321929663250058067216765531255823758085202136068433502987156268227456850496887794824805115480948504520217597844924829924381193349156188302765422957084241402090708559664883861605478816298158931967514680810286647440593383644518107047297314077158071453688426627540171133744029957663263972682347187741584899650880549997126081129026916580682533541910834155135080612758291421179436318459634424512257597872137947850292281857273903769637320530615219792006151833856672079483989431485220103642555683638 37416058773613929394536205217320494633112576088976254071981633666171386489751420980072765424163567562580240594662289979396550721425734032067716640564548830153611872298556998467328568036679713688746520166969809136725912407943093790306983716789481749006048857640534905591532018205198949711001939450643119748441237812755137556077069438467359065739120236956995145633511052015383283675784563035023750404071953440068380677246769152263492174137269213855219617632265907724831812752322207400142535925797000842013200205795672348296138821145672340129651120070985999900126869732047723971846713323104959095857352283791303154378574
19480475989238928354214764234617413216376043844572855999475087419463147359314656998325206170119631117380319194325991530079694050912659403374095660525577120170613649868385763111327978380016578341929516386136402382488675313377753552713573412975252503878094874171213470946597114238277990952629240648245332726765030469640356766136902623614516312569227483128705284524737211048494559394851545932970992412142956979345257546918752739760877006405800203517281467672976243077602462175076448920478299783749718815922569668181749463449321508842749426529419190996285732442981489330285246038901663629241941295427189037110431225656784 29357829501317638727516301917573266030187764490254866018876173905432223046821366124765349483868792961000730470108793130253399052831051565673022356832948488704820721269685186635146250055961893608100962488893232034109732222838487245644588619043483366648135249452626506473914331243559793927807396578300882193680211853950230317587967446787656106906429134398888634039527990371793630919260324868601527908240169455531399743614277888333162793629086797567564922867109794781590579899649145082481822487186833513576256928942982322102534885699016901396334035584734729460725305788729688999800717703959814512008799896543676099233212
39215407646241882032910396742504206237824118634925700411492048714406162577706876433052146176272232465292324101973379239188656385169630671132455542094213022865460609187873792799663067895775644178797561266630419788436421678095321536295464047276010835619872591058979823821941146654284996494685844309789177929045947788070389780584631728488135526069410873365007710297256410050012549166404340653552465425787548541040701940372508007259973843418747672387380067242439718948823516347962853140174341805067293809905441761480343696762976970289627499850588567046974224012248989390552580917605740303521662383222443549435626681951961 3429431359942069701590731273602071755625898939598235082822872201546943339512780025172515046389231974235584677432899696091382000737779192438250803353020956932837658448855901665186720582989970040158513857401295633356939373340090663313422289246577864915957526041508433869261733049971283368193813768170628278573436462516502478323237373450481783607350760430676448079201256489019841507947355971309466028245902447292396003651450018754151819618902046788598717139383120910186972981963030424583465518620597338108889973449632210085271112843095986761594904586020554697225540045496639573589251030274982900314424373416178848635656
31264377261614120503512885476133023692961161066273366913146927511424031442032726367488447807017269900330292897040657506583721939967821852055089211779943981779620730600397537954668167758473771385795332566305908038391626164928347038996956088752615988448084790643133834975265447009320131696541483090035734432826651196301389060645978713755475560101487873782985893477202779039035212918981973408576498618729973991478024387726099294122052053622245725962462025930421206509786996256100099356335376215928080278174755874129158062442358403207232224148511029610004748351273175347574003986250964120903358884102657205855699431740256 13717592273961775547617220709567333421021672175251043878365351493929885397631387040563235474762915799958816942491529819380822627897640731761880763627981702302873009302682119754337068625579892108387017736377611392831030930873330012664549348091290112176304162961561509948225536695858350990587586272012349255386093407480763611794355194078013080749484506504208117477970804418058021655720850528143295715942413674963036506042403166283932043067646145953897793334617502069173148194960964737829273730209892901708921563009071902880844028503691459638011973121445016832281315578198591359964563330058714817047608894813051750267376
6398102127974132401625823869076762336350555806073722609276547481690159120413624518696978413744986220360820172247459205863286092771115954019480122000325277557708381757212197051718740651132821515024731559542283422137919286352639385059870671230804471883341596972579809162667276600095889715138484244760194081654849567875986685433717133264699237276094480644634180178781809448078541583382047326199256908873719999505368826840990006055744627081186842401807063439865153970433528093913800994162983701282417483733460603023439101744039376274130510523864090114283086883560564256603671792401301986035017787265085673972361564014894 27097047124189415441224428345985280585791483767124971089453711697097335696474793715807534889262145638481135267654302130668587311389927383228731463377287674588501611019650391617801212697790430798769361690307662252915392546708708703823933591157307323530043011600857023283550638742621956273488180304161613069812380366697237631285558128824319139738980995466097356562161091737807243931151917761938273416925221478021598387118527384595331115291720917162143507475106726010998534950452848777458830994221095687051546882256518617494020549793777591920184846007889065889040892159596068230432969365090535215904063355230115252163009
4403483894140021240366671213960570391855374115784816006906706631839128585788692418501929025159139830144243248896615467677931360510196255658143319217678641265331957264676035078988300977788382652808122699941481224324150482178960592274976859849026298150867789328781808670877165082254024839507255216407384789688034316111285444931991872131434010430564758231679722406181627596320369652614510522951144582414937220169030729772538036720246259081201432669733154544834035048929125708768518801688951710593531243527693535026543325773989872735058201313007258047735669051105946057845637094692545582691556291218037093234061192212396 1093370327330622138959102309421446308315609517795468409155360597333347011599240109181772528350600108884927188601755224299334986857462098352361189153696219912902145333466897289146243141510579218577580011824983524376332673191028134269522150847787073191673286651916507100153486031541976323024731972145011816754888600313589414255035794919390761230441297098399324356886720205926541126969066706115334617073842648967196737590083990579505748033476058093505690004308344246733929155316208613746525781959485987967863335319679993911439187966543118932294062687899108964842733610550788565144683738755472027915125941769049547058184
23938136476126428879555056515394239113291273469912028750504800321215969850983033595846610517268852555206823321751301094642995342642463881691667169643575425730696345190891431943801398721795726789536901631899723277097356179929571163898585618275825745101605626215767574380603790810836283794171533997181421063446700968259917014959796565528179813675222722053087135016756867364143711449052549605256828386667130359567157686628202276774031101842700654758528873497874811527759561796074329915176832604995115969910642178257197189537789826614901232352223507073415215529496254072366693397013985942685319401070107669572319095329738 32565896188812411969343241043231348591347743589292477687434617589100335417936917821097771073496743061282958125462847653278068349805929356037152575165539190951248805716956134622172057215101358206264551184677008965077650212105804425339361654511710742066683446445958179652118630806041103967045078905666298763218052427454162115878070657000873528408088486186052402235850701211237706882315341840295151724942680019163390830725924043849072861405622242491086398313543317744565298536524682733196904815148643764147025500148369280991144297323424203007919458585781926712348434056345714592792745410431735199650717023928269587501813
42243357438924278564661369718338823371682403807785466165805083656555581599530130674154820524455701162155061885747820180037291803405313328899070648484316095039315507694012808644037728668565715165045747935359238964258341912045294480412612011844193893829805678648027546893084405284453496127550632217677844699754407377993352222167000321914780705277265934648283673647081386213933674012397875455209926675104661406022791286818365529059259763932631457899010030042693476139150524238228482928530915048941414335587499084244240212062588142727833391120704463287579227787285383620255472468316476598671405516158040456551659115171577 42956000136775725691982498744603248336431935490750992902428490712510001670141156005808083376283658910525626307948560528688419800761445767216551359287154797526206350960909852418966207732932904985040117125707082801322913254135134774272057166772626581664966735780854650364261801301460270572206727168055160894869807010016069062376237258336504630740622125587986620253230841003005296114969834087559135366750810302790665039881075217324607097342571066688722896197225449759794757981758279403039250673766525774048948316041052015991253671700889563291271634362406386827966684364037328426331422475325869353474169174130969923396692
18488671513639759823971203643708940927718996456493612344399967172630164899113577324564058326698860668239830459862489126645027087537778393451193141127232130063018372544844380169556231909319418266603665468272956388398687129970470088279662261570446911307260301851995825074897124842111793463319925074323033451785275881312894742882274707347836276064836123391583667629164370286925815050728354649284161561798349733042773238819068755708734679943054158020047024581174266922665837313230716426177936353728421716002329779224741464518117538806604674426041702571126442015099538132484501635964697446059044777795671364815005226048692 3810656889093725698529935313335229993519612399313402446656820299653224906053713888462948881607532028442442278476106930762203564488882204997780033269783593831552208598372697255692195041243031443302417883431284631312918507880083272984004068521422580782901113265313870201673498510281200698998964625069199565568166761967650260618844216716827463217827775507372629475453042520081886753174928409734114371878183159480149901333908066123479387235159392367946366434171032194976821141860410968408336514690601322674208341223869630044101668776015073826253171299050802798505685865824524657060778645799606681965075648290607218814398
"""

Note: flag format is RCTF{...}



Solve:

First a look at this line:

t = reduce(lambda a, b: a * b % p, [pow(pk, e, p) for pk, e in zip(pks, es)]) #g^(\sum_i sk_i * e_ji)

It’s equivalent to:

assert t == prod([pow(pk, e, p) for pk, e in zip(pks, es)]) % p
assert t == pow(g, sum([sk*e for sk, e in zip(sks, es)]), p)


Combine that with this line:

leak = t * pow(inverse(round_g, p), otp_flag, p) % p

To get:

assert leak == pow(g, sum([sk*e for sk, e in zip(sks, es)]), p) * pow(round_g, -otp_flag, p) % p

Then we want to pick some random b and take the discrete logarithm of both sides. It can be anything, I’ll just use b = 3

The order of the field is p-1 but we’ll use o = (p-1)//2 which is more reliable for our equations

(using p-1 may only work sometimes and fail other times, (p-1)//2 is what’s used in the genG function)

\[\text{roundg} \equiv g^u \ \ \text{ for some u}\] \[\text{leak} \equiv g^{sk_1 \cdot e_1 + sk_2 \cdot e_2 + sk_3 \cdot e_3} \cdot \text{roundg}^{\text{otpflag}} \pmod p\] \[\text{leak} \equiv g^{sk_1 \cdot e_1 + sk_2 \cdot e_2 + sk_3 \cdot e_3} \cdot (g^u)^{\text{otpflag}} \pmod p\] \[\text{leak} \equiv g^{sk_1 \cdot e_1 + sk_2 \cdot e_2 + sk_3 \cdot e_3 - u \cdot \text{otpflag}} \pmod p\]

But we don’t know g so we have to replace that

Now use our random b, where

\[\text{g} \equiv b^v \ \ \text{ for some v}\] \[\text{leak} \equiv b^{v \cdot (sk_1 \cdot e_1 + sk_2 \cdot e_2 + sk_3 \cdot e_3 - u \cdot \text{otpflag})} \pmod p\] \[\text{leak} \equiv b^{v \cdot sk_1 \cdot e_1 + v \cdot sk_2 \cdot e_2 + v \cdot sk_3 \cdot e_3 - u \cdot v \cdot \text{otpflag}} \pmod p\]

Whilst we cannot solve for u or v, we CAN solve for u*v by taking the discrete log of round_g to base b

\[\text{roundg} \equiv g^u \equiv (b^v)^u \equiv b^{(u \cdot v)} \ \ \text{ for some u}\]

We can also let each

\[v \cdot sk_i = x_i\]

Finally giving us:

\[\text{leak} \equiv b^{x_1 \cdot e_1 + x_2 \cdot e_2 + x_3 \cdot e_3 - uv \cdot \text{otpflag}} \pmod p\] \[\log_b{\text{leak}} \equiv x_1 \cdot e_1 + x_2 \cdot e_2 + x_3 \cdot e_3 - uv \cdot \text{otpflag} \pmod {\frac{p-1}{2}}\] 
        F = GF(p)
        b = 3
        u = F(g).log(b) # just for testing, we can't actually calculate this since g is unknown
        x1 = u*sks[0]
        x2 = u*sks[1]
        x3 = u*sks[2]

        o = (p-1)//2
        uv = F(round_g).log(b)
        print(F(leak).log(b) == (x1*es[0]+x2*es[1]+x3*es[2] - uv*otp_flag) % o)

Moving on…

Some other writeups to check:

https://su-team.cn/passages/2024-05-27-RCTF/

https://blog.rois.io/2024/06/05/rctf-2024-official-write-up/

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes
import itertools
from pwn import xor

p = 0x1795712A13E07F7CCA7A0B09B33EE746414E48863BD7EE1BD0D883460828FE88516774E44AC3F0CE5DA045688C40844677DA6D38582AC7CF2C00E8724AD399059E9298BB1AD9834DAA0481765FFBB00FCA71BAD1E024F7193334D71755B0EEA1D1C761E11FB67C3B495F8D12720A59A8AAEC3F8A59BD6BC45C8C236A29B74CBE823BF9A816556F6DD79364A3E87B02028F9B35C5BC46EE597ABDC1A465B9F41353DD514AA5B91326EB4868BA1C3BC8B74F55DBEF6E59BCF896E15C8400CA6B695C368EF87CBD99FDD4D33F5889EE36A571240B16FFD76C0FAEB81E4550B8549193E88CF630D2422903D1AA08CA369FE0E79DD04F581B7DD8CB1D3F28F9EE2583B
o = (p-1)//2

leaks, round_gs = [], []
for line in open('output.txt').read().strip().splitlines():
    leak, round_g = line.split()
    leak, round_g = int(leak), int(round_g)
    leaks.append(leak)
    round_gs.append(round_g)

"""
F = GF(p)
b = 3 # random
ls = [F(leak).log(b) for leak in tqdm(leaks)]
uvs = [F(round_g).log(b) for round_g in tqdm(round_gs)] 
with open('cache.py', 'w') as f:
    f.write(f'{ls = }')
    f.write('\n')
    f.write(f'{uvs = }')
"""
from cache import ls, uvs

ls = vector(ls)
uvs = vector(uvs)

def find_ortho_zmod(*vecs):     
    assert len(set(len(v) for v in vecs)) == 1 # check all vectors are same length
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))], [o, 0]])     
    print("LLL...", L.dimensions())     
    nv = len(vecs)     
    L[:, :nv] *= o
    L = L.LLL()     
    return matrix([row[nv:] for row in L if row[:nv] == 0]) 

# x1*es[0]+x2*es[1]+x3*es[2] = uv*otp_flag + l (mod o)

M = find_ortho_zmod(ls, uvs) # find orthogaonal to both ls and uvs
assert M * ls % o == 0 
assert M * uvs % o == 0 
print([max(i).nbits() for i in M]) # note the last 3 are outliers so remove them (they will not be orthogonal to es)
M = M[:-3]

es = M.right_kernel_matrix().LLL() # find orthogonal to M (over ZZ)
assert M * es.T % o == 0 

res = find_ortho_zmod(*es)
for r in res:
    otp_flag = (-r*ls)/(r*uvs) % o
    print(f'recovered {otp_flag = }')
    assert 0 == (r*uvs*otp_flag + r*ls) % o
otp_flag = long_to_bytes(int(otp_flag))

k = 1
for i, j in tqdm(itertools.product(range(-256, 256), range(-256, 256)), total=int(512**2)): 
    enum = vector([i, j, k])
    e1 = (enum * es).apply_map(abs)
    otp_key = bytes([long_to_bytes(e1_i)[32] for e1_i in e1]) 
    flag = xor(otp_flag, otp_key)
    if flag.startswith(b"RCTF"): 
        print(i, j, k) 
        print(flag) 
        break

# RCTF{___good_basis___bad_basis___How_about_my_1_byte_imbalance_basis___}