Instantly share code, notes, and snippets.

# hellman/0_solve.py

Created September 10, 2017 18:42
Show Gist options
• Save hellman/2beee454d1cb392616a79c4c8e954246 to your computer and use it in GitHub Desktop.
ASIS CTF 2017 Finals - Marijuana (Crypto 394)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #-*- coding:utf-8 -*- ''' In the challenge we are given a recently proposed cryptosystem based on Mersenne primes ( https://eprint.iacr.org/2017/481 ). The cryptosystem was broken quickly in https://eprint.iacr.org/2017/522.pdf using random partitioning and LLL. Here this attack is implemented. ''' from sage.all import * n, p, h, pk = map(int, "289 994646472819573284310764496293641680200912301594695434880927953786318994025066751066111 6 843235888465494832763255804166953659073735483996382764878385572219936486704848907391083".split()) assert p == 2**n-1 H = pk m = 6 def random_partition(): bounds = range(n+1) shuffle(bounds) bounds = bounds[:2*m] bounds.sort() res = [] for i in xrange(0, len(bounds), 2): res.append((bounds[i], bounds[i+1] - bounds[i])) return res def hw(x): return sum(map(int, bin(x)[2:])) def get_sol(): while 1: f = random_partition() g = random_partition() mat = matrix(ZZ, 2*m+1, 2*m+1) for i in xrange(m): ff, lf = f[i] gg, lg = g[i] top = max(lf, lg) mat[i,0] = -2**ff mat[i,1+i] = 2**(top - lf) mat[m+i,0] = H*2**gg % p mat[m+i,1+m+i] = 2**(top - lg) mat[2*m,0] = p ml = mat.LLL() for row in ml: # print row if row[0] != 0: continue curF = 0 curG = 0 for i in xrange(m): vf = row[1+i] vg = row[1+m+i] ff, lf = f[i] gg, lg = g[i] top = max(lf, lg) assert vf % 2**(top - lf) == 0 vf //= 2**(top - lf) assert vg % 2**(top - lg) == 0 vg //= 2**(top - lg) if vf >= 2**lf: break if vg >= 2**lg: break curF += 2**ff * vf curG += 2**gg * vg else: if curF == 0 or curG == 0: continue if curF < 0: curF = -curF curG = -curG curF %= p curG %= p assert curF % p == H * curG % p print "Solution" print hw(curF), curF print hw(curG), curG print return curG curG = get_sol() def b2s(b): ret = [] for pos in range(0, len(b), 8): ret.append(chr(int(b[pos:pos + 8], 2))) return "".join(ret) res = "" for line in open("FLAG.enc"): v = int(line) v = (v * curG) % p # print hw(v) if hw(v) < n / 2: res = res + "0" else: res = res + "1" while len(res) % 8: res = "0" + res print `b2s(res)` ''' \$ time sage solve.py Solution 6 442143125341270492632539047516324923841771661106084131391532190171922432 6 6277102109531099921227501217202764039016212010661702533120 'ASIS{a_N3w_PubL1c-kEy_CryP7osYs7eM_viA_M3rs3nne_Numb3rZ!}' real 0m2.491s user 0m2.304s sys 0m0.176s '''
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/usr/bin/python import random, math from operator import mul from fractions import Fraction from Crypto.Util.number import * from flag import FLAG def n_Choose_k(n, k): return int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) ) def hamweight(h, n): if h <= n: H = [] while True: r = random.randint(0, n-1) if 2**r not in H: H.append(2**r) if len(H) == h: break return sum(H) def ham(n): nbin = bin(n)[2:].replace('0', '') return len(nbin) def keygen(l): n = 2 * random.randint(4*l, 5*l) + 1 p = (1 << n) - 1 while True: h = random.randint(1, int(math.sqrt(n) / 2) - 1) if n_Choose_k(n-1, h-1) >= 2**l: break F, G = hamweight(h, n), hamweight(h, n) pk = (F * inverse(G, p)) % p sk = G return n, p, h, pk, sk def encrypt(msg, h, pk): msg = bin(bytes_to_long(msg))[2:] enc = [] for b in msg: A, B = hamweight(h, n), hamweight(h, n) enc.append(int(((-1)**int(b) * (A * pk + B)) % p)) return enc n, p, h, pk, sk = keygen(32) f = open('FLAG.enc', 'w') E = encrypt(FLAG, h, pk) f.write('\n'.join([str(d) for d in E])) f.close()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 True (n, p, h, pk) = 289 994646472819573284310764496293641680200912301594695434880927953786318994025066751066111 6 843235888465494832763255804166953659073735483996382764878385572219936486704848907391083
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 750064245476963423505702945842394443765625861201953967006896553853548711560128385711161 234642083165479109216388724274073750812859419247997565917389748529137391501559768603489 940566119619788793625447075113603858217158401663939664527280073374510742288710880360825 896591377465917354894473712022904127736254339558738164631551716493782702800298481662764 6653332645746290538635995586184709119943210196961395820378214873298958731306558598998 533088903301450038460621007533511451194705683026953033252728678295260858409112138076862 579721919518696212628041312609623917695516535844456197032246371350375607432130907527774 159722007047738728900379066846898733013253145903613157152318161094304293682035445137692 795232086966554844283109119844059808148272754619644458295276987128439104716849511992599 589811583618395707549623412448720134640484792909919153931048497389045960325113882548761 167046192137853003552527144671220039959964737480724248039660561382914079239001116263495 520707618468032191371040481452408160439937470728357438180374469391937303248526996947846 946957762726749035762824317067179600566509014465344415163632291776567255608088048698246 600129548455857490279500302453544602574803682793895635055827932203878573568372669208675 684659406695882136837275329506049169518520370372181180172431085048524408200206187164079 28973302119494682388612378370264630459308811716496532308563283537289253341266402809611 594755387232636910401615675917197149547037601049693096307239771803746678928920303413749 928514303712004701802561287128946101247824603643125729636644141003342426646094634962413 780081607853014507645253338636601009715829498742602132550935795702451609885991159356211 709647344398573299319389330202241070851535666748500697948256461313842711009700601067294 164097274297986661931484960012338654182311901299550441405901518950553152825912521976496 397047125672743481761961146159540095171378683348665439876942594563478455058448127040895 203988709267856417090517253918079687319776298467649665565709538364252695085743567708153 783511613974714329322408058080057607632564814575691561745912496175343887293376581941166 195844330884353434437156716140707931576001284491664912939472082190605953549145526922187 764477836001425701702890941384005462883307763799408289599245666907022405024085750452763 34768274706330685040722265688076604630656181054212498439129853437903042997906472850137 649961708776897652487079833388793632126733782188177954881211579446291828198598955508004 817546910158078131852226904629745427600125790512737297527468874007435590939804521849132 919236039291064576311110054269502883057340960268931923162689160703420280157658049164410 593337358987296600811284127811787151251185405367873635172973649691025928190647675318870 610082344606113287985701030540069586194031554079364691989685416074690402083365129189290 541034559686986288313374372941658432838140323198272020374200441817828444561894375760678 328978605868070279566281537360310758906724192237085830734952241517463937239919076958269 693943961266450083184029692403977177414316500086269380548746162924282429661843403950123 869759915747211076558168236278151284912645000322076505796166702393508815524555926043976 188422368929273653916118114589559908643404683800632124520727316197571320655464086767918 116287538397210354787815534689608234905543979095424296884669910836684518825278787457465 121376794998240253099738937271581177413568904726035041488809903525535880709579501356025 897543553319689361895549713319258441549199493297887727543483002886577791208980263711760 978816545379871816039331413809671963940191611265259749959107157244808490085405778703902 939463627514344950068030927871298606009191762294578992440340530774478337245729556140262 697711464288825851187396247295349241326780719107314966481727411605057297775605269863191 385296084749195139309301692590873473190559496135101988481290590156556122000111788453438 88164734728677582468841387330564689430287128448751659636472011601854212008701260597707 814941619338459129151903044226069880059255772138696940468719608870802655091182624896049 251975362419150637812612534166941358689699432353200897792957698458481674485065683986302 272685564908623474058656633531463818276490364543329239743531591335933776928695954824470 536334680846712828788466903644157054003743900998378440849011452004080630941816845630214 342660289382868072894418819489197041987508889771271719037182488945251276836166609695982 757175336671296641895303638732904809363316656957273643230736780955610420232847028315791 265410977416902875551121862316249702652235390681254241483186225952881574639458378098487 805499465057849802525440245524332676003862362454938491489619428023053714215683875438450 284795582406434677215831786280928693202848637401966065856138536989542800890785212082306 940596333795660816763171691913415140179995255497544923029067963387097390203712732963482 960116368814965496896685850822139767822233881040364661185718598676018987906482862869387 408595396975287993551519524578497617915671492787801473741949307233622962054238446546713 477166806384623901651320659113741918990306383784773925477941468262585660349171546576719 935678698513324019135634460449552373316349602501981480367489151307332546190414521552453 342647760005118516887512987562698465103863641600074560410032577274471846492339736602344 681993915967254411589180625096570454068196967745832641134842825721860841769177681680383 94039010540247611167694690305162372157825412312321420813560109791508121003755772829518 136648938081336033651188354495907265111558930643819813490818535316154639642672888486992 376231774221985160562530326440037364560045335771033117618689969837755661207572373759643 109809986632201553196425990483890223425161527366374572265218845589939117031068514067102 706883223311469065177334562817147149324784221060724367051372027213474601672105491690269 470396824018659404175848345988087038252647798580849347419329244212831992362361011695534 760878534648635782780501347575511570152619438474558716862793692615076257452996314459236 807589837258448715908864784344141743588380525066748637032398653318555985018549284372594 166941566016603549092661531363123974857620393396865504062537565775662668585751065066297 581388595779386548032753293757263637744026420797096208256418938850388109417334033645229 713421844017966769135222570836422757829296820684983398253715271700332711178769675340426 20638521391295655515557642760410541618618737806411028108883095816155900365688176950354 292836188587288903691364991630718202078864594445916735173204483337043634597991934009219 570952453207002653026769172052192615556794937428704137998767320137062219837269281792487 363428236266857420372363088302547253297548955945818501846411050605377916136174135893595 246049560431956074954085273147443231026103409272887148410060441992382867591969181630381 436111570331704974483430814512694197179490752462485356742821595908788230856349730526573 39974287306102440862202035529920415838374229530764122170390744128740597915765403395938 572249691729505534544272389790444669029833342654956751781476254389273697093134057279557 43885772522583481592294311539760058880137884065630396554319981064028140857395355671294 338458708229517600137246710209032625796520699958730176154536822013571578001625697288303 603942823276173311109807960194738496388023793145126980904784622641615615997056794913336 588113357957869082109047530823276355717190195988100238333286758566750996564907204742659 181690013544771070712098766025627794611907542332629001394822486348984999531649937632333 155753253329516840900892376339202011091066059313090334597585484949955889222504326506464 330524940711336150115528478324390305308273065817111121226226979120552064157677407349149 98267332136166494254115937027154833584951222712489133079623566120153638238108809869801 275718614567172697366436792555139751077166702581641402555303102502535836475916325211967 376987617273551557095492213314123566163671949504843139884744173089303418517608328120633 619591663794071977401786092299688316011454717495000486562831559976552397796023389335214 152577073819992277317038349847073455732957631908426024877127727864415389710663656527808 400113702505627152307809538101983998584257967520846548306175518005978054504319811255583 730822764830983968932568888417353793946713083631519438985809447649740945314048011415742 394183104404169266922428313673376615325147756696403236369837436605951263992674443305870 733442831645479674274220879723760865486398487630294865221690261706671819080893961207644 928009468388680681895542986376723964733176553282983735222916842899887154907046783320210 741121548743933998429277735720977060364094918972114115552883567780018500293026858649513 128443392317894917131778211085951851454155857511841946862676216673548701203629117724043 614734293398152272533238566729830638159959203841410601445359937928868724334682378892349 726858299917858650616714291428952742861747418742216534758223859532511303670449691392813 386571250070809006474991416751222729360634944049264860574145134639137691649922261215851 734776055636139445322813344957916982736865266110672305112527343141516289533374421422522 650664627616584102154704268956277666716060403544420153991632990628532539538322634868841 56222429161916497983005059017382819614346577228224127705318467139481262133111284137188 287960363299919193999594353372763217058627328964994551898562305292044044137231915606917 134692223282814380124138178459194273339485124013860631643306758162344557738532760610518 81904108671668309084853444461931873592882402652649955884241606173618313152760476601126 874835589855567062091001726083185570449721950448651319589179656282940008699415531708947 775270538100933329203775095702798674030674234609773505774461658163587573313752553549824 131228141698708220292865917917723861922038863471340646074315382462604400468951678085738 869611721532280415533016535840770974900865154196007679916394302223546671082261127976512 21997840306159599141791897511615685468474273146871922187184488260452953137089152556527 785303138154559925976162165020637051928227544733686410658075522576874291797352066220325 51558089078129162116709546482187326209532835868796561067694863411799913043507582833295 262321969977290573721390645802635378641271362235514112060285166440367287423526608888380 640694932930329853166048170945984588396139179362508366172819765890712452863802189581082 115178461217026704451852485714832848281523157063506327048193629692298204420888077525001 374834160591033523409140717832322149845762965669674930633696675885814193077206978776019 310925713582229686637225550526049565982347038022350483268346440217887078147571135714872 662834226070168418035373494443904638421103165881627858932591800270133940793597710415735 267112452216540342449848653859976814477461129404146528524624056906372444245452775870649 201560564866495060985943788149419405798857095589611117894200565509451183596120300654338 864380423504716414010136888459139994121139804031266624179033796236089767595344260782576 417673215173301168586879142589431204121099882826364146865639697237249043998357973822365 678844959909094194688237883222612334245087859624599066355022422837201903906434421850969 770242719549864675276801260178917235670347278050183890056707331607450007727778330676120 717705020153479007998572935286786330722058584589464180020757085557835544699016193526849 872337594645941412932599916508295593672881716997054407446660621921774180631561543255555 622858449792715111899394325997661670209321342318272537775021936358290540901592809412823 820590598722491142051517591026305305413138631314809797107829494281311591600641836446386 725799440275086666056199132934202925934879164900152530823702541390561198123763822140954 509595186538210550299736337740614012339531975857750038623331765342702036455618063298433 29756756993733856603147440793420892656279779418680827606258743339817972444017360127790 503062417904583575673170715035835572901873101997063646697379785363096297769858076205462 495699080547795339606412518592827628392344423435412918636947878114541378494654020177961 568899999833534077162405724008677753268646147327481495610908322908457434828083379773675 382647690665754600059680639284415336949590883594535166415398409882047778582086250566693 603172940844118328961330857994954462876283869863628768532428598505779987647389304362127 389286033227216069524991057078992632480548505152160397657693608289729080092965383012237 540201501568667081601885210420384315596635667018254981653607240564751424278733130517070 341166401319857338855746489005903197488600015495530149110025315410583428005629091411995 463373197652406433968795985353877796782469337003262392519475490229087851531892317284076 304232298052315411194096525768208783812403439544370567822113462289565625999969815405632 272416814752287438024363834239096759720217088593801266431664498882306380346279966838673 165661401553052944465455562006826844949827189773512465161864888960927742051735034618611 192595885768989498162585289215286329447295238036422106839393452659307610053196260845259 693347028587007979205885654991429101614115496821121865478160087036509989990754292469705 496592216144084857000559393871204540747422388869172538439636215962029128325913510100356 955543777112418844697134759111612235569673845202463777335246648347264237744672952380520 809919094493253636234667578118920542936966312251967986019509919839607870260442125891399 435623821108242080206544580605865892232725787904401762915582976486413754543656727141969 414617788384763588314331894624275583115477419828962870977364576443181532399746383938739 973615077249024773763218871921124475275144778345904859368825282037855919800395298313828 376978740764468291440999566654491019292922865858919831894855307376004268621206243159839 311899426076449665995085311525616713804909272270167384615051183405385108600527070648893 200075568704923454820612295335931025323757471915420545872519718179566845780531326633240 979504379882012187159366637012095315809086597428788322388652291466271933386207903435721 408269600753863212272426468992647902091636938802967460058004431268701804396608022309960 214963959315529905155251635013630586258982211671145961915737685574922708452783571425862 736195473236277604116418710768710227783739167076312083043641902735089246564839899258562 556379123241289045737838601323953625891288766144500053619939629119737997499385585587929 454955170158396914564912813967882633933280683406278888995794178934600274255535480658532 685332104207687396069860642193486813342043179040424939297104591770139945560880120740757 651325504580459801932732901682929494267231926607008083761670289031524658504191225563832 237632991297410466479086828934593510031314658995859972219361208866468389276800395009909 487897330141199158422611740107982256755087719075229264781288874952833069260931601334641 235538535729862282245764977313443408166044523786946384917110258508914330323526163041903 415804539168383554623218161764451271940461978722698024871721825400951660520531210163311 417595674511940435762682082249508819897357884146431086935380936788157971865966358560782 487215244035523422664493524916319053480230711725958736232610435928305200466248407300066 705263745881447473815743317056626705960172590992078414181398696361893106577588790944334 447770110705848082985830698901766238923916675597531156443869125024881040852013445691625 563799910386455112873319625998336573484030767018545188829059077058286292523609990750449 316099487580309707179375630114329758904572262778642224460241670161367791707285736914742 80309127370263695157670051729880702249185341517363953134037196224531877323638986352268 336131367278073530579391812406925089128212482872651876896458857154127747896523327750033 224218126968165825211448274936216126246603049472658473544950100571385869018515860157377 47272263224739240618631446697435680099130753847549164413118055373271977101801134825645 26256905639522256899596211222630623568103077746939897052497420397378207639863576554132 452549547931146653542147146393305710847599522879477365541810613939483911723907211647050 713308454850516965861028088959110042162147461618915569814541903957619029526594040476784 67828735969203569531166952576670940442683355371116230135801223388429714180501947471319 170237300374875172638652371810837272871449381207527604546434632255940911001237714731669 981940001489892481348365762597282357109934358348953358388545863717891949721072948136114 715099874527385276340104583293998987497206925596113239637151783985614327115082386694349 340140375741773489279543622851576661651852591458145156233717748537376141577029700110381 353899468435863980466764307276382103054607608490037845589385347802663204491029096641591 19896899628081652644673378954394217421037494085043682456895180549415577187986485682202 161026276050437701673555890584898112401034931035910538469287505155159186708880237478007 965073817504584025555882002938123020206977167863240167211853907272286651141593216313220 439699717871989595554132993215719643110254983208037346269478886054848309835631002421607 75176559799341950203898137342425172265073932626598175136353154943608376670298109761915 88709921014415986967187924399032318174710779246816627703455707211485660499996065054057 539286004950950933003403300014497419747527828890058372292393356439563477352960541926121 492862068693462508281476747982584549875518738389359604847552200265905994163122311541737 341072050435217322337084560937827622981489405440517207033738669338183892984683687342274 78145067955370915746733671855579899893824420159168531138201843721618299430176966512906 635396997196350588975664300104520648905445091175805547949563149812951418583286916968884 337709170474118739654392427900431818073153852167459426976982900813335601203204943844708 15971585555508801459359232193561611735679459862977297730894983158519475674450777004135 88270872153857991610772073323357995981234777457642852292243169380208504656530290642675 913757193177061566119947738963791728578633039913050502323776778838460330823676886424985 916812575807458214896017588414147807613229942032752537464241930233044666985712368515470 770527258223567275724133246598972456798757247287800659975918930957743147619406318828954 812581110243921984281077184769955682053685765889845303311424682846533061652743830696536 507823622986542473294301132111574752591119666876670767280020393888960904072885155539358 746816642170960571058059942831061136161761672085053355887300953487408509223523589016228 375583980991505090220000108803126613538571499529783543300913890020092092303017633717793 411195357965748880490423611235573437184491445452403774738469251698332322947730737055342 944636394725045104206390300516709988508650311600390873552988658841101922650917165884132 478799675390449887453241105965463374141468580217989024557096306928608556732769143264560 827846863862604585149238177515190026588498431508122041703147907146935814191212894422010 909966639291801014444517239619698410434748735600517496959162257938429681524708332772796 966906868788619542144388530840540650562083312799706043439041937498967393138005127539114 511759032494083744934267504212683533531040647128848774791056808991692409900253695992800 642499424059914588677173865319931426669649800136259089713431193712837264896544360252141 599403613659319901290953568779824769305315893078140641916373403814718698902616930899154 693649041491385223655620867907498364145807853355709846052585275208944336310657240849970 587274424853017438878820680470151772126411854932044321748024071836213378173548578650737 952729843663588068387251584753629142526367888773773496460748542745286014710431611920584 87645383738440645293787313913804186237698541436967526773193007452448509713964611965774 372990369253402927950978758805695749369411850143514632992074854705332381050175814233837 773095370070263977582479017484519758265162697982355392114208776215081980233189217354683 685179078275199892204029218734407459410504737258153112390892389287490423556103935264243 626720022390249063396973658343312709224504061643232383513035592151444199342639921837539 438055878889844408719111553835502044608646991852243113824136142031631754641489671554197 135819697875573069541067355413282531250139429315455940875598848112223168968102954270837 127888647465308412691597291002287857921437875085794905517051066786218105976605349362749 578729086433600405918066919715653813884020727185182288551779131478712586421606743916860 541544823832534874070517935130284275617426121114665285825756518146045138146808112793696 874818508939321979767583174449105740555969954132545926678194679060135746893624660132100 417507406655877779877885446022502794871300424283680829898317847674353327488594959367702 33335037776320544677602905561061454614305998976436340417097480228680414011020533749633 680693139736746681647861877569648789602204870089447854780798836122167883916427810901544 966422237008170599920895183759044381048307105040652188201109584059206138023954869281595 504775554071695897725686183716405494153089960296620681890758069873141233312055389523429 444257933102653269208736542317272123572272483601181580498625147026312527029694966690382 234346012370554882307665709379833175233904178498325998411589145404783353458509734566465 369864616306522820710076083533508024145902550331968563784706857516601618609326800867524 112078964544947722067143604524424912892481697597609468171211174024157740170379339502425 586607481256692933216950401812274845742304149909096651185030083771363814985431004184664 51965940903290237784082879182847184417435754493309265583251279652794989753636635366300 139221099072473339439000353047241805784358919902748190469638965474498872057588286391941 500435119419146197200421728127501415109881370368832537448211352674021903210984717963617 514343930929261344973018163949839272157155319733201700034805166985274589424011021569803 698308614206139644161862316106613031760212460943422536613967707551178035132054036546622 92635374077835144344187890052668753861343438382667095992481903024861523804189234228922 793129326004009665019747418861316536398641541727257255555306696738042435881525657408890 23327913902253685450253000643076242029589956683863020189820068220280935920731009417125 717215932930225775417610554987245770943594079762296791936561944415136585692510343868607 348797459794710538542698657864527511552469938190202205754648425494520754597722878687168 336548365085952311290711703951144048696289494936619972823400324731493569421259126880763 878949730639880467604297924196217840268170733723367424292231145316299090657361570043287 171233084758195085184219267830537395661532564476819086906703958032356704164585170490250 378583373068985335837555448549191489684979493635933397296629714554860612007559026228925 329827314350598259956181411644329572312657480201042195261727553059763931669489359988786 357223092320257320060574706655219997888837798965677717363142532918558610246151654448942 791985902072331041022306447485530136628694416025446827586574545506833241416334295804647 686253776809483037285141610342605257482875115207804678850748833949312968333849274708643 813765407863972275735569840874637030920157239827255267634093474043303536887832099666074 733468691004588508131898821628232562010103706778253392516866558987280466244940449079857 99490904029132363048313205365378826303125995095291008390423890338856193889895547870406 532112550235589788317878275375916474319705530550767228137157496188812396160731502449951 247622262586412400814059517656788924184819755154122105083958512187923546688111244001885 178440136774608047341464940441662336294553373857549803273467505089726006262283050137789 921756595935319015944332677096359427338693981738567545091711976734885683931865723119070 632112418441268293381402211549565371668007124248091134998196543761548953892149141130080 256068717040785716653920404414733747233509516336459348224720196402413729212464833696845 792123247496597231820250847535631275645649433289076388572879396778293312464948805428395 127468995306872744067970863480709424233305634478873474753941821681651727098691499025895 562259598667885926748399188583173814919326341905923520847649267150447047802104920494948 299996219859748787683708495358374511538926498901780499732040178953354558503957424516027 882435125896527104990939002395930211488477667475571297701788826049712115114200805386495 251754814633282045465280128979545013107857828607922205868522701995855938108305953509822 52308653094317482032901493200917469720986435459119815095863208412527072045983348360470 809622660896332138031123283927181482011018411112569785905772978991706869239150155324204 414151269491725703994303573097263830362933049589489655025723503138375477957281237001266 695269602146705931298875467213363891009311507255337655282252867916956869679123374034835 674181906248290442950567245492913663461423758857174873618857025678169520951150310237923 175780700612835095760890410034571565991243249113018332963972377859319600035300213459205 481668463488649156517721077889313649109230157422372469640600673429254673394935227989587 422926758319144927946307402443543064966110271651745250167485810347234904738370076667390 847888034342834586565646431913521664717075190798206741223817397251033019373560425975049 651930324303689830648251815927074270619330668796987235434938056014649705807725085124425 460829124958315192647190607553255647519221588464471406011332162352947898484714299878306 901257569617323515341074746610714672775138701662343322028840244823644219881689364654240 559832969609833806723255293798979988581556968433584403037099970127339472525359810089617 632800773988877891329229934395830751358534783840733399913196320336262825756135295042664 604667391717335126891528536491868289173232314513652294374525688028269561725343937988538 590822179407881521227556379924571134092520919703161339623613045324617875513536249760265 447408309899172405978556195934819958736559167509338589072234873697422194387864024171504 174095814133945858449298056279322135154557727982764109417687057796982681932869613203561 55069986114810198064353879718747644289465818483223633629544394876201661584871368629351 389011761633974632354958810404289114451203598595813615742087628254770817060769200894888 301552741189552445371452249650049116225605676672620032393678264339763272536338516407670 573523995367370455207935518802577326761635609199894176602087253915973088570073100068917 211716189352921502718308472034811684575084318630088367211612607857021299083255378230773 285608359656567113914875016410489479137791060255586972753097177375069654983815115881643 717259296189658009679944573076569644583292805743381774496595639476018001861773574309321 180331343737636787987499332738988853384310438399424004477773679455267182539334984152409 836070124442668442088487781988986779434757295111675222759713818970856225940014887792000 568209486946622688076347933289482673519546709140156321820167464214449307489093789164135 391907475909975414125442900385198302933670873615603500559928128383640786231050284119796 331189824687997649635792391874916320705960404013071708204255868516537951587876401502250 293637785957698778557214158045620552740394293950646914578475413039482552080820290063756 293244867439096459644098443272112569863742476786346491958957378417294908613501879501382 224650573516912663586978221967431290100540042540617136985862660617585144962387567858886 568459837222429883992696381966854980421554788819316847353043025134818855249605913575115 611695934659311689713947807115872523166497025036341772662909848347540744153876748517969 652816453302667204774240592201088602218472964727978495155869263485465635427567350056457 239399572025771382635112939220881273582135213101389547548527094335259657080982945255359 621835472197009137346976057595825455931238210321283612071469400759944811727359415124908 494452340408973669093100867039048363297252161963124341717130012783646327365842318043966 548852264698835159835249242674393063873326830860862099229072501089561206062013916682170 921002797074564518191395029874954404760539420076514930317987017577382372281901054110739 944023099642013381604241641347863756879114453283851659031454686795013855169109599635655 661790629735058954748672133663747724145387843795835136924900107854475698485099551104914 349344016260391223420273029160893227017419974167908205562857210540000465768675133488251 888532852970728331488957876157273656950775755960517679502860926693075691456995544547755 927069162937292843703912152509338780173254091048630254131948072942593851350633874940872 556910679558662847614322778647838006707388460607010921876373998073966406408624985030307 92388667562252194749908805540484825504296312622823584343919076738914724406290415987631 470805509909245167901096759552597847720261392081847549216997761298518326230906958561102 154657033554942937782802874601315234572894712643211141069185548550219017691865906122603 968330020714531071411610554403579782795478959925808013259030554840951479330098479780452 828257478774392324061641299298911847586507458734751650726452509054208382068101270076272 595566984856941469352775756228220938948792036587331796642993669592280223824304817855098 371402302463546349767398603675579800281969999497774978553748349269201972502567448716164 119374689034991989410031369368310230577741956739820559225452067568888194710162164757493 372929917504670962207834327254825236507607729025915415118580460521291951523959883205076 239099186182699746516096916964173204898502492222260512353906203350198869864362896990520 936779482794200799634874582339516887800445441190648437401788877263592233508668854215637 463632175679084215108174783806625094085192922759372654055369802553005386213369296284398 620628678095447006692866761917010296641205252354200520526758588867909922642459147514449 31558759615964124219594102139088615392751958042113988116337578539395298439202033330072 740712742921015225847049478135312455806211667392643717416867262441343654234349742548937 251785808599575724103174632081215464970930624136172585463135512319634024118107342145828 36854549476515240323263121180355554185744193917144045642384507559326531254209084355214 551425003255466404181911691947634427197119741314869854057510759128235890559496229757873 101022322101661268412914593908744460143478870447213065459164392322488742511350697191970 262124887019665890813810512907527370793036324267972887195604898441499230725721479708924 131303609350682346332405945506953429334875865349287415448773303470067814208982600844585 667978451861356188279340200509341324583862822673925997394130743188201283149101368462163 130713587608309587840524564290875789145667819494614869202645653356514860479796271987435 395455151201934784070278080034773198769500888567061930081507749585410574294268699514585 93591536958897003677353852905147874290347239650921013387810803296266370394164492855290 591978847694787088478007987146591735052786570489191263801019635275239154062515989437850 713608554202155076159106759222607104598077413982080470896651091317804453051507328475121 104232052038920312107855325346801069528779536824251609196219933022962538679900640482071 331557501354002668936809320931120119376210437839408211260035053892716457491512368961950 36753346743593234035752412440886408142268183343976753611269578090822006896041451835841 899756849202063314179771678698167935851608413442056109771484540700862218199849443298234 53354782872664596795448602515262588700823800261231717859100852547096839797512674627439 626418916083723865324276916926041478876613303457266523444220878230328567648020650949399 165439283637064856105718325147958840485458653329905580929216980130683852032787049240723 303614798448186822224579625407856494504521306876028224222268361268830025169698687842752 59161167806492885148982884833013340431086057929250782824290371722189933098990525188989 345739708417903578674680749253865184838145239002210993894889600367174788461886612018952 403551677197416959460122170718193071065753620528002989028527006997910262950914269399156 849246607901246514975595399005290802785751980016032696543703393881310605756936917265100 465246101821029283029656355463384679018108341069542087722377831855395235703115921256966 394132579813067438618036092686965907710605857053548691835231649574981927454337322521049 451633136406683209626051170505327614419361068651315442028018425200067442519804288815297 630547778511430083869572907699072057260057170334056901987949034513652247365996099155274 831577968640796849601503644820652263932139361551433857914624541715196840757940639152070 258519577499811821320137190971381852786919985493397247692320458114081519573234716514030 815885096695841235160186346168040518409841338661768998962889287388403060256950386391822 429305388090362564475978156032372940192246500104675554114789026068853659775245405135545 770844694747043220448428239943121084952465604059601350989694048986814383719068175474228 735074786734447248935823785729555085082994350559321450658400419033252731384005255555853 627892116272171711170699954851804341036936900175238293895438003567639431498407164029981 773491043281584462680377259268138404471162963004630523609288197517116147385224398103677 216898159045726073981441640477603356867430357983167559972281054542124624308684754039930 772022892332873254330467141045436375275453227755791419921965732260886281700927317373451 566091884191417083427183354394809513697833851229626992032861594205152190307054606939737 691199380777576199876185119989652571658512263504199468379624749471021852016537116470668 495939283928699770228581047006088178081434278993467902540618313106242169418522153509390 362364775633481973874252915633659144522991196289919663681555287440491831483018662850120 727231701884916775656163386630419173377888205485366461547697017938814775640177830348908 891135434682866003417153099380233500324406455131925913689357402696520859601809814084048 227226933398536280627609030997113348680376916234220589673695605625131999084505518779646 877413341034145845144046119421231011901055515440550404514348333808668167544084919538967 776639251439670066072462878616361194467620787131077861286045090550149601149624425721017 407218780512741246361020384358178801388847641873689176709880671341839358079666281840907 30426033402123454623799533813354229720791048175121888483280555184174782966518601196702 663076610086337584659083635006446889113691708111730847241643726592048285777030319275043 19278104124079829812499415520467072534643740587250094586784137553718299791183965270896 279056043390074290350231506799656656698051617528874695747826467941332218004633616529850 709282132663289217899909598536721501760305986152104978012398009062994063204367437220602 692471649440383568222055686155878788513009274803853628629000452251474118347195068674894 384001810688597184073987243149642557364651600160607019927979354235209579700034892357996 535089572922331896843428885432612579395315432456103670851845916847327825780354573943686 359564531319609545677911875455735245478703562522811401536388819879263106807142333218839 532287798328904438502740616987278733084793411525981816868173680356333131052477645048883 28203551312569280161040256994569077276897427718273262477400532569946006883760317368238 886877180330209073725299080158552031509124734035858928030186072653132189169536657177091 515699546599873125794624372208681297065783627434137726766682589224181374795619786849724 470826173142355619451892150595720563773785301600411374324619230358207893585771418609799 627758069151803714020285806932386724987939891603248874484835583332158774662731347506629 699167061433265611267781463100966334430359804540232685982959927240117600879370061564774 727352145361822125660049676850638600854146866129221840282754062937908803915576755491503 437104354316306030141551458183466238948037785811789497439035497058180388953516012708289 330754648324133369047345384231675014218643616239082924523545745975351275975657545377258 848870928060496822077320344607216874478604612489679345318658546124992598915961737437912 402669258679304473194982191607530307814251986546350340501260435653968641297029950789384 338864977232251357080353349761532028433129226980058108926104958985815150259942731358479 124387131827294183505026221651112868312618021465622450817406001079863500231632210425804 967311809726519751619303279289355816302360892103166497072850670089316383300320071245951 222199134442202252115419032024805232118562363629654906610619059111647945058253776017171 475971544228335032459390613668201122940186059775767642894397996519319470560031540785325 610110403145393005327789576522820791340248102723816537961374177835500746560038703765795 126859399995275049567831722197240589981692473510013585556595721087686675902952347474141 453055992285763733086637795357873948094992079649982884826912643415983059716247513974331 80204174054514658352482739290455421211200451300415109943771302120911718958141813844740 541420520106909139413811504862896753511392007090350739573433656125134272250908806873472 176152571201706973530101548819277042683887064527069786888971212749355407874301025598497 586744632741809357341383059772248525290095643251315509475062596853970508848856577256281 494380925067297670692558784400411375564557437252735323787361350351478039636408193277403 893966410749010159755891578820725414063859693561045519334928603831087907412661107160484 255717409814293328530213830789781135642056989674699446918161334449877517765084121392588 71510655109004104676755926147835105046755370080027106907065343493741656127904039392494 510797602964693544693618618238499704387516944329455143251380487789028688547389564115562 328770471484468481546886704743837427785816435457285592109529611904628991204226540096615 639604357775513615562447495687479760746315208478270769255896916341718533520785104554420 527489160380275191770214685424939397820822458285166541550708557946990095372555553797558 567243413678222308583101795903098810373473966848952785554634038890015706822879222985431 143156742866973847835118442523535342251141960441990968601371640832798342237417457857786 371534385382819247485339843604874537167990219063536328433337865067492391275040277605314 586199216523959174589834601411841340799324489726411629825278788185728613229524560058086 291375275978393900864427450712046404702701153265199122638820417733078228044724919393647 338332447591900765949658446052673992635539130603597603266019529965581112179624340754069 946900761078696820273428414088632734049197694080465194384725698142209897297449603779151 400289347358308825896501010765537321337408726591828139781953278116065991106808197423046 483163785456400133679102368832679828124660371961409373883317462264913707589112515190151 729793978818584647561514946667343987884843969461432297797870297096338186842499497336289 480975177902729345331756954455004154187760556275534901938663992265313359035122028511355 708899594896725694390857980789735164527988921679648550520107164601617559038990607609415 35516523396670752329646601754738303235870193581247227207904564731407683080080194423565 967962586746965484520222284291442585151952415350038892491603814788583345669245309924410 677291838244710193050573519330237987828907779118600541894724057923179210403878853789172 429384736324893868829942666364629196091870999318646324678250895293882556297795881465867 555952105361220357806725348136858194225281431715011565648538657863809593174438358344032 687215693634316521667205841969103357364394328986287963471381866858891695563999566169259 973630874174790316030103619105721160721629913919046625029929252727999998012909245376231 169650246080447746407223954058027335713146044258530787159581013643769956485437346964336 347537396267981857149084651030939744569915495629936721780849395002205376403245917298920 622446940241293647451432579702343013262180164513104235773135967807236579768799040424698 123104695034663793432372897270696209194807854585890809351398625497760418808577901957827 96738685107180262843509445308050035568894255104824390426517234270402570281940501945958 332422566609307682643762417712497392190576737401886481604276316661494623517321907485575 50006790905189348379912825636995685823193107188993966332954011125339372933304631622760 309890614417679605933147957941921017579442871338449052828725082194672925661584238034631 158841951211277245211531850220929547144805537560635536224405613146856534260524242419510 118617108767487614069588599717500407725110544914595726868257429622569489483479663979629