Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/0_solve.py

Created Sep 10, 2017
Embed
What would you like to do?
ASIS CTF 2017 Finals - Marijuana (Crypto 394)
#-*- 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
'''
#!/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()
True
(n, p, h, pk) = 289 994646472819573284310764496293641680200912301594695434880927953786318994025066751066111 6 843235888465494832763255804166953659073735483996382764878385572219936486704848907391083
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.