hints = ['402114318792974718824952149091412746569000958652850114604712688687695759474284595563652528842490249173770010467507366644343547854496669207508329727244403979643434353241186323342646245440546614673308947681679828199504074027146275584397757046843797996195252162499838097695355680207325292259909256424247522654055073624844909470648902447549647933012926304941717156620466689028992989665571686669924927016585067462513399505763016699662294835742785754410915294425828255426996773123994329901291218918020442815798213485381469409762633175160645795868046213961437226330856934445779144893216621409031291618419432757068594946386137233798760133051956536382615854066422979598772919991195713740650576935798513429402007419608716803577158733439245053932044442818719696242967045651579228184189687812726045403072782571200164992837039635254979845193936925844362053654155241099468370437230543015554254602005979738357511155336891427574441254013676255827738754880488174796524477577107160059675945110256576109995435044945715796779657241763688570958093828681597931210341298218257983806835157877118100888266181056450542995551703534548749929946720695140570881863810980069156083039620658100814113893455198563706764886355342647969120772838663484314820008809414409211544832726472538055098950258794158590589798820627716340092010288787669168205977137884058725247421358593741742261761520203484911430664226392432961982063281973595901870472796252280352323636181731091091621644738794276711053940323556404289970837546633137366386790144400071994065872250475926441589765862073461398262743227909380392931524925025794137506003817722619072394183437127224638854117046240242391724932952131411533595830736492283986042673976081282928069891548932484411425627533843362479347449182624417268906023990757329412882271730437747423046416403116594494463223283319792406799996567600107400864900511252422657556209557394779409915264521808282921734159247415651004101496888978762170338887206446475882159974183815729859849272449679702425931196', '8479576353124247371863074826612777296541946988908156929145325088256476562750931183532071928991297264455894455220295651957601170061514103185601075342482507444014684656872059778763974240826021312220703592525761942213586755434461688999081294579115720853101887615340890815775147813738578921771550710248662674574707747613430544633843861084475234546161268540765277125273909765134604202063479549858757343081997322246343460336505409314602791216784763270044376773354318997998643587403910692582871524771050916927599381055328541505793979645262781182119977901902976149008368375085697532893799242714258157109004450146808561503764002293877446033145690694974311699176249739225786257888467227720623371224425700273623384022171078725528076563492657786944647149917899487399273054057802732879089649991551403752699729189559175177372352574620352088349454320359118470334077245185221276566121772204692475818645700620183108261565017312221887489531238901505353565264938650055855481480627361793908243894021405977310018137827239133302527058861660952266777318496294547167085676789938061130212036873858734307304656192610510758641319905495815402044965303197232241872424042632906797220087281280784808876927412681547382749829010697291002522359753168412290858044280097343119836869602880274732914257906253813761449720623533339572327233376102607561456795748958338739739492409844712190881567958360609247386181106729786584018219789726871696856341287632871465047629060920297598527996919627484157511514582097109508740300488617324180606112823307084309043951663534715388989688914082015546363050759931082347054788174232891350291028876719836131023958042975256153950867125204319647356713640239377854120505664926611813572188081037694851826393268267326745831834670402579419684880127970570556373780244297029240480107876840757183961291013249831763906614627571984540490727436790234217445058290414908601713745885868994024920244975749500052025894658857445454735788771160722329753105799272766908132787551321623783278717539825075631265515094', '2610468430465928035538692738271247824574709545185422329381246829279569156880758950782030180009174561499013288985046915359350368068468875966163543810110186347882729380007398829999780522146343377782653100798313975036232532763432125494994596802078367533676162629376028223325236658525493504004737792949882522063513510236967495318981712783923189070920871417253946760266323134422197870768640065373678068292677633176015266846728764426459552988414019805355303328386510017780822211001721525467190094925705471043052660715157484635060415950172572530594079633938933584688277448878848694848106739533035962529147993244793310890175229013494040788903536589850617773022165707683032433198367990778935715153421659167669669584232739067653249643629520854759409477087344666862175655198813963067210417419206403465013148096585817333332324309423437284572828758590502952878675983450989131175392247481742185255747452485820907804021961684196985819765510341218958836865749261929426013333019044733747257434883375048206627878891335879198475290741994486358906211239895891783512903439510703086686973406425506249232028769876672080763479633227073788364388890877680314449433071958979027239389228250554815536243004415273377594588611450876053206806321828900094428592205491749677541232512638606302073194140519503878895437043799674187856607487764188631624977741947728001269890852703095783728072387662714044554507882638123369000086589745755590803848613855350204005488462254683695184097813739770780468333812094702569956061314938524605104806640856602895144746688732721745188344706794888931895692715078565741928778416836469715323552033683218341131768154348514494363084061483665542776058982548424498111211207578094804825761864314115606207731902050962914077880359254464351598647415805041620096517240696184162065237416145629535861406739461266938743219468926651056111075666353817292043518608617580590764805976080932703179627499776491277992134233179195700360083241098828725852743581705926954927972891126251992601595354102561324009119319337', '362924257890957314566805923189267555635333447745851896988264213388027236847946715490580257224219070495528966380457258758687549001007524623117267779368059784235553025077180846463394668736980134176531102167857215962791206059774858638014159328542304105056010975464025278617714271945074918360476986765515095412737483006767179639006488867638313162765964962398670678699374154326294775665709732084407959681318818676257443716461482110277199862127984791629499781202350807098903100988116185896676822249137468097785036108150808079778506092961607443372790971337957243763247274612831074682576903877901721800039876461315327639941014378652470275601890973304068495076799022186628444828432418127835862337632422112636950568895910349158637874005549147396664143342397055038983326856198506430682985913773850699860146472857671898506046126554974866860557860583311119270205277229213187130972821122837216776921110165111766868185544414425338450410171150456311251900778986547790916512725011962182772666937147805767923246785067136280822630402353215267346191351284421599606858713589743405255747894593003328746935545978261511937011973760455460091468801816998468064253018640969964597117673833828349360140769356314203630523232788424325088289981824336667398326830084996410075331436428657992369224967195978263719390627828209951860243953932458928715130421142268429080923509011025497503255702613412383160689549810620592255581292985539457715608244555652219733022342597922445550071499072937192465145544370279025895011946911768176582743028503738535263087784932371624056031850887720692124565686127710978927650789859220028454628668095621108505534860501882556592520706546014191279803393366668193507975315737916830475045276676604255055704758850599760103652890840689128144800005326285693731670163948286306541927081951333148278665125296707259405270142573418776050920402986596895736618838869845841714589789615146385827960676243790418552615190089911056718010030782751702200469595458834917138108035884498507883757546462629470733622051325815', '6279165533140347982418216666785306829190900562208967411352507647810688163894253186662546382423089699123258845692510660312293181548373615229235075356835993457590099544768892963987053562929686352553615038678413779789210904434161721842694045405864338575314812834842118876155833672173343779312709532132108690148889828341769981139415759457323226575323928450380892823888538191215479043575575719363420456933587531790874797810352322203397263551976873088311047996990978240912882302475504873320595668360348054061464788255251243145229081551321428029200202388627630549753588533640121743005310407987526101781201924261780367496771774815316578325791520679681200280404967626016112988067383507309771096850695743111774259608224671401967198753332180460452468558697264221116166826688081535252121628210147507469500564687085299039807340588377329048659461204438906391730938658063662878734807313480076783421981104299788901782814630618377569626315409726327809891872321857795565747398995279318948475716292267793564240187765785857136691374422269468905730186039013756730752793480877864283058222498449253189380139838234913024342311840780882460528929400433528698606386823349492759459715639851491428901334658335359031940687072376965560207324364953353861944344148137981820657946716725367691628832339771826373879149244348150992612506031389697982729100629792632596845060880033441711641139884688974520328763310877357641472467098168124960179475323817512299171332771667916420503711352298780493260305957854876763464918995016708967039936007922514919564267642121485047864614657192680721272244719326143901691926163108736278496957332259394241544942871877689853832819563286763357050780736682604380320075232399257211350255819384609457512487338944354584142810770165989675303527407347606640675194797046132647232419774774310805700493048763958846847038115850144102139824551699850492623915082908452861476140055651046517681702236660748508930837752852939598044668574639140490516414419826252590638751038334118916422721879033336518164895465284886', '97216086029723116795341384302665222109080591063389030956640089779935516234831122077355389571902600379901694652501273792379134097274538850439812587903532451134012919638614019975371127639260666419951015792761589941619213653277511705973495659243663819979301230675011343474582763425898406538669444832282032543296989729326305657847146889742831099657195900415941984429359089550821341611516347652186637243243637125782590678474480507410048228211232008139646764988432590096608473721989905605223821687821612411552304884861854916558314676593273830760075510994708585112304508992515155595167728940821595753114121940199813863745471148755023193853833569117113944748376290111324816583651557437807773535289300036414453190957833676267338649661932639663287427112280285988997420106930719683230129832787992727213778257025373815560264777445509330773686424366287896680887048286132863194736557188962427627251334519950346344445090795679897959967242196331139201747812264886159862127390785623890450583862192241738369083472255535816872627914033515017391762496407020262010453438723962494873914028380710118169247032140458030690177094036894692517385699718798483507939084484389076967755141188145639923743581796523715732796177617596949427251543648578072971526489558255498973149083634565017921758158928693583877313096045096674028814946294817393227562618381007765539670924956514406627770407082372276846552100891404631499938959406309335076735406178715779725183724568094333152533149806296148974508750360707930853790189810122068631548121880819047295700313300853463108249996541682368836120877695706819308651713827977996233220612274830281792811290015461262571473818059196977581604956707330252981098127064346771919024661653894945685548840281719955453291453655461723361396674531102798025117920590517223506921236346900236252241368683479004484043474024036043728800898859422000149820468791488229811147804205725376309250011740666464858827124401398486588450589256833669679396102107861956710676038441607915101528485881086718492435357527259679', '610786196354918736081300550012826985050511008899536899288159520525025783976807318497631932827572151806676179924267545944804241077487485874361195310263441090595319719736220220912973854471276814950279226085114737128828144724953236232364204282841156199552302225303089552801797598407715521136518820640148133489334381536015366821083295638621758958296869010322496043695715405571329088641634959038327535297637615077611806926477277379473679821318076714272330607553523738714995678614682255646354876253713500120693168844388029852491630145408454027514464576240258727650607176155163131977253612888598267092238575245732479783131046580054127753277137443672089604578201683335660975401109751925587586366324198140433649141232614757628932455610064800578769153483012651288550712149488028447174705952808547255954703380252717889290458932974526329209486094482490271447033236399082081326229129466722107935904130705065752744467239477126421521514600881714570849709138783954780351973176492090667123846518365805335679824466071263714430015098017736476088613054567915139404672462978497261665682887776563545537473466833442269474696534460703276707826377192103554305393508183244239071258152041082886910263861206449594448390505588387352936564205648422133639410067093663285121853353264569998980767634517733624720739431512310752349566688976414181246469352396842020429811824556593879212871565269028587832664109632770906487417674218868372721655399141960601827285382692568016498897625261515686308983342586991614889460864897148761511477383663838813390805653535422643909432217204722675133212508191905675693401548343441660060031443322122750107919126552266822011036728662390250823843035645051609522074397700350302840160090495963925300920596120812067525321256151091918504349835809066934722851110004784679565291918884312458360482958446607755628609631184929148081431550820776916193685178862794871041351989012974390799959618648880672887382136503888924892686690426901904776773110262468818717986465749159794498680992389968516805242202104604917', '212188320666628481805845317400617665554362226996588389652942160135668652712186373986603502618086148755348437465689248095474130303631469596428559993571936566081072170055072629807928298206574947013507716549981793420437666229251745873287014821552816836232834365222788638386597257383624387568595652067790459483536094863427431135282095037091557692665823152139662427514908728117861123510078602416547569717364928720244160075472375289699522281041604309884088842367319899548433215889501640794339211563755413273152343255972142976779600194452716972875752175891920761330381270142598668312183461395493687310100842372914105118080188164917704429641936790858008571884144615512822408057180240668991262414133491587002381868048880778488355884011148932456833248831142494506855035624599337529997970568118538046796799647938939353923084466622155921981643825084077238725902717637693123550480644598306521003172226080077817258441044010396138775555470803751607816803597921169854389734791522780066171184975782268295900543944344096739589640424460859089837232869124013180546868691366553925387897482255301224124885471801588092014519846972786203158916856874805578307228005166727526041724423068140825895070582103453036984746221490135802702741900653768230287632694353288784576366798644717128932857853373503328170536223355486200223035929820243674583096032997984248252622826844520014223906703126134396813059156914054594847815944372349688653967642422313179164343890226022439139267914685359100168550054557654421081562421513868436112333915665014773673890809159778905830303792462104600497199335349219444306642339429992981301479358107114688252335039661004419021360168957228397377490580884308334125824800657884919375249918131387997185185483056042137930685758895827649621503699872679047229093860422626239404498815360640672421612079422834406552458636083988535911241384966573304040002044167987380836393553082174590159413706099230233309872359390832705694545734931401245176841332388987127182551579441677506612621891628731706091995320990813199']
iv = b'\x84\x1d\xb5\x89P\xea\xfe\x80b\xaf\xfc\x9e\xd7\xefY\xb2'
ct = b'[\xaa\xdff\xee!\xe2\x9c\x08\xb4\x82?IU\x14\xe4h%\x96usz\x87\xa5YBr\xaaa\xfex<\xbc}\x02D*\xd9\xa90L\x13i-\xc1\x91F\xff'