def gen_superinc(n):
    """
    generates a superincreasing sequence of size n
    """
    r = [0]*n
    r[0] = ZZ.random_element(10, n^9)
    for i in range(1,n):
        r[i] = ZZ.random_element(2*r[i-1]+1, 11*r[i-1])
    return r

def keyGen(n):
    """
    generates a public key M and a private key (A^-1, r, q)
    """
    r = gen_superinc(n)
    q = P.next(ZZ.random_element(5, 100)*r[n-1])
    A = ZZ.random_element(2, q)

    M = [A*r[i] for i in range(n)]
    Ainv = 1/A % q
    return M, Ainv, r, q

def Enc(m, pk):
    """
    encrypts m under pk
    """
    assert(len(m)==len(pk))
    return sum([m[i]*pk[i] for i in range(len(m))])

def Dec(n, c, sk1, sk2, q):
    """
    decrypts c unders (sk1, sk2, q)
    """
    c2 = (sk1*c)%q
    m = [0]*len(sk2)
    for i in range(len(sk2)):
        if c2>=sk2[n-i-1]:
            m[n-i-1] = 1
            c2 = c2 - sk2[n-i-1]
    return m


def attack(n, pk, cipher):
    """
    input: dimension, public key pk, ciphertext cipher
    output: message for this cipher
    TESTS::
        sage: attack(70, [32606659912595599187366700343108679483902926975194051889029271338148970133346485083108671, 343321457203677172026546794962897454645773505810078932757530715016943297087981707058908939, 2213055301330526925973051742448766603299004795598651283089240842117324932971955582425370042, 8180658525544351919875847212512802942711449069382323669682575772275481339524916963068122496, 31185578738795686959180648437244237453858635294351478027703027632156729341020015139562306930, 233650919937563196871807478215788187931132148228733922272138473620066250609909468145601255628, 1494163280670374134511072319079610345825480774966149631751727757983573201548724176011217611523, 5281127868783035512797506571043716300690242605538500145682182155048036438427130408420014088615, 25581491667173334882752813470314698190448201419099304050746588115032845885721525240649495144567, 236295293457050829244256618333044881753019778973797042880003679738154113164977886113900593954932, 795400173638182332756497148594171537227935273936227408042872435723179775285649425232163077290934, 1716224788138012782200174028344006387911323099063835592246053487200826190028007989691906658916203, 11164931765259269572663372761291648224106793424473222626117530802118577169013036018417550726714994, 100376112906369010484098850870442682410540683158165938488377994514055276728637788293458735710386829, 391348206086007948172757030063341277559957442580742497080470777942372134485007487093746670955078980, 2212949776740954165024085096107019062871771424910355806923810137064323843705741319609958529184217888, 11463668028167056929570937687959353950317440383012640547156265428295652705766413429572060891915296240, 109706495730552010203143297801695007447338256657152599757547540871405034476535738828619716805316803544, 299366746707695554432692045267113812590247732069770006315500847326584696779654963421232884065108611838, 706160230184766621635335766743385112104637783250241021182232552105777524132789769178057877894243504842, 6791103505455847099067673301836516913654799986582965230073011939802010327843579867930464319791168901665, 65637247611022009780064579202706123100278706533056308890879138705343630856952384539230943366659608335465, 482724458974798319787058847965820568434173150558240607739633481031789102514576971069769939639772236120198, 1649506254171543351736669605802173326836782748833208107504681644429371536044110230495645947963462457685794, 7835351262187645976758000000022772046144583191677881433018401471680011905969621580013762430787088888915944, 23790872127659054595637620985974147767342751883380452855896282533324198646681116407821099265790255897729039, 187440911687235585582803914583276374911948123625573439489291579907507838398013800308280144466940485449711657, 931218362772216756969309103653982073434580784621394693061562037977229560316559163060713496694674311153664030, 4549481291165911035316356298010559948370983569008841799443074250741690816927367439346710229630203100356206945, 46588525608988988982600573610139970919440573566535176773487623809888570073112553737814274336197196047180873864, 397322935819094893340698348716632297240276203312266996945619058897530851958208801973345376463214354881006207367, 2312154778020126743729360675291725538691106118505087815161041964429092660004459055197960326784235257016571222390, 18271259698095124155423714733174007783479201952164742536116190609360245312889620606806123467622887430266325357712, 78583748398675937824538333088082011427707544053541177523734782380291399600708356446716384473957811270178466713276, 255605900901643342334234599628431810833317867464853047716924998594009938846715182929487801397656617985680149868540, 1036688592041436451129882936724208795845724165494891356461289786969588008305945041960755245408259388737082771977999, 10018933553460820995156428997982868978335399403677800913863173419000912842514281524451204424493875893970744130937405, 35848105004518110924210580183979621614665182104657767650766567376800565596356320695426269112637560709554492104897073, 268599591837641736561210808308996648187512700171618533701645446951773733601208593016997420091541929093460320750786514, 2545815810727013736314482246618890284053410333622051820721730638932254943084263265165617728353902607862527817224160219, 26447694993409116241681115600613194449234738319508258826349127517907605054226083610933964399485627752944735397746377187, 289127220752342030611465971266248287252527901014802305238847775531019442206201112820917845593747970695871524842833453081, 2691324806226906507830882308107651097008343493915478007803791678119860802918471524158499249996143650020604398608868025701, 29545375359233523883846895905418231250122502930627027152274548085733145728040602849339896154340082213453707438474955347862, 150027978468806610687157847976058181108894768494011119375213135931327829444013920808930256505465662138426016696372889293404, 1448750842520972951349224429987586330616238065210973143716421715530980838604018146884897431524657535615392523206415112236904, 14031264820251906798857765245416646478439571245554539874708441226429531431214495017287683657051478317823968505636189715524158, 132118345825396514079940083171242349180185471539601630224310588195023333126934676038318072204672707251046295625366764036515254, 563581747781227789992722477470117079872449060551012215260597671315477741498468433723081084191051970627929228220732192697596414, 4980697609509682048899261702046197884592039037263454459877635080891472853046400610429116777265992666132114724719916250266724915, 53537954576536566762195863069211721247489488514499643106690468915530403931008371290066975652219994942953031685323669355932930859, 322931972154081030441468328291685260459188667536946760838384748571062881019615369148019197653181307622320639571541156888640318477, 3430283819426037478141784350107928848931079986265469203532632431697052542648495557291207319637784882984713027795048281990250999465, 30662680186423827837498970945391549720814352475698575535774367687569155690231896608504375914175971150803908624959274799942336163870, 329231136297322476014321812493523926448175130550881465559627839681943273034184383756223079989447308959151785470802605331056213382327, 1490354461852119778818665541857441212950127979112062787847565960692659996781274842280924801437603118017828824410754725986047209557350, 11635581088481177386163636393994999962249221165369824968203517425290181051198618395508517793621517049770958070296846902903991289467292, 76114934970846192293249999417167820529981673884750898791458593180813487623897917022533885957422831978175971797629800060827955142897153, 800224161838047751030180400775055717220431770023074885796518805035100073511360219467506528365205350780312466280784071677263165003271412, 8304832031484112164841789835082338011470472549440289966299898322042505912144132539934810249742646340183459176573907722810670146392059180, 18717005351490371961808410816504559548498034148939199065116643854801654935236704588134240233221928959856032238177826455307556457034779826, 74843284952203304884295953952099516988852023646806661085880086757468918610319122409932459177381891981260474630495221583879744033164006821, 375592334747031352362495044658533998909293735529999051361862859446126725861589991003617202331442071691477917896911851198639601334004540592, 3694317872910136607986973219082265381472404270473726333753542462265365270039734308405073210734428931291021216455172060970482303967424291649, 26109591280375862637445495131832014619386045157184155490586658566951427167136820584260274101951425771069781780388456787863454517502513753128, 262131097403158316600336568301165141374039287009643528194503985675684736521641813314382717729556230121596629207022679265356664990360239838705, 1636002469333928823293494835016471703737309912566220349602195032770658969143422524105351371612015229290238693904940047423111476554684677583758, 12319498384142201956911676022691432577116352436298280148742566023081038260763545208380099385264797001769319744114172264584953863224625243810135, 111430145764393034458690266687266051336072100049276320163104465169948096792377241359068667994025298713375069163431770334402780998566609298250091, 1065311539980788612766165665682495772499387824562400641287181103278143646930624264886383905646374608240344449688451153883710179505510190587643896], 1636480003235554320867806037580660517984339058177692262653487132650932206994768316933554349231040962668929828528985601590294526019632758729230)
        [0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0]
        sage: attack(90, [322347329722264950577588049939840148311079366739363534633695364086671294743459716906167649498802606884, 1130421496407253558122205227727710643417882793432392760226393089294850111592000085535444085246318181661, 7503809504528014783985485419646561195535443866845557137244622463664950001886981894622224193852074155695, 78024549492245214752826813549605741153492797779157218052902950386238313966871629595351575616938196245420, 721695954826199462538520111004474966791495936541179609998358751851981573672245551675646243662627227349793, 5320088731217385841951610570929166155362471587049123003718207052860806655878118139795067795433432089751992, 24629734049235302066567137309112247147797932662854275582406420899965295016936328684651608412341127928372344, 127392875651184158523456904984566797831073820609753775708504683671097373806118293367994314141918069188245414, 392919586647814398917246187851967838991692764707447625083789884541080595401378741723315559807631745745795442, 1020241505800408519414912928670424279447817929600003634655244679079168035923534824154030248495469292600707878, 7672774501286812381371737240341380411287584613759129492572162140079975545463840585261936730545663128094614390, 29840105877638293079775596799622030876322151672812527476681865746136693851184312865012487109343748931940659437, 159060478000131304247508892107373614038001780882197491320488150819361130848156079366809582100186969416904347327, 1738974228873804018644721368676719522359526498862585762021573204995144587365335660364275127176392463673439404744, 4072404977055310530040597872754931109466104799233535713465922974434104467573198381514907192477300467455970670556, 32628325526232143093757372987657140403880646757487638736812143876531012482937732782268631354759996751669393211055, 237126715573816267333623245915109109225255296372018526064954518706239274556981641883404238463164643916211073110003, 1011326018958130668243872715912649675200440269525598535482141280897563743948730805573234183294043765116395615476698, 7017050963906344773204830841944195052243168093913667808886657052870920934988509491158578184777402650407807534617516, 50956114124529150485945953113397158828026929612977963095316781248578291367643431165596759715022819608648319431293901, 241313674285270896742901276200091664308581191759823487571651529484540831965834801726649368826848057324523944987027209, 1468558781699075126664012648286081087262800208834443941109265808387720203264018737422407561231704509589423489317130896, 15173537577706253787123528214476872516370853322210393304850044332074713259078286341680565459118885079363790703534051100, 94860813725938625457614503948608705052700923725215179675472761777765934764613249965977245133233358451881396428468725221, 836500582755698368642866398079574387032437366375074736173652409592451386668604205129671983284492540593000136915911904964, 6422981676240195786130547062091459861626917047231742337091419060799765512575449105060824316078169430625966651820077128284, 67859215775668644484634933385588849182605733105277613944609618032869972101595350491128976555447009708999824909483733519220, 455010366790558214668659151134261644699193167954663489857809731630537144934481095690358167178161032004408626823648244032738, 1687782948964131910206615234452745557864058710337610445360481710813179928088114803901285822938095792284008485620793282823760, 13309033096800834399000397520793619456776169107328092972887516343946357342861089695349089372843636145460015564150496461158720, 50639813976374678014196794577035508313584279615777233771355624711941679786263883197584134730149297547228400868416995316737666, 264099105586171740265765834200167952668641748948951635444965196249896130647644330340730457168877418655709409059033899208576651, 868145250300433285557711171310358640170131210609379009007858899764337991295562318820426347795129964072130329024825366060972189, 7967207085808036785528882879003389309838829334838269864625982671652516390189874784229774644294160434725434426848841330547049423, 23728194497507656467900203989697705065148952991995085673811754088419682686197481607616071902402309432921834879651274472749205483, 242572422810575632308593389813547513701020777816022974643174711605844128569146846992350583418724833548844735672604157260157922185, 1920933882637022790031594521819104018915597533536603641717162201438424000973156396532911486282871880958871868401932290510319299738, 13098955228897776052150530022199909166761988948913286790517645947501193382420671363613120569549988104419905706204073317183224792907, 32052889200809331548513416510993035183661334120832165523464153966871388648802711358404493976699649616356306736523499292480470101157, 301731783688294186553981379751594357757827279308070988844136406953517175304954244100822935798119560581487300972313552690097611669926, 1210321665068132594605396261053766528149048153024226145681723784638455017917042414750129120536923884478388169057319099836439867676953, 9360235069849124990887093710516202812119275595904647170431914919495323242140309228731500213514232169046707257309376196914305154405098, 41998530132289426145097978398541545866876708396987022535383937607279651524817498455825824958243996857171292618245414510692645994824566, 139733729061680737343421390478362964680514659206856153121171118687042735060324869337704250383063003955887934759790599000341471842372282, 676285129032133727302077789062528328388950138347601406469284449470125255993089144618369554210043693991465045075876175288531194784389353, 6087154042167202545609514330383717851611337610224296125507711197657553304895500403942196594714276970937867107046856790896841539384199245, 38856555466847093829653278165071685163157685544684678134367922993118193663229039294046214036779387017620751551089599926277664478591614080, 124036855421672756230273821509585305365754892822356988465032275543827388247718914720955118557774220201176406427980889288133045769867170334, 634827285978061406258770564780701758951574781717935597354283499955979824106285024032941268532563700838371315584039387647733395302186802115, 6515200750903284084751579444244834929491797260170088514669955126881757611417585904709282284735178292199544342857103374795081153361461726720, 14562553390265202727032092052132705321643501937713851121166427528658732289389314026195300050390566813992873362312802331003225743374534422021, 32898359763910651611870215759723338672021558678142621440919910523151333194861102005476460909237565694565599527425422889460054189584743442321, 193378823060015975836659086561092097096386748444480346099034445294212901497717398222210622854995744339526106917373069450684526812316006696082, 1236000919900627416336352995201764271632933341744305525007167850215008475254510808012563422463004390610267055604388945360403004731438888166729, 10879040925595130243977755356501218657757940280315965629932781402195810032453762349963692917122005456262679407136251625034564461845834275349889, 25719832436717921369759815913172463877782266017493329584042034142039553404985549386240089692255211911531429272359832362331316159610359532767014, 203280327182962164777392669185643507634964245336928281681634771300608887261354240144022818191816716621215259180688805694511201691762851105246065, 737579745461820629830456874500000510775475032426506789166417178255692372601690863616874351990411043303567436357886121911062042352727048894365125, 4136468398620029874647302070975988908018738544642920958174540868897827629760157518248124975105733154350309792865667885598287830495135494404126102, 41596683634373261052899879653131208418427795794712048940976839345354317912056765874591242563426036805678296493767229069325130734438312107689555869, 285826037585955955564804384395303633542994246097345333492379520179402180933619381895477325735589034738165086542634985529699448017704274909686595508, 2419736594048145367437758218876129846656877711973102047343265399813191856064913577867432530873769221713771164507895746377964768537693688637665334652, 6536339569192100560879213029786897871437022092890913067947835107264888649228636288347448346834254066427909006026136267395122384905753747619875234238, 39257938075780355241970765369607119013974216171046068921278238621323453723892184523064147316192210727074332775819122389855462853417404803982172718955, 232015169029520243652246258715388612203957177175537868187721091987602242519011782174208108490052144736643769772511329457678005756682691792172777830721, 1380215348462563217472575071368810681039825946698547930421333662578768380051323283906623279119547814513453535907226420884129210476401593519945510506480, 12285491799078587535286855568183227240114703902989579969091045492349631634376127191782993714971984452659858653145957733857746994733833718051069502918747, 109395080731725597207337170095272123548021795069325840941511437930750842495611830002395402546923555050080935374943469969295802448768031823287636635513515, 268296764309592554081898718745128408013661336405176789120141897076606581269578059555805918284700689991342971416485085622993299247007260505393058630209543, 923061684889580201157602613764549791205370493899759033531664645113375433478700284217758393455141208971433950238155606461929544816788553926488639192779801, 2663576544319375873628298106670702000373354240117253712689786715350379574047126215878964239748609467652535021499890283564221245567917331985222945051619315, 14626914688572237103486619852069595919785429843467990396361960157660377016022700758989251918099999941705150781101500772644881182169158724357321062980468170, 63738326825539830625247441166491829900337461235824068739511763739970052840639306199576173448446975416041468376891920215135980252621806239561201111782219479, 291035083686204949676927530809818156095967510773197298465368768104354443400561113921719192250424776018319341309999330542706589582523922440741687919128398946, 1816761413303873048609593112712801005694700014867835681610465992020588314113960697822371958641797296108945992430594010919090393535453246376425409735972801066, 11963965750905564337360143984030382466632762090554489275600067568169794865092071930547054516015405215080823950560001045524567971040335454585575884745022519476, 97100322092506638393231866802264058483783237244673457896197823205467770604411530325268112639487143060777386266654095606663839934808542917949591637272982599172, 1000506050256158655655633509189073865763432715661044532283840676948949433665822141318577782057549317023835526292357691052231781787507922583800458736686826421963, 8478397460257570992964069497604214962614316720650545275187759028230286968269614209037716031495808473790231254416027388069416912340617742785286660242609294652528, 27585082584813121827839989017023857899788659707491941151908806345102034768101694437293337484116042203070717586089827930070914571576422111407224439281310154897148, 215255063054170975858677728380015381145186418115505445900664007529220524236939823585870571834634031183044795984832091043319987634676866946860641304385678570487561, 1306544108200551999175009949475424421875953373029909285123444243266323779683788138011913692639409864829832105240395165492632773289283693641887684377251561843518072, 6695498012755558297150899658470613076925698528252544710551121611644600101451438026833352909012474946932750103679915108058537285867800671157369652095847494437856896, 27071048365259637696561206604931059930586325347491730411830754543323276987007520020429191962717265705856133782593195493761692243184959303527840454911821159579368688, 88324111945025140502270753112264488860466344799155419157518985961643861821992785192146131597554682068008030793915225365287695021172356223681293374614619814473376855, 590406686195899998622452267215709331372890129293738114899466328554815563285698956121532371380631602129097281233286331382270825714146389482288729704147033676921395376, 1299510010342370128663916981811452295547101978521511881077806919742669940635666273689896982842877444481432715871113709453036166720268732426747455718954854685892519095, 9373946829410237162978013594857306297891732034748223704607691605457937568844320143865340251129491313838087110571693704997468716270908171720390799403158572647653796702, 80070546071320616302246326338808327003378126985673643179392558193773782599417799640765990845821162270239345527885653664634483572565292333305757689721754355603139713971, 488494418492763094910335616096788969457346225891197751107584299147464552230423281761642688815599414372564251604673572794797100832806267231042212725249674282658746413025], 90158549120662522385562413112497660042514325785068834940781747943098200170800563914097006094195412562195190732985304034434442619850539593421109773278184178619181411862)
        [1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0]
        sage: attack(120, [779315876325022118982821700268450826739656440370306332254841730890453844421269938819646517886213993686728116093319353811287693646970, 5799724964728804604031185252187143231803332576036031044053138816481594494676463514783576172546823989947168087849765271906229481383530, 47506865754168886441044261194537011242263641561861626511662754055571901967704722517814914997972295263241507554188761120892787017719870, 246644379929618066711862282698653702045363944782274759856685281743271829682779360665358299458382798823974907135001456101006331002766270, 1646646645033895404361593418004066495074198772733552813292318125396279530335483159776958740132059884995679915129630503820627631753059170, 15772643832454682621011792529945071040858102725907974771487894007087583457138935491865903480973145734209531698891398182489626092228215260, 131754913336938034426780942966730386183091891389743653828422858216947775365843707844783983583785589257451659535469765157069338196616554490, 595425582958085887752633599117638344395146535624781098540712248512770857330876494907196023875845521376120709340470999214520432150103216770, 2469882311385284954960690065172341744996556182269384326258860861593853834149681724855102996564734551199698041290548018060507077088937108810, 25137898545797041617096315986300488969399788261282092317734288349122521277107332914501922629229344461152621180531659615545636731344970366500, 218647277847269616250798948988598679199044688988644807756039086882934904359974360745714263211999512022960525371251153556626273099086933387670, 1152433770147231157698390895764287034033776126292981341543451238126358841356661326543097799655364879917573036628893320231200851651353499717220, 3045489547210208197102096149306905570309434405256719404613689489908869357517211110273725949569171931916936246802130256943251560442671577550080, 21512956651480947150426928915033350304192132300178269411582799830030032285875748168945041037029521899283807123526166213030036966067716011424330, 175832813885373735085986423327977978554998176201316032163408783362787038748798328583524367299922111959820618794831364744184253539617867464787100, 1239986737673046924891852961963799631363199078553087529914611221399147283674538490832142477420885632889070335435814736159995583342058865856393690, 12121077669075623591170747427326404583995363956325218318319899683124746385085482017916860731748788076524268221656270884618651697807520856629569910, 119059939176589213229647918379812180100715929639280336601831012708783925031154482770883687112038845823863857418976246571761010731480599612432335860, 1077330898087773100801733276907215325633633900032142423625823301918079290618791133911196282762222557373841134730101105436560876986665982361911208390, 4407950573957374349420365415590329980080737484270093358147497169587858746897899869116476397713204196487377238972565979181778504992141042259099296740, 17741257330535190287008847273469317896838269937750648412063517281504946980101771857195757342439543738675829135031263800086706802566262638475347457020, 172660446918815028076479498898894516902730303326797402931927571178161141394874176688850315664587757063243753176778445436278856789756597806795655003740, 1669866320823881215500568943461644084143305726217824247739201210634449949773124720793809775542082228056364386678514374044897818928823673271943893956340, 12574006420385795525281374508122912533948544603935339457694455462590460161960445403620807699733737143571391652544425188563902169005498730819502859873910, 54512634028996985312922765625288750971219399834315335701243978968130755886890833771613963187926122881124363083232766592369593958341912206503232921563620, 290369933746909553337711167585612394914007532290075262677778365692556627631746705822533820003845615367742495377457459394838340845044676815864448803414070, 3007728608294108468188253444970187154167815258698168481398858496088657458717097508012783045409545930515379206633355153788489511037478332205872916727766300, 27570068883227883533104865737168460032973102351090457609698482835843876769054253260099870940499765542339290083018909280438696909078778821597008062571866560, 206076816714573013939655138534642552689320552270645908139518265677051370005170674422297871860125149537275098919392119048232007035865006526541476875005092780, 612032096648488025453693747725781652135455461936465016697358778426756108788763767193947716044828696542320037913013525511007467541221854643479135588677542170, 3782703064320338095345822212187633678997515947328363621537228801104019529476770317737124178689082489997091254149233304200855560362700229233913609607779497110, 10651271575402800550026003459566686728361005845811768394341253005378807408595685395762574678281834304955721499198576839196209140730245365870925090730716265350, 53652024996457305694748290285962499953062776641023157020758249176982991952845120778055283018946149007264404294586836219555101225064514612749004203864020271520, 572103945395636292215379316844892285291118052631230257802165943720502596364678928685830259798761031065425960336029534135027524059721065870322203397176064650260, 2689959402087714217651678423937099008667434442610872020126343133779058422657618107262515466694663645525961522115785700871168742385832749062099510202255899847760, 11864670004079787274128124617290697715193008258790812121579418207732507638443302119015207854764644171137434718598807922394972232023318212428002839049615738978950, 39192865642594148201013416516263051780797554899067866430353607287766443133676085809801143635307023588017111005782088735531470425738726576454767694659580085899500, 267776519248733552230438593210086507603862307277232918881844500516432666553265102340127164114531466145464589302241034478408299016736726891378902204631002491782470, 2199169647434324100378676775899462318740329012175986629582369868882297684875369769753575893995877011499244194039936122920521617481772490146136448837688748656466490, 7341173342067814235664455603488404568262694911620887032956588167486495759612472770524411910053715914328072781929220471378866557179424271961840605044239205661708420, 21545620633801109973328198816731081077629162348561656385760472241538244856533310464388938411531367246083079800572611852857804642774285091154923356766736813107021260, 109194715947100070726229196450190757985497252857393857124258009153052791889392112995137333521904157458670128605297671727726513305972627352669515360048104503017850120, 929962741388900408994203569090720143998103231806235195499573000337701831558516091296306348093386277299918408100458476986619359680530816971497330868932370250265810270, 8881957156471569516834629087871561359228836038283525818912905242758665764594660704093880359652655411275130736331686900128748365526354722705691651154037226768618652650, 66769112938702209837963949829446818443781433065308285187891891465931536505556614018624904123526369615717399354166810310071782099572238029098055929885771857552409921410, 453111752236214460732869461300817813930283771363755118251342067546266680790879562741866507613196781276095975679706852024585918514719410824278836259860074951715353739820, 3467889558946760196736839155687451226401856608276227212316432683811118684833046509386238116354401258050283963853587698460512459420913626310532952386821809680469875990140, 33118309781452984144348353345157959888885284040450721339651352363028298348146642061903284163324116074494973470903442269493126727299613654853765179028015006613388368982270, 363330848917232808541103652727229558229424424074685731179153868514352598921075977615086030763240792508205022203003373589793123284040576649472166858317389300415466019543930, 2516044114567842659132143784732013499639997777407163998316962524788219303238350909705228548733067652020978006632182790681875910470976856721506349407211903457198844679625160, 25507372786376471859652919395756812536429617124470288857567599875368857124402690395628131017548200945212202786465613501620122854234038596157070998300525651208618462263753010, 203073895575103800689311173972881827075111729371013830469953930415357020554919403108022654452964730281909314587456350229742055730186289475168663229825581628490671193699029000, 1489113419869826109844040056828526749207800601513654274163149579569273574965506068425010329713374670753749878247911703132558067653576306897046599992377947721720867547952486640, 4905424861660302946562929542487215419600603502746481429703662519414085299887827462103951921518210963676384379205032029014072399301995716207910082223757773327200892161243699550, 37718104600544461179947602322566989641477121055764525557175913939587719241723321177934226829581583656641034210807111361960991277809862693730082009086651995995044933018845734170, 248684905214879824338474460767799359943435504517005375601602926108780349511504205028495835040631837012668541432845643908247792710696598338356565989303544166159824288840697697100, 1994808315022862691733398765016507344310485512560856225036635836210967766497267985281076861003635254580680801007787491018480120250878227505180767159537468882061948901996593557600, 10728547211682529092785332387593911469890529982603007164297427447125232575781911679991560772593588882570428019815212281673384716540221495097718280963164102662737127958339186250290, 59827585181491517451395086104852706235341760757829632637620825408877258692794059225823453119410468195292188304578623509428677155863183307708087076028909486001810786359149241877020, 356609374677422404720632471558859500329682870447368204902399106258963562520424601999951149790836980939923537807544420269925316910101897379347045766074058206735860820495649610829430, 1035871414719376914436465785971888341369587669281291202370881312903363837419700747932911744799081620656973328897859529551018437694252817258448189815614066453321433163601711150841830, 6494705932121453266414440557352744257793696369723887836003819398407691406221517822023119628339593554226947512941886911453341701906458660922524113884376678205053802913901410000236370, 23768978049888219139270994227464545480250186302012315476914871252650538719300853689811162107031788024290981343008304496017849319716999720493174336048952499625079568508418439513103980, 107249224715503122971199579282975531667871218767167690931570752391159066321476786092124599562940251284848582264284227263481864322815955843388870292182054640865528711925277632476640960, 1103988710178313082318509869414949160831949730635472705729228939477234117374762369922693366012886369761689114903992734062544586981446662005301989797391849848219129970406636367562282790, 8769999903952841535936201648145921093995729142318318970210774403962602243839286914093033407899665224588014150445473982198189202436697604625292927320455906129674428657349329513849240050, 84788205522021568797505723678722299243075227602861305065910683741505861687712137462880826443832123106244598725433109134514698954639378528073907580530006171250464202684834594214284733220, 240312990855153135091305862605440806403917015974747404415352924040474618384472163620329058564616545822044449149756004397058637584278334110899159837561274709912582185551761043205088662940, 1202700660747993806270275498184952390558297859584217949591740771954995056608460427288135295499825843914574876744529930089576884977371408876090796502057830047517527446227759199650529256310, 9000497894419683822473821323191338346602419323198860543716408632878982187312377798557969953864893802375422362558430000491087938402744425848640164200066658015592901098700663326036085909240, 42863853874827917055650896272598059082736926629486051831913565112201958671467280069580878695640703200212470435752053300722386174627706334748530227825632067640345970428675904724124846800740, 233034351071564202265222934011731917488988652760832057228554745922141156265354829499966335224773545250068192307746109152384635184291169096798830543012341354768339948091454312558958902116100, 2216597727869371565126521901184107432397100095326014861053961590276674744904519945047175556404592107275332125370063262442837852340999288495118143900460278768110373357136498038419294456502440, 19139889558896264195309129461869898842870135731052421488486423485560606728740143653253402758078212098492515381721127917954789326259319063241311444694633574839074288406005213542999234443350370, 90270121547841337610141445451599897894706555154500387017992237276472415456009698863301025503431505835289486078966846047558759159874848833207377418579039173172970514408754153574586337608058900, 899794116479192808760489710692086935796059045220275649195718488624278241558867739200647494261752857116203211471545691845816177388235201987441850445539603232296940617667679327437837498184825570, 4194049187432215022882385129187042075617909162169358096433202297142522328691131661612590271014338692257034517042061352858422134450058485182567113590393253053313574502806025430941583369110200770, 15417004962001130759559951246805941231127941203264535402802351309857615639558933831062067544101764852333451554497866200794497395842052581253184075034774947492534966146925119096634784133166353910, 53221534505331161808895300113352294022872676624800102934553961885715698371373950768468883309394098894908007814252079241891129513294114013166678802329338408713904720695245432629059940051358771000, 172432033433706068893910238784156950948125652512572547305053647512352961800008530179588149066356931355938246314839326410764444567783525824332965810569459556409832643932169887090112026766177171160, 1445898417059385988624124237268966365391470445113567126309737575150369229373538650013891080569429906237591053607136285413219339385914017341933944334294455164912806232287299246609529001240053500260, 12732853797292718360639283589828034223995495623434199178652183868262880539343624547041079058665178714565236594182634241743436387945039003996179890729385311800627516698821370217150922307756093618490, 89485676253267971593652731635542290058939337283485030385256871248342182113542446894075624522841791981629248922269886920077894332201504430965569285278977499165101292185240926323270974547409844166230, 353121959579973144490040241600767340373042220992563981638769214937297956916056190918423134124556089386254498273248556675459806143084512906952305251463135210665942417955281682240803721429028623412920, 3503463468271763390312005455164355628965375042413957723295450004959475291164265429566908666471107791914722085432099321102408744979253641987376259792313624651193981476675264381115315258657282806701850, 13978805241001463305326211736191523718695752134625392536347159920528479314381433776077667007095947410268026786163570470947299706812426753345301860781079645667508394362798208163475528835319891473827260, 87916137625790105036522947867581747279106923193411340530738505753724291495125702808698848639253286519368384142999769169528244572870377744336122823697499175026006056172606754019310422091354351296552070, 837866934401404167830964009389326149458236754120657726851059585309437271860026854006838084610188468023212662430048586707728519033507025218299755281726575948488118183293036099954981215269618577708545570, 3571710158253633259263378226693229596446726767869796534676812161991984108092478468505999127866543384343225210285991585871065610116908959434542277353321363309576679792187678290708450722920356562099204600, 19240683382306371967554322461353126625047478514866409002437035881897793471744007076859343746232172712763373819919411143773735356615496917869367609527835871303697486678355221876672950961856462541738845830, 160501103137407684514587167956821195946496816442401090825438065872128742013216630994444842488516294166703767349994110866779531185421644246775522484311506281372908002566452931533070426553153270831952115200, 840143505222310288590089845561499471531056619823264032431987733139667490730367837094852593667783782149679582963870338381145011286846630824840217357946649951237454130934191960460205642563882166163749546350, 1767352414678314315418834543790776735639815887121021893938378790252688074836191456806631521878766780751202810514532585989270538466569258185044297329832725029361363845143073457148214761133085918343105570440, 7030042045657645267983946302631476443970717673390889043926261712871161980527089616368968112530920708680524843099372690118901073973096267978406625825482838854413793718873687703291702199240106065760015292900, 45780726815056742722378189415226974248143746457420789281065441010891763602733250889574683477953006501729807158795414871605439789527489975454419404452306085501039949754664006212841555486465008253431318580700, 376794041269943395726075235151182558604747175782067354731335030380211601248218996558372365118898536131069521013255525310964402999108923800265778515954265030628372078055794857137349614205997997693265081620410, 3997204526251175663751873879608443151175756001058551691581128366257851883427871732120215021142309073288180629994204955260432077031108264800793447360035263430516260413887230230443721965175811193655738026231320, 10033626047209206345329502053837709060082583091658861450266032658625455477232528449973670371313012108386860592777881466829292699625243989769404726098591668053919387248303470236378399195543837118389890274374840, 85021649581381159200310063372260307553606639447687746757171378693592009351808916676892340338248295830666893016647679275013064890924070277597681177313083149895197674515074851004955296166923043306840704430581380, 210691972415982747581878695260870979259391397206037555963270672937244353249228069933968455097673425193285594945121754938370169238807162804898855903622078213176326164960266457015637645526119810555569034082977010, 759780516258415954864073076943206535998772635614429655819528339144223020780948079331285651620530454407133585006694717402521611054517902027184335591617972688024620324955419206197631015470451516972085718908182320, 5872897201713849811392209778019013240440591465825616536406270416025350112497703232729850621932795142148292800347805661793685101547463914019850376074945565567079358018866265858370506943904021054734925541140397500, 47466701032293625993508181112345646213957409836867666693674159054953148215423749753422695587010585945462645234556698863168003170628629892618491083512395708017620621829547945407998932153497668814752046662718217650, 397448845381800773403672509696150951497241547168857998235142728842067489769035999948426574236433558374649519266755441858530054465041087679287354347243791048638305036976918134385758149986874263268432487970962350210, 3805243593836832028778201131373460388688443235483919266331056794504415323546665237324407194216150785561185863459595291550600664496539615602503493014832701411324609254978989533249421665477244986526803731650420440310, 38643938460125953860546453760569205191205107261454545334825533375152050038582961463111157161365262703829295632892310063172924485756955031461449432897489018443527646636155671862811285972303629516144876307315603296440, 418730263801859644133046995226641038265538987877120692882670895977982939428532857022830708223214083051413691545530875532393845251699825828779542353231291957092869500393734869684638827469278789910156589542890810884160, 3402709766200045409562412538371945732904470822572771116591320989574463697219976567856474772864634081118132687340732070444118421377882766160614461537541689375002060772341231220425254650105215165855161364738686124497000, 30918273644142352927334107038652708695166250834927810156401155780690298793971134889067588866864144124417202937287607891358407426884530638731195610797519256542066774364086928005019532449003754960262129859530964145248710, 186911959061120910809162677058389381553578328689614604679938674012994376376074718315738673645824250500323482270628165240255211022136713902281932444394173936816312959260521483940832660225904716534823968450940465665572220, 930496722473420448079904118258312445662867310458256538613557212612134635289773680237004445627224066670003232590357728263830185265085802151245534961604775198946215978347824688381666808293278047289937742834050116365142180, 7242305418963140859452512585284025915134991078237377104557279073923484214164335919763068580908855123328841216228851948888216920663541723878360177909599480140665497532364133659741868390958228862911414540563500468585412110, 29955878384831694900070008158833119273039546280058609769921055533447379935348685876011153634941384764981903213541262868526606004179406456930707039235324218532671471923454526714780362939680325309770407121058871926750142650, 157081379857237694153005960416795037825227647311795460546908225594831285190988999220677305797407574958495118910051040929425985469199622380143371527891541702716991705585285687069822344225108382560104574354400139994964448430, 1216054343885852034357841133858436330683408422970245891353394984598333521999003441086695470602947288761371870112481211297186107334936250710025722498016601164474711522230332126463165346356727594720159975908215740094570495070, 2697418749117283749082430725054103608600620160947033744517154652104087112230803045903439550112686194141551609998759425878277515929098337799113489965653261782964562030291251325196915252662059334309182251448646042880464192640, 26682502880570063979072995444308705262162726370869534745956298027691932483246990593579585205830130344356357643427818274494230683802557015552991655479837455688609162558942726351548669365383410501384568539853230549772951210530, 133045717840191029864273594159413906262043024533900126057104521821548463209974071227827047238071952356838266257358768777837861623957166127734595321298978222527469263197172307819056150297434628115950002481974455335135910785930, 1371160140246883595406019979789580940614158980848018201449320508934693819950192417051650438429789565373535235741994736366498719476992178085136322889587207712515273386858060998276053009906469400779226477925916686589541040597160, 2751317188334554662979276738625733493980684881484247704966477487435208745309992989998057765569375071878703762434595809241643911905304003355321233548534846176696380975942005680380182987442465087659729702780120493795849734124080], 2780862364150443462854210372079131862979854479936758708225051015636999472029668248835530962996419102086002142697876394179318783223735207255143788324991231641389817944978847609076058046321378428988369823505105459185557201041920)
        [0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1]
    """
    #YOUR CODE HERE