くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

zeroptsCTF(2020) write up(速報版)

zeroptsCTF write up (速報版)

相変わらずCryptoを先に解いたが、今回1問苦戦してしまい、時間がかかってしまったので他の問題に取り組めなかったし、1問取り逃した。 猛反省です。 めちゃめちゃ問題はオリジナリティがあって面白かった。

ROR

相変わらず若干改造しているけど、与えられたソースコードはこんな感じ

import random
# from secret import flag

ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

N = 1
for base in [2, 3, 7]:
    N *= pow(base, random.randint(123, 456))
e = random.randint(271828, 314159)

# m = int.from_bytes(flag, byteorder='big')
m = 123456
assert m.bit_length() < N.bit_length()

for i in range(m.bit_length()):
    print(pow(ror(m, i, m.bit_length()), e, N))

ソースコードを読むと、 ror には右に1ビットローテートさせてることがわかる。 RSA暗号ライクに、 m^e % Nm のbit数分与えられて、ここから秘密鍵等なしに m を復元する問題。

mがbit数分与えられるので、一つのメッセージにつき、1bitずつ漏洩させていけば良い。

一番下1bitが与えられるので、偶奇判定をすれば良さそう。 Nが2と3と7の乗数であるため、Nは偶数。 よって、 (m^e%N) % 2 = m%2 よって、与えられたすべての数字の下位1bitを取れば良い。

よって以下のコードで終わり。

from Crypto.Util.number import long_to_bytes

f = open("chall.txt")
lines = f.readlines()

x = []
res = 0
for l in reversed(lines):
    res += (int(l) % 2)
    res <<= 1

res >>= 1
print(res)
print(long_to_bytes(res))

diysig

もとのソースコードは長いので割愛。 要約すると、RSA暗号の復号したあとの平分の下位1bitがわかるので、複合してねという問題。

c^d % N で複合できるが、この N が奇数なので、2倍したときに値の偶数奇数が変わったり変わらなかったりする。 変わらないときはNをまたがなかったときで、変わったときがNをまたいだとき。 この性質を使ってとくのがLSB Decryption Oracle Attackという典型になるのだが、しばらく考察してほとんど車輪の再発明をしてしまった。 反省。

from fractions import Fraction
from math import ceil
from netcat import Netcat

# e = 0x10001
# n = 0xb70658461262420a495cd1550ea53710332562d2e1626cc1ea96e865dc89c9f1726f5e800c10faaa84f8f90476e90052c882be52de2340d05112c8537ad7987995378c33294651af496856dd1dc521a76e9c53
# ENC = 0x503c938eb2a9a19cda0690c057625e4d94571929ee3e0522433fefc6eeaa8e47869dc517ad67690e8c8d1c3f844f44ee3e3877aa784e0caaabebcee8fe3fd4d6ac939ee6e942c763957f2189ba405c86a0d9bc

n = 0x6d70b5a586fcc4135f0c590e470c8d6758ce47ce88263ff4d4cf49163457c71e944e9da2b20c2ccb0936360f12c07df7e7e80cd1f38f2c449aad8adaa5c6e3d51f15878f456ceee4f61547302960d9d6a5bdfad136ed0eb7691358d36ae93aeb300c260e512faefe5cc0f41c546b959082b4714f05339621b225608da849c30f
e = 0x10001
# d = 7431740025043756221515365067850832783728283232431063318145314661892911614671147927990392897931413631166880130409307412466350812244440287457800809181971129220878086928879210857936329091778189386682273
ENC = 0x3cfa0e6ea76e899f86f9a8b50fd6e76731ca5528d59f074491ef7a6271513b2f202f4777f48a349944746e97b9e8a4521a52c86ef20e9ea354c0261ed7d73fc4ce5002c45e7b0481bb8cbe6ce1f9ef8228351dd7daa13ccc1e3febd11e8df1a99303fd2a2f789772f64cbdb847d6544393e53eee20f3076d6cdb484094ceb5c1

def to_hex_str(x):
    return hex(x)[2:]

def f(x):
    nc = Netcat('18.179.178.246', 3001)
    nc.read_until(b'>')
    nc.write(b'2\n')
    nc.read() # ENC : 
    nc.write((to_hex_str(x)+'\n').encode('ascii'))
    nc.read() # SIG :
    nc.write(b'\n')
    res = nc.read().decode('ascii')[31:]
    res = (int(res, 16) % 2 == 0)
    nc.close()
    return res

# def g(x):
#     return pow(x, d, n) % 2 == 0

low = 0
high = Fraction(n)

cnt = 0
c = ENC
while high - low >= 1:
    cnt += 1
    print("cnt: ", cnt)
    cc = (c * pow(2,e,n))%n
    mid = Fraction((high+low)/2)
    if f(cc):
        high = mid
    else:
        low = mid
    c = cc

print(ceil(low))

# cnt:  1023
# 3299797009569702876689278043775981424617312808105724734787052702483069

nibelung (あとで数式整形します…)

行列を UX 、平文を X 、鍵を U として、 暗号化は UXU^(-1) 復号は U(^-1)XU で表せられる。

Uはサーバーにつなぐ度に変わるランダムな値でめっちゃでかい。(逆行列が存在することは保証されている。) Xは各要素が0~255であるような行列であれば任意に与えることができる。

Uの左上の要素をU00U^{-1}の左上の要素を U^{-1}00とすると、

(U00) (U/U00) X (U^{-1}00) (U^(-1) / U^{-1}00)

のように変形することができる。 ここで、U00U{-1}00スカラーの値で、 (U/U00)Uの各要素をU00 で割ることを意味する。

X{{1,0,0},{0,0,0},{0,0,0}}や、{{0,0,0},{0,1,0},{0,0,0}}など、単位行列の片割れみたいなやつを投げていくと、

U/U00U^{-1}/U^{-1}00 の値を求めることができる。

ここで、U00U{-1}00は未知数のままになるが、実は U00 * U{-1}00 の値は求めることができる。(後でまとめる ソースコード参照)

よって、逆行列が求められるようになり、下記ソースコードで求めることができる。

import base64
from fglg import FiniteGeneralLinearGroup

size = 6
p = 8360080291231856208342820490554787440072018576480512700791136197550784456752887668431380873895156613081656896954431466745396150329739610536564837226911771

def inv(x):
    return pow(x, p-2, p)

def f(index):
    res = b''
    for i in range(size*size):
        if index == i:
            res += b'\x01'
        else:
            res += b'\x00'
    return res

def to_mat(strs):
    tmp = strs[0] + ','
    for i in range(1,len(strs)-1):
        tmp += strs[i]
        tmp += ','
    tmp += strs[-1]
    # print(tmp)
    mat = eval(tmp)
    return mat

for i in range(6):
    print(base64.b64encode(f(i*6+i)))

encs = [[
"[[2844109057510656923952466146137977471293285267640412110199566979647354787906393156285834223940331193724189323464515484588843099726061450009464982167363979, 4663529941370007603048667089824379230877162373989378292796895584214399321763444036661816764527059996643733921819566666950119226241446224232143490508807097, 6075374380206399306206199728758345261118486866873029127956689642499175844929618387914495024344311564970148929167280642192213483593070644492944370008873689, 4097301783660782251336476972845798659475539100511854532759941471221051345039115357990798965110496117219736164852673302945250618902009919535937629088878780, 4901804800356980143822832819720501901599752314050363109376874785860871742660241152466646105755211792821221369418255975686642959683098969904231031976364042, 2258966585386204547722395445687643461819163669866968489295435430580711959935760779278933967719942319464803369019303476537482047659422762747353459149032564]",
" [3560797918639006346382690226349831460455429848252421305846093213490807744303822764946777077307885167259435429607822401980679320254062445920902415260034338, 4941693658577867681038303101840510409533819832854703323965355625735153841765106813962542715811856254964742636832021227882811022942130841930358478558435907, 4893162499985645890510568573669085120412559372211744188812438778446013560729909432354993565252869684798238658490482434629963126606700097643191151337421815, 4464299947361991331955438331982234748267010891544101318451149921762352925642293505390880056548617394654132453619952720736208234320504995053637181343236363, 8193476280258052153553939692804878474565442504868336509417531766484542510033261824312615229562242011917200907619196728508114506649233854455066003989808840, 330622642492148380105914481912637145519716547951405646334026402572081611513379423574188182190392337351753577969913705221153680101003167976781392870895408]",
" [7886637382328416017019958731061506711022902163245805949442532512620330708486799281813729634550474959613330950367128866552749824636542481462173373202080065, 2912548487954813628882397832069094266041585093136484171202438738374338958586103517803457504494620495859481994554583344693625171416901828769765136810209755, 4618213424565770411146840748114321323709066783329600365846065614659523847332403706350098558642482910217163851943566972776691293991332624500698677406980768, 2310827939353277656385830160062296652051490301038103220715145255581220042504102162372718560198671153358860392143564942445175829183892655769056111316183844, 1720630852517271021919228739118894843828437149909747954696947144630589151429918764318207550913532720574339907432163297630345779083296734590043154204006603, 80863307142524577043957449467545995775605640278801755563508604508669844693490961335327418547126029731580344192627475417946337458435230162606630029741411]",
" [4683896627467601484060512410679012213392944441658970182956302192426515153762046314072276718314075133720283274507790052350262814271141785318386673715009754, 3616549657910893463479827045131588966238817968191479219891543099222741775216875988027624437944073841822738543239967484143502029090864643009266315120483851, 7728361346193444604763293166910408942121424137163284423118402521753319882318604162934794757635001645463213506528750097795268758454238764563796287815950306, 2688399857269946331943050840478987147469925875094059311995962934264463639665931000004316272555656696677155690631708201620746426398363571565978286218984002, 1964587000961659876174873136407580254723550967367023058125238940739926813010875070266694316427146350730874711867470166409896285393583896511240460525030515, 15390954020832326585900087183031292287474451266723351241323747632133067503193271357855256697947505177244771871542520607255760409590675966180861617611563]",
" [3173551930862052224202372619428426453741833926344773441673678332786629997648301144859781616021937199647790683283980862694021670324261476791114956519752707, 467776452318537516179636947035778541233537716095434962185250647768738226941543648451220394598375954044734476129148767477843344760098791807698342130287579, 8232807472321858343360616488598825969006238178758937145510511964235784060454972139507879191785785837534219459496770549721739053048115688210356910175864324, 3455042557058964332732650066466926538831869205003079905327805430287617960981133625471738778062470080446151100262099726977114229413952823439858050771544140, 3925778235441558180881453368193221291691056546093085629719575442507425164108074468891396652205650879889352716808664348173992523215390473908898279233801414, 5703069890739428289582880383754395481288053894312350933857304113140746034412360946745677870242659697918845619766991540894460228344788824759263839094362551]",
" [616564095832684444493933086603704939423530262009194623038159773929132052409705429656362059655305139144200543675687503810364206265687175744837692233246214, 1495719155768410198093574350768436670033783204722793751717603235864683086169705356670663476028141865538459934634561739317264195275064559215677687708064750, 2423717961021113945654231675347773046952673688911165520236341403746815775346539132879325934572662283822205281033290928864839705467760034673255242526443547, 1680524687326186993223553699093460731212355837334277222862337809388867630154877198542414763552348732689010509533822788865700641653775373377403796828339354, 531609488186815098934795812181406731080934861399039702904803476563011443267184625547379785935973532131250763962689058071923931993338079240874906471205712, 6062046640329769096066347266899344676518901424429677360646881995838432089480753859799954198529491903772366471182818165193104084715939869694295808095169244]]",
],[
"[[2803821056668490611294073034573880698996327904364163613205066574880527207299722854493866385187457761354302112778750196964656219820117464591255587308956436, 3750836767514077095536483178606067851183226503341429995524322471455394778466596907321592826288496684012320273983261260963265414788261888514976099784901950, 2498981700490371942559704337778236202924549970675634909578493815912127662084151348487768439519914612466946631571922239782082288447650845714368523884826549, 515191682021112042461459536958522376068974661629463565716455922014456041016779153956872450752381881941831499975234747975319299032221694507688938502636522, 3968904451751795859948656691772943297799828237009606237467823202982212290912291340506914007380248195667843494547418040468150823726204831156618971934520382, 2948962403680802606789930292176406531977053734918306366221342209590433425253475763866493711782328378004873495308679410362199939046013134920706889527235720]",
" [380884923854791065893933128922173604072100861317386835940884870619107636107321720997401168326678319936686466669769096150700639446306793387808956333031745, 7355166896338964348820964068017746975540070022013196213734834768516181706828725637574436549441910722096531288758959579331909936735146191357660917332907963, 1868575375607131209884190402730729988169515786536777956425072034917870989758858547914066656824654657606054368715873408840836197242784739803367293818577677, 956309002107663456799742197954334274234348977330650984848615986558625577700556023037570946658382913025033216579873617888815933319169638545076251813887012, 2867727447479143512631658343669566725737044184881073732083130580175178690955952451937453413092886925959274799972772328787195086437872784209122330716221643, 3541379071797772847474309427659550464634110575665448839362382214809310378356130081815101786136105890845481980775919677660020737168957143778730376882889512]",
" [3509365376767303292637179502111115986117910892423718577787965436812668209109533654013423474593124690182153973020443372540908768559879329893825913073046014, 6115844777267703958776425796438545186188903490023248838732007816524868169775391080053882888551816731880818558456682534497400829172216539395394323323139792, 3441946893521007741421732590063713555766555240284318674271124018119364508764887431406902462550146113764240464256827512351400430511618321455132612294688862, 8044684075805621919499259109344475676664401947257944215273804927366083890062844033716393858179755212089799761748156540282959391212575121739253779025491818, 1256692924591411602725043950981066258161625083837129674584486932677229506313258150793216226803346677764866174445880703328643292127180845238971146971063559, 4716106146978711895065985653010884193487421171452106095429257594174696036182389278529271459953047149510655007835080164014679023540138865031451245807729632]",
" [3927041841574869015958598578182387497925877650197495790355915878184536523021644771481281630510006475360630571919388130010238169764501029573383568511660669, 1419852605311001783651930972445558449705617057316941009927353336949678003728606137284103802520062399161077156727109063713165319140076245893114487609944645, 2022968689722258825105433586819875651181915266699476976378626996832518644820110525812995181952968471146498123206899172234364929688662810025852048344583792, 4593859473771566885377512892325350785046727314256554621801809437883226073913499295032360693198614710666268276506172043380434238268834982567189996699511803, 8253801929129254987503976172133372692371767232532242397856204289036659250344308500002748804392345865993856100906374498197302608580988065703797896959012141, 6691040376245757985724492187892249722245968616848642770154563909932068676214557356888532073725874863775938918134725529041948065054871524880888241707871122]",
" [1902614142783282961185671980103888135270345914269236174925090709119237074230024075524928395568290135601128475414062444300707166627871076567972344206996464, 3457255300632707065900214017597628667205399353068036667446507236070617216966503672181279844757514679255314895110397886186436538671386399329802957375181628, 1763742401623990024250635529542182048583467994881024516006987992156440980472346484492699379576953398604362494717009581637101641948847382624889714515069564, 8304377857206944735354006238069273229688482882271435196903342297306201859793340201134624767980780270722776268585027077722352601642322770426328789337915249, 1031101775942775287016866592108364909981264870277981971770663139913917773964280054850517647630443278419275580826809411711239874520744416138903427799244555, 6944493149911938176369791418981045745787743620130804378552761048488359471950876111817887880679935064976749824429685594340192209996583867928799587789212721]",
" [7503815648137835623633928908026634268809031294258885949835577932991551684326479035967478500815007330124699296552386744061078390279474906126983473131361457, 517085287840211601988852717333025651543354193848581180361524137645161828289912704202563130110076170698930364863314183468128997409605722958136316077734530, 5724764168253792229212915794697062329944092605014768297918462045297662162184149766936115995003351086537086561574773654746415361212648745094116828978295020, 3639948528224714524564720995846802672262850341944997181161147771994015264205138188708735892795368527120761488028791763149844037465964179709648469762555824, 1996658703261117272315591280755250309625003189705696221886914582021672743701691591400294937006485404034508213268486922139046722585071583080245415702180249, 5854344777452763751097312294575305394885110378245323007589910653339136099487547731936058883676897252944352967735775656496547751132757455499551970245425695]]",
],[
"[[4142966158080332138958719296085307659474717767714537501855968569758510970898872704183969562028412015410390256327865091382562555916585490197551596901677206, 3309591966565927469547142030300182972401693693173284431034969587172314225378687012723540096186981934345664040301679812673216990119926924397905478453782764, 7974600173720957953874706487245414735251695851837024540307255552068202392981276531695083340087660655952495580229623667946838501336946927271970939890094723, 5947852292319848880088187514510157132800608058863460672082331054051522802043061451297495654992583303306271833700629605646551702513995808902817275696539249, 7100080830805993173052349538080494024761329429286294972979579809460279431028028974593563483053866040627311300382935810274400004739868331416420545771671422, 6558273465204762436217210307162989499667728489359642522934002979377431799100773631151220238278419661583371986060364276315138546368027535310336945680258670]",
" [2840490862360559354660829223867315195431655376210133755307052160937672029815642504039980897764148115084301110639033739477985172264213275482449637566421360, 6710234940392904619450564864329878239437191922729346269321730292801235450918443521840531827334495750234543839693795456479565117572881828439207757113404606, 5459127950122918793594675136313198614392536025537452584841784330333120045258882956470432342963862172949396736598630853879989542106646738628474882810953923, 2178572274870741909871720262271328202473789076421411154230632881219232825085148052262513138344575247014716814295471162760633570095436802363279962296633795, 3987598929357050135366978488660387267432714423171749207544118308316039894528382978157352243969276772736680596922022687119459646037986449481991291748628618, 2024902144322406614350233184927366471486890515107991809354366260580482272527636329402329397409634649458879747700584350370572156900419424472868547186593360]",
" [1498492921735640032986138858013958757519628043121172031589454777341434900343222204559076961695754179170730082672258120917458239788637259913772898361521847, 4864344039062918801025101278865083141322858986857848293898712293003589974382160530941177875846399027389228962349309222554589076119872103474333419369053851, 2462864971287447708964822871813409504140747459549362890067151215613292331696212627896633552129568697175511348654874942332715044494016075272784917786947218, 2623588663724514586603028974920037397101081162205258258310198464072618713807393699930112573876157620581559492728800256794227874920840455057841204267385984, 4344176111507936643938257701970293486790854967904547087244417044486225512480959311202754841913794306523148715533359916432972643555060070985084871375458635, 4684429010652906597384359986697493707480954795978106655351181904714252698787948384322672455923378033684337433076559772457714364710895070852720903248048403]",
" [3094809101588133868012247838377864107063046678418484799557310357839176311498648412754403353283488526446663492189084478143087631556421796037154271613530982, 1218400677817303283419143220351644298083219232639648088727276181512443774345428394435178602717321214991504434155157033450518496774161363519006999208996135, 4976753807830652142749798556684057210150843887981733255268786503127364803970061440811526959851457134202789772724304527348366540795510690626533948343450809, 6306187871445324721376028421212670926552209813936211954520585336810602819267101506169718411421085148520086757665184120904287963419432043464919483057889859, 1833106920968942472486810225194666867138304485980231800031340809947587741111962230539893512445140276665700453661111529177756750801229299829920856895396686, 5944983656008702843299825744939879522916964169773676855236153835126217946521860091930095349890238031759118454121655056243894407323812224360177569100681000]",
" [5470100782607793034630848954199211025033364467462884963827914367440359149323628825139100538085878619141578685582945640118065146890881393360543180203471251, 5171544658380490479076590885600853495465746668635150049085401445916609195612855329299638211404766486396082950210344531073980204186651305524726021531325664, 1244059226470035685649983657879334539158679284156712950290916476402509092101488788455310664127922470760345136669007686978437241324069402309374833631914586, 6967709626175609013358397510337425358395174371229548954405617743045323413987645698831341456070932190075222891888017751268883695493968837263913485133305445, 7145820732880643161292993687975828061608307352265755530784841001628971312586770768906184846878446322646098014767246222344293599082131962615681304617559937, 3552213214242624595495939080725627959411013586354641573603156281331127763767251533180374921899865664711745093743958999874317193547172471377963591251620128]",
" [851140108791000166571631972962293784153219617798846393093315381220816911521196933317687423641269525559585526151386313107528665448997595805482294246239089, 1168888526444803924291868279492845217956322680712562211421799837645552433255744395900173892042349172636688101861404896773414028579661301015641406267503827, 8307676367556241030465865911667154755418491039388345767526932278953889131312732355323179135364080085649208641044736578248317119148421511456627180081650047, 3111883634392521585662726441377712558441898247735045724634797815613834787479737455763556806453700269602829897176786944686912691419674834905293916928612403, 493688661625095845632754316439965382734982826018467933521946919606183875577604067566523895593065527258387500288356968626006667045818791030945375791371265, 6672246490840772483328152820802055369074899989726836656614268373590524941644149544728485295788618518339997370708760033538160320833911042156114289430168259]]",
],[
"[[4294586530722642936230913732280313153324014162135400081989906682467693258981754249388650314342909302403332897052040072868039272184571093012201838964340321, 6851311731105828323508935384408131212989592492085986340490178394613987804277946161747269539307822811773779910247817389225162805300663748270666352664694912, 7445848879449328490484858548937458836874810726938013083419359083403063924579619000179125578952358903504702986501722634764413336868852609114220231520158545, 4245331744608409800948251415401811315377043954627846503577483698684091346108485839172854930100465318721469301971504574388329356861635386776340956419410561, 2524164254835585858547575249056871436345007554440042610074219425984917114029395174632688395035896917704724223519178893446799155149468704315599439767740341, 3079040969490207471709368741103968515943143091614028783336673228555732331897660321609778520391062295987199035149198223393401088192203747979253112799218243]",
" [2188125640236177761325853053554464439600809922713117197060049687812806966237022273285130579917715518193767676797779333918486292349092082957639341840012013, 5954114384739037961445602960202347946468372717550983864767105412181253131002083972649921499389197883776500760554065477625866643754140920892418175361034094, 161196877018423459477130072332389485653215582939061486440276711149514065908771227465544969481870875455750990873044314177330347591481699945563448476106124, 326569940087117899399973175118512397897376267722474819092581847150412917239894174119650490785178420070080189450598743803454442567987772960256396599814155, 3301252077380374305512176550701911384544265052352967816266146320923681951255255971134223651300690786241704021739952765315676883054879275869129174259833138, 4568088877791822593747508913130037278911145087845848022704553886229696822317289941498149558482536793473292305523241480453324020617483439539823637562939729]",
" [4142235316184468155383946652709310109790206386549011396265857743955056144907720041893045753774796277558014951898631886253305214194514850581636271448393150, 1505860708579779802632551609865947381020054803091214304835576473913167770033716516183879852424809444359212477179027146718823917701679872216146098250842679, 862995457544552571962897078981704497509922344653036387641185203310028754124566465543795764930760660021518514216339207482103458418097936687140867626651664, 7380999536553929794945329323991276296521566478806749394005852816185202657485437751515555741984322082870761440982045522874765122086616393453518624288482970, 8177872865899998379874804144179981100994754907286004866439820048795477109627968466058964166668732830444380212876099032237429298685424283843207417850980482, 2531756810425209693207802343461520767426727495074093780005982524948202502360216494748505421706675070560277994692428742114656094151005599015977813566066854]",
" [6012413239108225185118846377674125100624076533901364620955031609880201868348953667083753300650249209931549704442244703646690580289154360443712539662755906, 75478720791987570557638978786617957306242071415729697405854434163206571125662369745735791675779117818890553687862539007518050975276162933287153763530183, 6172258191234383067466415025066292342453944633150297681215825916136098321483099791194342067287913863085527938439026930327889536860415583600549645261495110, 3478026486685252250847811456053848120324037883921786789252387532110297642203456951104817930735414530345554362717170717556082209886160388068405878050810154, 6091287475937491835526776429518913507657248887272965960122968835469307263017006291508462764133499416398582191523731810388969654450921326826138469146771773, 1911975711851516766398139407709197789709745409969770893108067454436507668646905680603265654282908085373460682429979016499086135730542393136042776288721287]",
" [247607048235078846193431949417599266918305741095175921742741844041886801219092820111970359780202178236269708009124884096234721191886888611962939880229426, 4671245859635075958942633991095376060756694865947685266926252833023839845188233941081884357821287893069593523648094684543533415178614624231307563823351401, 5679273703503918152812232669898291973206737557660055256657927379386522628733001757224178668683554510605996983938105909356133304870897484424204292205515268, 8018681185256784871229059492967727947760537261542163211674140763233904104139454452148287303774439729091138652291781142407590925917529889531270441139906421, 326254091227477180817965783454170870965767896452885532388493678916823013955810072598402438281924110666128100203506218327819701065408806755407311242830738, 6351764683627587285426254487172052276822980587945584990276984099405244031268635472275382151114691984671543910569116020973818432007400352749043075924267223]",
" [2934084480818665892133298175315611662675750923848403193702575234096133696704420360408812922229952046664786077320398073567283595477092331628751168377260429, 2702971780145465037755452475002972037641878795501654571524736037581495711555764515048562443988879558913647148233447684313507383230737812824146039564631438, 3510009608744725312305137912397957487280451619075546442470816105919906071151134805973394575081517775238921146826060832587697009202633665010598476771475590, 6735600497877785763985120635749781510954256265031451120044373628578040597519091505960229286345532799033567933441513361675596988204228241092707272486292888, 6331570377496859138398107440177059495573658357208322202344572810989546166661904679486139998148952954664520480503964828505186604944549915552937843437842041, 1804183631544749515380449970137190291551922148246932745543193886115473113238103625577173800110106738950279159165741239630881015351100075657555603208156572]]",
],[
"[[4968683861434171684601355692918598994624099811023292544468652135223903340511708347656789843705004960932393440027854713788525353567373860981507177649773607, 5595705002215941301409024503605721013015469826071690246107482152553843883028284949629950173462732446266241491392805161172384971684999868394197385752445416, 4286737153216173284787867155801768688108523892607929446668619838061094469705559992931980174373515069746066212838661975545002590656805380476542362725271002, 4204089108427436471216147684286411870141895429513017452488126013324281584537102445507275117430536050156362238289255953854213319803935756225117480218383122, 7025685473566478581286387054433719733553531795177678851985157113053593787524636967042269532802589141046592866977635514936516421782571173890597388207549066, 2463151706292928134891805524035274511228046219919510900408646388924380199421744453651847970686739006955949047186310553858056367105435662313213560456611531]",
" [4891527949940283099704697375041714324696439699082778801351762121938023616389973505015902221643933993175633995511129719111111377890060254242316545299417420, 6331247541175722843144833572707234301083196591139789644478912381354963485110531716582045185563188797635804761631567751743454531102308181403317261223067742, 5799702271552974587368235497113879686330801757476585256123218040617018568872228653730253719132930193061792310101890400376617445858815249879062372000716438, 5285071254826656181653411547841011646885877919352437589006365716334598210869827686730923415703151160538179519148097034508177804527471456572164849312356068, 3488593723018207301771020395877467723891293176723984258976551897896959026994777540305049609868261458037510023081093486672385348566220154697985135310193265, 465709527067128858974544819001709341513008052107253402519547367834589105697731624901398498526586170910264575721202537734329710985577791449558870421150780]",
" [1698775592830292691960781606887432750870966165173163801511742508351163518732004309112679665488726997307678246989684168613272644762573566694049909867786018, 6762456403165987999571295806935721686561535240411438814452191654809071301774747496301954790819812193827548020001965946275168545485309758940038000259894263, 8053208397205153224118587091941600612430937640575196082466581194373539361534742933993142648949631506019331769416346300029845044434278396155786709863703537, 6431442883269169587447201310292427891017337738666403616507728635718919443116271070115625638893805741562252688290536862255276990999879367754218615944598023, 1961577081848769881624530167388862458722971960047725591513277757972073277689436266637228137009777776001198006540392563233620307460764793210325708393063009, 7424819120528389039413166367502911790631327249932124307559542127663595902765071804368418015688682978263460891327002176010098512425496964487473175150580122]",
" [3099133037326574470019999137162541445312920361301713736369120667535904254578401662708156610175259332217190643542103061411495105834143373870828914832865002, 160238057392934982555975349611915781645837143713073615920183996903380864206981947105867343162002258474414387207133979082728320621468604309781582511951088, 6784949222656838334237227879971054289305884844425125415930646871142470424628162894774062159557013769730900537576805399947944431961812633037576246377668286, 4771991159213767563692205071745593603786155666455449976593966887126725218122123840771200082010022206861827920348139510860675015265589355532522990639810817, 7078269725463557296288671756507332416717134039679973284500455716873268888041727604449078845419747458015337409768552405138320348550373301903960780110670154, 473043590696156651936592992082529722952354043415035208698954788136973319482547878724520235789279992686903230572966197079862091080647225480694318877833097]",
" [860308360952054463603678554832209063987952481311950104420577800427756375927658911446570182349376521237033672859268913636478819317333047290118814508992452, 2117728894428050383781683349187845909336374723736919669859270692153507231933166548223872570008851187937388562590434330585430194758410449595201932226443889, 8197401845415390928122696895744194618004324526344851368231497739620939364883081065838752969603564196225450709525862159387503489791210342588632262466086030, 5334112205463788971332794524777461476265456087847083142753118864607149081798628939642108149251407866251517469948458833865202842305916225169609197315795727, 1614395370662982438105904065510318843109739279928729356829880223846164085280733154395904831113364353086361418717316648687269044568724510821076200388146799, 5653475264208344724309438807566406059607008128826086382521847355847734504273935887555493950069681121059847823271259176920253273605885312207539937539689914]",
" [6340347872017318908956894333407476397371496893443498190375890434197631652422473272888132388384427404544861194233523006008907232629502099183597533807439690, 1801763267709706445555844426959376327673666215229192208493921083690341146196757120470567390909286925855189584391504242923326355047471832162200114296386911, 6261626742078680773544091341916225211553967093815659620515961025963553967728687784024755382080470242071300132301028574691902557046582094732660761872983168, 4660397716658022871431615792588400855257650927421683461538763978330776157777980889890829210068628374684814758277704148006747501373072138010147591119895919, 5715475719538182925576102591997075584923997141089680042140925657206830065724813988725465857588803734171861826250121262083500742508603801135822041531196434, 7700794835235627079708396467395803405253945316799593198326551968277842336451710680326440904239414627790908277676500941871815612380684137252049009143144583]]",
],[
"[[6026074209279274329990933569668284342503610816563732250654247650674363804660211693285032292481354605420362661212268840643561949774509472817713328688623765, 909265464923786831978209284919880039748910840779768796419560402642413357343703937209973221912375966203231053118164109252039042853920177799805704516103174, 5158778877844193855457945703697926036010006996990419695234126858259473532731325412517070938302865645686267247508514706751034400415632035076212920878422576, 6070474262657979178977938347661660966351994524295895375749070433356950251514118757368845503299007167899299652073996215426524153875420265661792231754887079, 7919681353610591216713480609154619366228624975958065021280890452861263460856957064483441971552814364458934332972301632169075236237746431462791971249801831, 7771845743640663427697751161498079799580920523763081040177308355623663654649248055735868212826978177248773758139438459769910462618115988338830544068378585]",
" [2858333287432894788717637973374075855887601445385187506076430340303150920651992568577569802829952112513489114683328642851829498455744369082012778154906666, 2147863743702927379471013395121431888225423219634031486896606309614350211386659011116045718039977043618504300347316373917977349212350478123296759318796773, 6898475899408474684193661789505079425257427204739916629730618697188816139730012187358851368029282255373737626083372988331451791582790305710035363236959336, 3509338163209541637005355465942153610385634020589949535952926042076346456968055895321223699750408090861171600814869653793502315828908555578715033087896149, 3241592416202741216192687999950150744045296387443426578085929718855951296491032239447448473892111884352600341528256403833356980243026312896400575656049809, 5789458318992433122033130154478274178079166374283077681307396263075408723093607935671594325045057384123641606218001182051391994886038253855366849529354753]",
" [6344734283849448435040456120881038004894442078928666345775855613571699888679383513902187131582592735413062485915147985358493759047071343064236145727908219, 2919186457664364434140689147489970659081118115921303679252481616027317195706543864009789709548011945928680678321726205496580911093238728814017533667594973, 5641011729571636967413581090749612826658826261050023702081301346576604566805849840103569634482879952047204742375339465263433179139875477538150726701763265, 6648778066220911288490633083608635846932196677947592098351814691279093080035501956075117122447914641863393811924621742329179392915154448372371014065504445, 7619291037330181094946596768025264171717411660456382927894459664090758812717122046283771698376285527937037674035398887373177130077492103742062212886163025, 5642266477967826822913189671524005865414019376726305508463935836642936385469546081989947849866560577494659019739596070221094118703247102059464743878568891]",
" [4262947026630164601858257129588431955897190063963508972179727886786019259048968177194271008752391161568653004262683974674414149273856486366228543344913000, 1869560572007735124678304924227461987092285103203641068918925148799333468129332831832870895875917780813031821937201367347963933727892590872108299012005869, 5755029907289847859049113746767461325074061536502133051252255981211365749791511858197802369296271568697697709341939739327750403558317960291951172764498781, 3241776025309710871791852789847911737036999175777475448208696464457037977086550412211729231764676546174077682994919805913962597750838490410677877013728679, 8219268112466518365390174242457284021680068693089614302528336198136387871485670976958645252762747084522276720090485457669338953541862551371200885270765815, 1683726293640745842740690561302686830031530461687176323143208659837668235136711057358493177404064747390647736777994614018745841060015177249145906861105473]",
" [5065978317023450886869636923128240935192234622477004794992269341285699515157069559780410655984628572299512568759480188645284776307245338451417439134381242, 834609417068851012804881790592092206146283825477798786079589540168257196863472197624866369199517025460199386220442733623568603104317650584392857367233381, 8323036515592231699175116720556320612328626764120469566466703238400941700366660438206702621802846038596252803470969979900669870335818141988801335913197312, 1360397733765332909364374129600335209346554498028740392100519691722941406311347756497423040440596315739821204842341334740440306545267896315279385209180102, 2676810376308276168570457483867670902787901207942587380088818908288267563610106817220355331680484281456097962585320084246177558207079050833163151172240100, 5235304962197501762186977784019622237371274488352582544352491891989926021338490722150706721573792918987895316036714533978543263817127613123649317308494547]",
" [6834288668098063589238774995348641267783026738082709752327889836217087372874387973055669326959508393206838052929912759681026360888464723120042349885188434, 673652273323259000657228240998131535223013486465728777271551865123550251285003576138850540816422919438741762970198719949755190787198382360763273312590315, 7212526317272871542189039326192976929138398259716565154496031930321310719288306828588752473478544979007905825037835297842412849240912391179000858676799712, 5251885809216336886160723907008203992087044109974083392131987588746818933121837766428376662469891136113986104404675393851386590872504064514493464555038925, 1651157632355642135828289539558817376205460777539819298783108948714324618572576384136957273517032073902785009635243894065127631582097051032304091520027841, 5346704789523742907790623142409450623003295048473687834443737913041729246709285231357410413236097410528723341348129830251075816904565861886692668785582732]]",
]]


decs = [[
"[[2844109057510656923952466146137977471293285267640412110199566979647354787906393156285834223940331193724189323464515484588843099726061450009464982167363979, 125916803622691675236944550713708261925575740355980424077863979267031143507142192003574195189606667919494728339899426590217941804787294091472836181979618, 2301116634732889691363783861688383805064805446983873924596986057123279745240097714252600957729107714044009450138910574228537794368157134175788489075101887, 318718888938183765413971514294620140188603772378957854020135927374029520979205807536035574112228698461453451334048806756709044268568170142201246274686358, 3581548137718255728735441891380935286649671069122492881974861581931460069998261032905255738809084983342499581115329928181006735187866597554565940406350071, 1932683864738983160770065609046590104547856589329224769538100818719624851753414261001979606628833175081417784893481924555671396711895564910212218499713899]",
" [2691317270866646045841863507061509422688151115399279272371014131635199743858944160207654869176928742872340793619768467281473074230762295646747198713946222, 2803821056668490611294073034573880698996327904364163613205066574880527207299722854493866385187457761354302112778750196964656219820117464591255587308956436, 7416674009208964021097121209524722754130842961724743081225001189966422801760770094830849512824989896782951038592712997139362070945792784323896787016169498, 3719840184651929957984572911239124079676389954211575123651119707259410824660795471354443799954849344767103278906571962515225176776757396456460541090109094, 2995544769758489298457142704209171657842738808927299330647038687710285584575338814061938327334458358987508853584418885238419183886108202465972930887110887, 5940859133985870915014135841063105428429837789335747298640249558337025498825081253006863038681921317009963110394635229471678948725009932123395016843274036]",
" [6376082358307257451205749418623852069997118930527314479534416555061858248170276757794093459526296308636373578776821341205910374376279234772810872748881983, 5066085503905096161136623097858570177957856682751451379070933347866958687538283356956487171430495292006265706430883197827230180336457644140372104724328334, 4142966158080332138958719296085307659474717767714537501855968569758510970898872704183969562028412015410390256327865091382562555916585490197551596901677206, 4616305000603287130514044371825742017052053964265541993650947153875101145638101586361278669954032766812737814100175724020289904342726054385277067676286804, 1113166586662803480963680152395157664454191074594839033967987761361054152225757464530635973020791602189280083008256756203699233356957633033034670156172928, 8216329012163198093711885101307543317315889194811330016537462700419616347968354448796223058848426932258539288048586370741307658014138324630712418973432157]",
" [364144574555009374750297629257274852374873723241785904499383818065495098908411646970636775717040065121435911253901267143831014003000039425075016593782034, 2858861295025590619087561528126895614881737776383493147663429048617262956170206200354493086400425789054162639058587230773727350065071069269350309590382596, 4264223566593622407978704074379629908789895617004358370463725929072038443697798175371172235998190853788062285303030286777519421275896099550692440604442681, 4294586530722642936230913732280313153324014162135400081989906682467693258981754249388650314342909302403332897052040072868039272184571093012201838964340321, 4091451910401992698266846737330721816141689812358014978331516770284464442271586784945440841874291832834672748424139549035428286622373862616028211338012061, 6438339303446640067227579174820262172629981330890794511531592941109554289154769324894722805821509664279434967416237787981010479929922911967058929166679865]",
" [5587093334135995986083360735485352854204527368470966702769228925775590084206906792273318925629470517002469802532918770202200217394138681758119484325066414, 3593328610123630778194362893561992060897854624730802836732605699869636402914783766363191454248648305612169940263300125706226785753523449789499843720440358, 3588030508028373611956236719360864811827502120910892768736216902649395284530510962777095486823540689694372081471034907908333781589795406000490642488041949, 6459014302685621753137017438065170120388446661864597875000129904060489261462745479477730691304387568706557792731987212886798260259885831493545409654489369, 4968683861434171684601355692918598994624099811023292544468652135223903340511708347656789843705004960932393440027854713788525353567373860981507177649773607, 7233689984894869853565759454569272654636093458603536889360627120961556618496782619599624378501284446870230187889012735008829819516472168433196508127237603]",
" [1945846165037523437516007090824291155275598508513657591554739203953826550004896307961950067281013940665818485203222990124547430406790237630242537045757105, 1102332120520063207293963623066527250484197278409152148555970978042797699606426242744435378285203945667722991845746930315998426492487436955497858827380329, 6644551238015566636915955801892798663419551962816439736650695789330973509225903446281229957833585877801555323798222450360207463711668293923945603317882608, 2669903916837893511869573380361941722065271422699858673015676916787860149509729586702413980191629024230851144830580838295829430204275324666071004934248179, 6217455310432758496081099525018232738411640273771126540899100532737437894949526826114679009854341393425978876590691222905876917609379827977150856405292547, 6026074209279274329990933569668284342503610816563732250654247650674363804660211693285032292481354605420362661212268840643561949774509472817713328688623765]]",
],[
"[[4941693658577867681038303101840510409533819832854703323965355625735153841765106813962542715811856254964742636832021227882811022942130841930358478558435907, 56171036128205755508538883963102969387344558464074098260555547217734898756638846378122970948913199830771092707777015698772354889777968705078189427181854, 6136910796662164005318180252428152756538635100940303658937334261945816257239532909517822522800060910877696064358242455528757222352937425632080755535570643, 6575029294988852338910771857289799382124197275600512689161019702859051570531333559918048551982503481396090767310523642336090023288588211266526798423915203, 1536593019898319782004109596204518227363355012525799598037158964058749260805802603510466868822335287693509076074505942961974563287211708993398495203027353, 7165628519647891975965561176354464305529552416246459135682260620798703689880463230701330530599818131538835341567069795370681541522412969700666271610502977]",
" [6608644479135878879961825267876166502003041756536554107464364729439150899307064811380614092195919101042854516287180555508113549664681197773924855302077717, 7355166896338964348820964068017746975540070022013196213734834768516181706828725637574436549441910722096531288758959579331909936735146191357660917332907963, 7997904514493817490586518572853164792048787226390785788551843811891786798035373096802564620036519892508964279551129533485642605668581577457921406917703628, 6887892800632606484966558821910100587474377609714336387215011916998719144166180216376775746119340429617469018718382473019320602847288453898298013618625672, 1880342575107077139310453841624157122627857267706235649672743116863424533690342105809373845174660939915193088657359205926902135232090322064962024549140331, 8209966839199345636176507549604144933930044434533882499384594299499620447950333026194246848876698349809284346969041263670092495850625513868459415207331293]",
" [1539425521774194159103749134992077113728917995375408476147592683150250155998443923659668798688032671852165800007791069242841829311771687251398346216852039, 6339191367272680905832707192005648733065964384720506610953614140382168141137552804505989932753211729812892394500653203034510843757056387704423194592354712, 6710234940392904619450564864329878239437191922729346269321730292801235450918443521840531827334495750234543839693795456479565117572881828439207757113404606, 7317296873783588837226089832500656366101062036385800804765238510994442328971968178343001888541022192242079501390014957341979886899161199213035008572713419, 3165037339984685931103205643383245621113545665082925694243632527922230737221604174919378736040017933838598333250170888664829181854903491324046610817342082, 3531261591525418419516039745535954920523249258954899083880341731445279772807798631871211623073404205368112754759178329288010056968576174335619638125826295]",
" [5204063723491395164990632503029915007599486118612882113586609632013943809054391382895377849024452784264411336649522892824154686936348729402865052927664731, 3398040247474293255865133456998190360562192505666142609086019263717792331578546567655781777245885805607693539548030290145453075413000418755157866736275022, 8205373056469945005243614638634735238748657099969778504535202804165817976151987839248794088773952900089951888388680137769044913759514770041717505159070826, 5954114384739037961445602960202347946468372717550983864767105412181253131002083972649921499389197883776500760554065477625866643754140920892418175361034094, 5553196416270743203036096331868866135180441744999427545785206688761693598557196098777463203340235933924825359289835743632917795730021344545672414911826665, 7703609971013701061033433064764787030933187045656042408206018347581350091770903003772734923115290648827087472314637301867646445993321820042935303426444085]",
" [5428421476705708804797591046800332903917270814329577101043427295849392558464636824810106143836948629832913405203887906542694982280317583695740776781685978, 7808024587606381841823012626694158383559956351297545851896267128157284093280307059390301992332006352198229255562903928114383069957165592046027297547291208, 5557854276381146344301338564968515042781540284154192447366776662721405758456202166909698765387912756786068744274097915604483404199857965374920308024277502, 1186480628993799509238406868671529548036728026210245963073518659436254029535526137519999258410544453828223237435930081036049062573877578921127233038929511, 6331247541175722843144833572707234301083196591139789644478912381354963485110531716582045185563188797635804761631567751743454531102308181403317261223067742, 2452607997188601940012581768760483474370192500420900777417313690866068695293422376404019750992669006376665329160197967816780539339986730346478453761248568]",
" [4051964780981721538892082627724566661632802765494656781895385914849186941862732373355616633061764416088396797548173138170497410128113600981520238816212394, 5442598131799872257365547011319499399904328099429997104986567216465017344799976192299422328073001764480217561658850288034925157546543820236297579425559516, 1335428489420253557529104258741582963116885318559308033255904033006750289486781668030090459873315506801206960798019731486160673014810731061840533470808219, 8035425483059224938922467922794604370628942801045728952009318306136251266217670866370498339498092389841679383834666252775162628045178053924972937568748807, 327862721427656078695469662045438319136656590718013216222496781044326648606852849035298726678131030847518281499963931064743996054768383423962543795662429, 2147863743702927379471013395121431888225423219634031486896606309614350211386659011116045718039977043618504300347316373917977349212350478123296759318796773]]",
],[
"[[4618213424565770411146840748114321323709066783329600365846065614659523847332403706350098558642482910217163851943566972776691293991332624500698677406980768, 797833652665786793611580416043483828968635724808050836936686284384288339874063909590210156337886279694067425375089119737969132653776565161006552634438777, 5074727449642845050548866024415222938937656270779409966777004787922358676060564650197716401718542950735856848360798894265170697028517868194425580167317106, 6034231640855875550713768013713537478059561553103969817356312638994388780709053787190129171728830136469071155773743802883520123198040378490346819960501035, 3668465071934316173822714740079284165491129803550087860690273712036617098296110778788943145288839852554180019384291106135558789352087057450692277214886858, 3646451777707571366690402280701107003450433045113342512743140688509051488936457321469153399682963354265264518320373301379793541293214052610141413314092676]",
" [5873140898166520344390164680198077282484427275978132653852328196961186159448587863181905176206158917851832904142521515321598586336875929394975184648885399, 3441946893521007741421732590063713555766555240284318674271124018119364508764887431406902462550146113764240464256827512351400430511618321455132612294688862, 7104921243735709731265242482270621705186914514258311345546176216299935571689923362380965167531067334857055001586546932040743128151797043165751526223349496, 1952732632034318055372601298963831261354049773018759250909308552680612576341102988093171040041432875677544549449262593590884103984847130039744898716911251, 861050253111600784514967740838855856694210678106908462736687233622328317244905060748728241577784094782437148665953059153280464798579330360842182218772070, 1779400964077963275269919475596752980144598164803349120181828124689374764393210795111476507696106106279362644720221184691978510520332784567657001049192067]",
" [1466351673349208425635868506832678626425971243915771149541555417960026500356366231752070753237087635066517752816841077548934529972754036796985785860705389, 8343267038136168252955315526973295394969412090232334329437962345492898886136512021569038691760745811930327312086280126983058509149092363499993619206419406, 2462864971287447708964822871813409504140747459549362890067151215613292331696212627896633552129568697175511348654874942332715044494016075272784917786947218, 129749993256360389349676260422988889733730113606404025012820994884340607003087642049927195909122214936401271588007158151366475169094876977665810741835155, 5489042892453908057602400782439519123177001149640230172414231339879498671985910167630218528920706509861771611063590509906159926142075793460870451169099750, 3510011116550773352516395906986871266038212319222011400872717513555679891579899393480777877925684185726326136902699859805899438183695701819382015278422217]",
" [3346233429296957306814387562425616675581515073080126756998190338084188359231153260593380678546853944784137138359500642062265091186377055320153308711959357, 6674450588885860327145530960825581631438769858152132247294446186819959456253107436959924296952478909529245675138682338232965585020869723858678551711413049, 1671028109195293854205209526893646252756854484887568775126074644383503273079390961081836592023149021257608316055332871183817232777228553186819734015904735, 862995457544552571962897078981704497509922344653036387641185203310028754124566465543795764930760660021518514216339207482103458418097936687140867626651664, 4097624284239463293409097755185003822236306958116960040445900847305145463728180796321717770886441788509161889425577363521121106699862791528562241301149721, 1168000093293649540494083183331271443062968306774219328095608943035613707675386388436362968036647528512821524896194702042471212815080704564629805723506240]",
" [544237836178792311834851103403069780813384605286274102856306992736455826856678540340034633965166932251047697760630096454307857933690845741638214848954216, 6917137412015796267037919457778857176441889792058781318163072406147330212794145254416925657940593080424796534857373501149285623336153554350235582033876303, 7749149334635546934299245786008571752316330928013574107506253746586030320370782908125098460411300758308607464404271325075079038281238559677474472746948375, 6010459480645052371578334738312073802221232667371338467608468494169382976195775981600713016439759648301958150036030930001577898158822621808638381275987724, 8053208397205153224118587091941600612430937640575196082466581194373539361534742933993142648949631506019331769416346300029845044434278396155786709863703537, 2613992124586939315486854557910065038469449414282516834884104219423001547527692668102429135074492238815772807365110829340569039761293584225127548674696168]",
" [74497055925961749021449502070381123451196923510452576765937746007989994193549226001616204878794708122357532651921737280680166307935457788270712113761456, 7588257623548625713289457954468579278674145819181185052222613183473418474866878301242769487727805907651384983988402794543196324883901900406363777733603722, 8304740518227692028080951978530321210144770410519999608197851220506595302061124470335554509980637375785937814503494452395699430787496857740874803678213207, 7295692695661461383175113151202710028893599170744867156457570900261268643847310849733886301356325424424668391089095052780916146288963096768973904399866261, 3014151605317886476265608585006133585757671383824608897419961767831805471356192444153734734179027335137552010763127797288433105271279054443395315707533539, 5641011729571636967413581090749612826658826261050023702081301346576604566805849840103569634482879952047204742375339465263433179139875477538150726701763265]]",
],[
"[[2688399857269946331943050840478987147469925875094059311995962934264463639665931000004316272555656696677155690631708201620746426398363571565978286218984002, 6308029144747958665246395708616075023307033724731211689891994654289888562311295551991688974349818166974389110403682827074289995711123279546083331209231265, 2152011515980725420669808885317800002590474041895676686512312738664405660018781318056249819885058019476733887657564482745536452249481178512269958596590230, 6819731034964828931841686789033658349304148381634985757230241695469398774621581755474573641628383386570332719916439712306669541956627644269313092760876260, 4581664498822654567804201699805726362105886776941844466771940157621988229894102417300587124552394707896873994045201880301439454981399869890002018631403747, 3790391680081197414651336448070665979584574578350631658103571121492434639726291911403471102378438185563920630890965302942457212967437362833437120082704625]",
" [7587832352708932802864674791308325470365692592839142580958969033771567213442408736119921813168087877720958630170523851625515148628144664231931876956707386, 4593859473771566885377512892325350785046727314256554621801809437883226073913499295032360693198614710666268276506172043380434238268834982567189996699511803, 3012930839631619751733551074850627582599372521869098141371338458050841274588801535747637882710669197517797228074996293626650392662390972880329743724246085, 6046444396333509512662430307455624543969851086322401672840058765815134849226896539102363961646080461358070544881738838509556652334974165010886960682947681, 7915038020993086428409029784703089142250356894325456099924117499971727953299963294767668921362215306788261955812719283693964181938168198457511002286663595, 3700685951509570395835732849255994496145994869449173962630415520447033149643812226050198594056926221940113818601235744379493910952998116767281520012438180]",
" [5051135080072861288798435824503110926994493619586245642460877880935752533515940196736169083797175764433762946678725893887858519385471685741552158529711276, 4102452874189482900524516981356786501197215832466956832817896838054663136765460104493801314869232759245133030456663626153667325758368279203778403432167740, 6306187871445324721376028421212670926552209813936211954520585336810602819267101506169718411421085148520086757665184120904287963419432043464919483057889859, 8328463466878712357313253597849642119569898605708059781061663754766211682048352203469195772736253373810214056772615440398633838901856411113830699894028465, 6792826073105939873548388201953839873511062908686062106913623174036319189281934299265013193622515976679150220086212298338695977994879351935051323515019725, 8222846534254829017465474490124055984869791814151427753473235321005609679939356328656972535469231806107671122663048839094219850517783054335244532555523173]",
" [3224859092637084414354411757846114488051905333691150307140504291739518185949079400485330657809362670203758062221915633950568994535207362393891762112759213, 1402213184987687066473420113301291318947369461630152474675998702355080682116923891579872909936779692586430073361789636509965905709544271009812782560170261, 4938156402135532483449602834359857275247357120687553783936631304847299511487993180810248854600136936744615435937883396705582356322840802517280942999688676, 3478026486685252250847811456053848120324037883921786789252387532110297642203456951104817930735414530345554362717170717556082209886160388068405878050810154, 5005068559735767319230350882159667676326296721912586682081472060979786792450524503756347953787133748024741685340873319209665339750665659595129267838724047, 7611267542910413742864285271293198211217621166864242229900616279101604969849441935423682615592901088027744831142761813333332038967085050085153868636999389]",
" [1014414274464156389545887226471576007761853927035338985136533491973433772975257339792553409486536524724353149236175919357824388859589016173188078077544033, 7895138478046132656991279703137609694170854693851576758647957367888621325306284581080934827097026107157210615304175172340829324703784897725230628183706786, 5176615217071731589702948277923734636443872704037638473482289661043716019888704737763354260348856139062485783768726715584135447436124158730742161914891551, 2097836864953804378531689095465408458369427097280901198203599718467594836880835567307831867127941722028682757812487712436283696296458947234888473138795739, 4771991159213767563692205071745593603786155666455449976593966887126725218122123840771200082010022206861827920348139510860675015265589355532522990639810817, 2556505047659214709675163115561631793697740584576810567166618831599306359182599941080724275734024102715328015954454731737423615177051807859090091090443794]",
" [681533232518836985289954800204156351077079822942520143600452578095367034898668130667529896315193148854619919663954540988289801372079675164665542460107361, 1250221324909133315777380655846656103749650131290697378565324568377782229062513394587727898375482701685037999041225396581295398170197587722204515994930450, 2986395300837570550870677677696621832455805179189205862994626042937278335849178892402982806468533967804109247741429284249954632439250338615415480008234827, 3842018511852504122498199184515997741982923387046998311137498610169243624216674767262683322192215528258119752070686830123883419745010157250560986939427524, 4640056504383112245586533751493756860209550650970050673042450028152879682379483766057544789016990961020117905189009677752546361605873827041840445232333009, 3241776025309710871791852789847911737036999175777475448208696464457037977086550412211729231764676546174077682994919805913962597750838490410677877013728679]]",
],[
"[[3925778235441558180881453368193221291691056546093085629719575442507425164108074468891396652205650879889352716808664348173992523215390473908898279233801414, 6786236996055436847088656629009571857079021280691151803850611635847176412935426902102220660966708023472464567722741215102149358257283707850226844498176338, 5336601022505450016415061694023852903796368651287115305963559754445490803150781351830931355559102791684084040692129886780782904068496696739166373225781182, 998868830631254637983637521012035822140662269216170110192996151931756960950320954174523240474157438927120506516208572469379223565138309388961430181881695, 1708759996913140886988216976125001687286182686839095567390266582350483709924884932173272391250162358270445073028626761217680251493023914391510743515217811, 5358389653989286662502363312276141964701054873298546069125330585565060633006885059531042580273849934632172848238339750423863700593945261237875263708271576]",
" [6566818891908601642198888392330156930042068651759819152370527365997552190681188977857404446537050534609642348362614396990717378593009470491269698893719927, 1031101775942775287016866592108364909981264870277981971770663139913917773964280054850517647630443278419275580826809411711239874520744416138903427799244555, 6524752095282814630322258945430094637255402513614451322991838708184387336044724033932990451659241316766022270457485764637463023839355357500021618566070292, 2613884497206606013004885461414659237183478942574139230341683815390781718949756154589598490701210069252522878818743551035827011661118582086327381137013000, 6399504294264274736463546412013840740786493641707197875156001976248296035018683882373417088510862746265515980757045470425584455202655092042474712427811853, 7648153586167154617533946886977499718050396558647026402819513881039439266700846695482170207864197173955461792054948157539361109466291302344683138018628610]",
" [7807660711822637762557988261857971231614795200807011392219450030081625035602009408344323020532241277458049256413234095662342187032693814510628974220553789, 6404290005910285845288888756695548069946128563034760743200772996164632994710554175824643672683171898070653465170235743970808387164291288410255592252665479, 7145820732880643161292993687975828061608307352265755530784841001628971312586770768906184846878446322646098014767246222344293599082131962615681304617559937, 7628253420868446165455236407732101093891526753322184971669618231430181405070158455474847663291294176810947596822159250033173103223766616159185920485946728, 2090313038890847900095317779072404893497882149338354748318837249302187827614992193357505154265032174283442253885368383749997435310732830544400884064365018, 5219899086734560823989485770691671166722062251862050324141103205321249132758034981966264229432003323127304005180305229765593770315281339268149302548405905]",
" [5780077132944548981315087748862031838264177043627647708417829007727204033260341880372990490057155497846523781967705196773723910298757508898564491062760036, 7764572114806542067976787720634340703411819807450756682140679026395918479537011742465926434525359106327770790857794576278823847946952438676340969128270524, 7559634822977851125830670211687658680548763044099170874516709265108758767846112167078737376994795559905149294471550276089335233816311143437884775879040382, 326254091227477180817965783454170870965767896452885532388493678916823013955810072598402438281924110666128100203506218327819701065408806755407311242830738, 5731596309693665523852926746771775355890783262849623500406449060161971464328383264312865196214018797256234617560753577120786636638666677285451693301826874, 7404061235786259951035122313316357035326138605958066151911510399406179421906000352109994409639582191672322145179346551952977284953661871236345035551643559]",
" [3911261385088713404178680962763362480020705001343376022137877539868703582949786882301468111731738482621273128463078344110346744985662065964717123370890048, 5182347318944101741047020457700515657663431560069338900640991271534150578557263571458602649911502484162274344604878608085914242528813859150266864472864055, 4113917568537120381356457423745534038972536405233025591699403191216749955530513145558907813326761841478883887357886390362468819176094300743319337987695288, 2072785336079346585597399902623343463262963010531407207279118728023210910883994521073623011652275525853218179683112438087816997406431656841576569623210035, 1614395370662982438105904065510318843109739279928729356829880223846164085280733154395904831113364353086361418717316648687269044568724510821076200388146799, 5863778364604464946964497843188609336149950725655659873794081813823455773635006266332380667539003424481763026279565127653919541126052476132072206331424594]",
" [7983584746949211766343449547629642346296363313500362244066708177449631881826092651075422492952001253228855123960980277966900405689704632714432967498484226, 1288307055386703195839027394387216551385527560692699651477173401131902963469696735151733903079959278020677916910977696831055081573561511073846927376256692, 6270323089735925338179425358013227805458041914301377149014905504918291952361156820790619114360082531273092120840155385794344284855024292991803639522103081, 5782364796584782189497636925354222662254467562076277474323726166388076788964953994373815196911195887319899245026812066447482998182803721563378567961829818, 6113190818954553030552994011835099246796829278768221321371588158185370782968533815899125811940443313705532159850973811576561087696556104923873257882479503, 2676810376308276168570457483867670902787901207942587380088818908288267563610106817220355331680484281456097962585320084246177558207079050833163151172240100]]",
],[
"[[6062046640329769096066347266899344676518901424429677360646881995838432089480753859799954198529491903772366471182818165193104084715939869694295808095169244, 2645972949243632679993524792763632939476426123910556548564560294095449556121207934796944789997380888272126869359673329287393517342730405719261920502815690, 4078873454171494440712760753790949913288116217555158559586210992551002228548905061438821563993597452426590399655648106687403380921628528355963355080374265, 4333661183316573400164625776320711148398882477506941874412702476023727762467167141000832441759366697420902090012329863483820494712256118052345124078874762, 1643129857177025277330956077514109151247811803981705026717771397102270544586613572184236479067496036405806050260907314693132506357890072792960199482937702, 3186695377530638044448732645215392962402584227103333957181004757567478066955151221187165402121567058163359566953064325563721057900313620317362224465449560]",
" [4112567272140845118113865323444914152704692913409123036147341332398481620273356124978023098296481278228998395235117080254166863865484884607410534392310433, 5854344777452763751097312294575305394885110378245323007589910653339136099487547731936058883676897252944352967735775656496547751132757455499551970245425695, 1383138462574499208366589677289918289066754568064661123478346405809764044891958550030515860818138813893837769554854346051723380051040706818338266460108085, 3859446362836598601037412670681022610557908363600326437416225834507694256913931635777789583222556658572260420088594981565374903384233104117976716435128615, 5028760960461040237873320988275247800014398438668440684236820078236290946429429847533016197725488392506053663385798495798038029931617686217931659311236577, 6161254689987519993541039359721652203587202489152871519507943406190644699498266677880568298404777283332441875077644287228979625803700792474783257776782898]",
" [2839585528369409537726670324854672351454758739229786962469516025462840896615626487007817505904636181798101356169880922688301010910248372536318374104030837, 3185034375513710767633230407329300883151496752716040907683365122241815980723188210375562712083768961261355679173009969012309355153692479187436434699711413, 6672246490840772483328152820802055369074899989726836656614268373590524941644149544728485295788618518339997370708760033538160320833911042156114289430168259, 5420252409537029953512981491888019273939802832634059227004256144252860658279882608027272305148901727714247347144753337036141392782353284297264841536836513, 6429854942597383381715468912420195144462372782099126346515096540151062791928464705591391035816405642392728189569695563372806696329669731312290571958735810, 4739973823698645126172000947573053104818869466920332224259684318455703001958106888954074170831875999738674280263907238286553827319483847757151441426037337]",
" [7160862920770573382803644270243409458344098437187945311730891505022003883855285433976426170530604877024704460410748767481644754029528136169144880271809942, 2982103442515595288480027691778062690974166320158860941512836364746339464602867166278144116624540536139667972898410328295252686833780910040354031954223861, 6801905207555179956663480676263622404196546939273620494586200842625719854748268350134734347190401180541240367661248898456285443367167073411863950249499784, 1804183631544749515380449970137190291551922148246932745543193886115473113238103625577173800110106738950279159165741239630881015351100075657555603208156572, 601303393353936587233143018348327514440537229204925355322863165159291608922791557180307655583347738695334390822114847716269285547628496038850682989195945, 3115043018476760470716778954693273867118177849778686173519197879968835346655049669088025773374695331007216646868547709804147138659886084250136406402373946]",
" [234732275890345520245269906185880853426295436495492487638898148897993088052508957345280523140452139731256610712171896823418109206081027739725997049682853, 2044344758191381548277686823346016787554087283914005137083650916606115214158766441015566914050850122771946897225094531584945555039517089084999132949468374, 7254754260273505971755055190211929477946291863572727414373604625985840488234836752591368709282254266996209626541708612447084110635848051619312425745792419, 7253664260337944026945613428526836927937258266183047391208573088495421355299785318314244776750560920526330573163746025787662536293742195309918444949322935, 7700794835235627079708396467395803405253945316799593198326551968277842336451710680326440904239414627790908277676500941871815612380684137252049009143144583, 4359667354761477859323604731674300022892629045902113159750662915978964376123159133774964413843996619985211324214953008678665896068362064613729703695684586]",
" [1982734601050456939622697412656537242410995818999376063699048774745566510719836647800626453301545759203265934880610248959877086754855616793997676519501000, 48444326299314727120264342021096295946188263957294065774623047610650201700284470836672752248859628658272340463659827184321911992786964678919015096092833, 7898882528690416721795166887344597285693019520535720413050562199503248438027405375885046647064471192860726120136404562695218116510707927812379288910405142, 5814915760931558687408291397989673234462869962308320236220753890460437354255210609282226355431168198251409670965884826558309978852728087972301947103526495, 4767523913179602297846755936265701569903707551389517453417811324700532889998073304033759550016535805108271456969527959648026982751361633799472092657434286, 5346704789523742907790623142409450623003295048473687834443737913041729246709285231357410413236097410528723341348129830251075816904565861886692668785582732]]",
]]

C = to_mat([
"[[7914132327984568994494883270649976522617339419584229584506320069267100426825780120870985916691616230746312073199739273003383604542199755254171664177084611, 4629776712629310456839625757811438237757065307306314354274828526350520266140179766016721666163654385874219479722183713650673141826852864505630096792189721, 7109204164372242881091925094024019359516091108253460412453366571310406702727031148959274883834909062514400620116562591756691700690727290842392201330872788, 2477559773134163112278937317769341245426053204371422009050567367592349746344450879892782729995511108976496874441648643289285371630272858565243645233997772, 5459877678587757430993568968742145916322083648966017912323213093851741541306674468422028381552505664502178573619525013642403269863611523582838113438963699, 4533850561319753809921018667771099687554603071040623474974671759150963370392613040094306554975171133182503458567984982962204953859396760670470565737289294]",
" [5343449757099849857840769777066997342636505892090645356193395991104145176841294738919368585450934162811108961397832868384600016965604379061454200372301203, 1103129151964579496425084776093263683101432126361676754196377325350074990644308071155967500791176019665296214184943390296688059347549352037365934949955138, 4633211618656319595822361077837532752589824229121651976824075655607724950274744397342724545215854488249828970851532695298375831137441663711799165905012260, 1142378635202578563995121528757512604785824832961174761942529090983399609747221221100359313680419658913148360441213482866465529903398212065475540281107753, 7054157717567957719036149099411851220142044683803466107213295655009718695697881702017302236225450159546528341540899764632776223069940786924063351909113511, 3124377620355697989207793493460638982912257463919934159069355478358946967537260119064254546754263422314844896114812142404263656938250991950525158189122329]",
" [3582954385464445051633609412194910501954310865400807954104461037336443952448097916837602428414282311641201394962736563657742667074291829173632356429121860, 3751634377192187688438461016605077306894846758825439550172971308702864693321006221526803973890746948637687111194699251457722023987352978563084604066206392, 6469836409132372383423389593904400360484608990214822698145675592103054135172959919782038268886048766370788577793152790221499470021076842697287128809824716, 7291702808883045213981690179732663971457889104053942053452260890612893624965320906401039537972764864636739967358681895464825791182085739144982987182635699, 3299753974417550414490414013799107429472287039209413803586635670873024010159864814410287887785321413859255563702124618725499396419267594253011453058695665, 8256748339427246020068747450621026909576116516431246273373345876688375617509366683335678087877197103612629520339292051986808534369102511798238519847195826]",
" [3781612888809757574721491791083186900490945181056011662203424669866448824354699245155713093767699667147704234146189496900196982924950531015334241513401382, 1441227185159609962486765718490329894521945105600143839531490217345659397106380353698212399501875433636729515142714959019326095275246494145877181035418817, 4667669827386245370894887474221521799230065519101908048880250201454346640389680725820864364053381720083360963218910847369365413718623339339707014057956602, 6497087697271785860409372509454324924932647104416678122495914854826753688933949185773561957150489234181663761283750950436059446435033635828461039281191893, 24303749714021422066853220320522782093785924203813745587997307099973056253098798052337823966363261100222814906708352084803660128961942567447633014524323, 4948047469975016041976070123869487345730410005224892018723874308568824112508195260066007656211743464385761979800624180845457585164271927377307621282881482]",
" [2311236231274214430521863711861390409492558254483679558651966539918976267350234754052165248990122381821778554332481410622118479167054397864336117606769703, 7112696162769751792741511097930473282299866429103877319791352829249242978872309127849912410612476444652257696041027013185592182549694296522184072992258344, 670900800318924754524064350761756947449780512175550856877662840971700134896135544689162339422880571543056204472373171946000715663246113979716744105116364, 1257013013813211928917177461658770061468745337885024039490468945704252059669709771398068625685809197173084826889182441777168181244798297421758785757645816, 7670541068600080731246190686115266527520699113715449700906377627569335299090936689666939385880728437086949946998296712390824453668287895792960050257732700, 477801656897543780130206565511046282794203630041030989732746299664487329519994676419042200405279554430951006645073219338411872667031587208958581843630924]",
" [4298688725784585139768411709267989930814192997497489035906391531015200859775089864406895675490276200087674026753346242346207362403084607316379244135673147, 4449113101274552188601004601050530818104217769635849707791480317804438859455460290007508349450878333574389214698881472277067463146427398869912440841758560, 7852661916977582595529059003286805430692091224392567243784624688721596428049862573507968530054257973460884826434351919953590997089599078453855570141717668, 1469040138293943931236145059484628468407768140457058426223810726475203075773661416758988227467103058982368053618258786231735244267495262044199307956993801, 7917782387893055716775937224863842109301303026784902768707824273834234694637771018423203435967997819181839780740281536813589650752392482436045244089943192, 3785594509974037367372361126001917741631347551629193942913879321086819286343616686476030466180567764275617014357842750633129567304810960536013531431858527]]",
])


##### U #####
U = [[1 for i in range(size)] for j in range(size)]

for c in range(1,size):
    mat = to_mat(encs[0])
    U[c][0] = (mat[c][0] * inv(mat[0][0]))%p

for c in range(size):
    mat = to_mat(decs[c])
    for r in range(1,size):
        U[c][r] = (U[c][0] * mat[0][r] * inv(mat[0][0]))%p

##### Uinv #####
Uinv = [[1 for i in range(size)] for j in range(size)]

for c in range(1,size):
    mat = to_mat(decs[0])
    Uinv[c][0] = (mat[c][0] * inv(mat[0][0]))%p

for c in range(size):
    mat = to_mat(encs[c])
    for r in range(1,size):
        Uinv[c][r] = (Uinv[c][0] * mat[0][r] * inv(mat[0][0]))%p


# for i in range(size):
#     for j in range(size):
#         assert (((Uorg[i][j] * inv(Uorg[0][0])%p) == U[i][j]))
#         assert (((Uinvorg[i][j] * inv(Uinvorg[0][0])%p) == Uinv[i][j]))

Umat = FiniteGeneralLinearGroup(size, p)
Uinvmat = FiniteGeneralLinearGroup(size, p)
Cmat = FiniteGeneralLinearGroup(size, p)
for i in range(size):
    for j in range(size):
        Umat.set_at((j,i), U[i][j])
        Uinvmat.set_at((j,i), Uinv[i][j])
        Cmat.set_at((j,i), C[i][j])

mat = to_mat(encs[0])
mmat = Uinvmat*Cmat*Umat*mat[0][0]

arr = []
for i in range(size):
    for j in range(size):
        arr.append(mmat.get_at((j,i)))

pad_size = arr[0]
arr = arr[pad_size:]
res = ""
for v in arr:
    res += chr(v)
print(res)