TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 2713,3 "name": "find_the_divisibility_array_of_a_string",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/find-the-divisibility-array-of-a-string/",6 "date": "1676764800000",7 "task_description": "You are given a **0-indexed** string `word` of length `n` consisting of digits, and a positive integer `m`. The **divisibility array** `div` of `word` is an integer array of length `n` such that: `div[i] = 1` if the **numeric value** of `word[0,...,i]` is divisible by `m`, or `div[i] = 0` otherwise. Return_ the divisibility array of__ _`word`. **Example 1:** ``` **Input:** word = \"998244353\", m = 3 **Output:** [1,1,0,0,0,1,1,0,0] **Explanation:** There are only 4 prefixes that are divisible by 3: \"9\", \"99\", \"998244\", and \"9982443\". ``` **Example 2:** ``` **Input:** word = \"1010\", m = 10 **Output:** [0,1,0,1] **Explanation:** There are only 2 prefixes that are divisible by 10: \"10\", and \"1010\". ``` **Constraints:** `1 <= n <= 105` `word.length == n` `word` consists of digits from `0` to `9` `1 <= m <= 109`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "word = \"998244353\", m = 3",12 "output": "[1,1,0,0,0,1,1,0,0] "13 },14 {15 "label": "Example 2",16 "input": "word = \"1010\", m = 10",17 "output": "[0,1,0,1] "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 "\"85404777601719662219900477245322424860808861058874840830777525364972674193637009457142618594703392232506217209454890144098130112949272892999793799956940349139893722116604422300403955372773166787890886421771078140254116243800145903171248846842571009728588772998629479356763603042048801711902339856980297176689515208711604268258164348254409299711215747755622351068955102763675099921509561698086132319246945719788720566580242066565318340752028444530495967139436476170312005436650117974336435699793852058134045215465055918228315170768036676290224665059612276079495040712053991456393520697933832963717951337797650985775907475560002785504106139770472354582006205953924152859860137720315796874243111230884833820611305000725333314210114398615278515998907749737546185509449318573127645135772643546776951425256022779134389832018033382909171204081176057258728022828973831234271728027332466610076407710315900168747041338041173075761255162648542010060911302063861874493421961097896291406140834248413357384859547791827446221836410269400932271255195758257814427382842781237847330758326072391600370141306006847766553566836218744994684433931431697294322366273404414901967102829785441994020542838875953683762195795180173020868752879790190128458633957594909823013603948223156654470323639766181447073742872590622478461168151260551739777355992523940988252677485701791522635374047623408821885370257692111623954659323216620858488994299960592188101156741078595938700393609227342998442378201091586751795635838936209261411832276949162427885647204194385058827971375193638062239391303948713335903264067686825632445292414561115536853392226900839119450265971551898488175728388532709231854601103844959514911687065003042428810251144150545095851450382310941848618852953428994039664335880452911647290911561717773973076974999954679520901308427376218227218626977517193531397428699465138947231347519941808616093772225579607276967326675088021240323711149485092868501747622801179712872262337415871088989768665981747800958073374997377753177966594411942133401391282074064187782406599100724386804380423528841734729147783838306779192928020787824637019463127373733988637416298683338536892419235069323628605750514681917466058106328298012321019902593603109627314299107544332307105297433121217131590144052164736374320226192310530541920508488674957480373563801697607155247736558780034446030861573987523423121506895098376231364248487128508113566199694241362167675888309182741242762147888012614706607978279819889560560423807000902016831247913268152300203734638245966263047580117888824468169634330635769237410117622194823279891598207534000397966055355846249275200776302309106158099210313829679068408697130759589318023376514889312257293231200452602428102935547975206277481865796726224378240708284078663792097639948817926799685630002879141338005560719319208267055027049864167312604374017991648925015503764022685113290439508852152441685721405821480875084797804852679809719749394132204006170243163873913427133361281938120966043728677996323566668661397206372789762449168735905172338684707830308310310320213792551034249710257510024811125589315550135846784566467436446432696190489541249739833389190203695177347936625518650443552107466843481300271766425928828816589373408823218194670057676956576453745066427455867845472379785165075846094903644452662339593197886376407678879510248062650800454923174021226426131951539000582237507664260500912051091579074766253058171686082655583797085759391539750616675769128326723231334173847843484609305626560500947239558227409653369424940892388847459767087467904560476228533876882454503528796028208580204528830405434056742950928810450680626067287334860856312361588261009704109978698322401591633728880123669421224623770035596035485824982413430008861421096862396940479059123141327542036823423810936016849904954254187585797228714818886277862562292440220573481943880061359297855516195097746005184626213759832258233173741222597079725488927547220872818052985304729951885465668659540038596189741143468461868653631001130332190074889745795536752296504580572497594413813371954041068975989690119787910862788537311093871371223754462543530417044469995475766574240499032118497476210687753180797483129449841453985044840571760254063666896839712301329291740684126702661799999043644012576516487626529454245844993962334224986725543427290351959057329895047783033735105623273531258089672876971692964628064538638469874854108033868223103728757188435923082486189442613892373178854804813012191991681994857086681291404986826395866161804105037497089149362798016238616749604515856527158153759530185857174174586574302016575888043560445703914085807159197101576330902088479022447850320907844841260933806140894918018543445002166135032954557912298432007527711712206135839402926202430170379776391055749927550849165163624428859660017261522075513313059711046861327714150200811447102812254887401790554042882069134522707611940195396001192418185710484332632700784787636238876657594571460181431202347347185446886083865446544825940788220647784011036982037083342714122897211160170047488443168557597933802556580096026036053722897224654019699693374574973523785996319408208481398549076070190765891035208248783594256396475345514801663017848260870639244691988137531160994885966085463832854549551640304672964131295087148178804970187307613376144080587055353569183138813165019442190338414711402680820151913888492685730779084515307846750295145724293591132044036740553496593551650146512037854403686956487148029604796887397591585383401758997694117737506570359688327592788644847853879114903185024892580332876499648641924656297804128509066033650448945374576834259028776234358379007056578183969396056593186290754226032236847960938450176210223086795402229166420055540915839740367685682308716627812995325872026646197325820467638802281962215126139008208832938735763268697589098219651404816836796246037399905980639383051026384006396491263902587672032662673287638957187683623528672110742914166732503075143297971478625436369177683072606014401673664316796153892528137092162431715833528521376973966045799592127895281761193508513166154377967566542533297428713405576255205549482993322694559394279413514159583055551082055632115284203614689600838188896245440101203757289677126937805593424260208565088623984588437016169239141827407037671865752566227062755833166863588931015442678858657495216692842322219233122209134223843582743850384343721495308115797471458999332587072386160822210382966614619814405653495741630317543345275420394638568447174841153814840701847330294022063756540930308429080566480122185316718659568959872743571128827940264084218202398345718833049303624173159393754568893689070666017629695141726538757191758224435850238411406138044371616599234245134234646615330929337342278585988055450216980675434178303386935966191427208493790507574290125924821257983717486897510917747789831540545323200787717603533210213866284462884205709418267448591021157319360262780110210342247090559119058095688001528858144588260426990942583028432038573987944046138359512505058618398413925426639809310344315855317174423340455468391573257096617389319961565194898707699595512115441969399488803432988743235770779425859339711077386352845643705193953547788014307071341361832478338484551308543141434913136777798199560516385774219404240113656685536762863111377338172657941129042482641193820169185164211059272116771176114426089484218095236802508566918758527741820465631739408986309608348936749525822465142405073976430468085796616486811860063543778899649991911061155054735359410161608161210474542612539146642927297151143772948755892910843405195960284270689731819813986758641305928893082381341530971744445124653329447205044074475226859981538473783793622631040608788993287673092310761824208838753306547290591261982528874305795575821747590411802852524657225604187404959893383331555437620970231516359596706812042699116098935560114744728473660141906992173942927130100104711463099682675375944083003985912821805079854688572964585976141505838990880206431341607225956665968105990914578598886449419602680130754819438153756978351882866867150075476679418445765554032369075528861525864939056144936143495818550460298827169840439260609604873958647711742786058290559722778916697571582909766855631226374113939439659442372063351858137287125252456902583257569560742658668185353127818633526820550062918491770500513292809294938614577456892141834921385376345953371339419765654866490529669373812042947842553328182594291556592074137109019979771764896753739956606069454568256900149422190583175556369448401389267808544311681486879823992338742264671080431180763728626988607989782887742851078346689520839091081018410679275166641816716209523632502770184593248608046630845983093246396565354128880496987878663933795005452424534828548760416831700976362878350578300121502996844849872874641036337982089426670569763748404178767090308375671525743160120085507483893580821373369009331775008428151430166372425970062154559374253770248821810685628713441721218940100789377207686577636978440827295645694280398266373427307349000529641513495191990106628205342422069652234299370624200143692334255945325567584239929571053467201715771697083006082254578200769546385338240580924352830975937988144349219659681367902748968782065069073766782724357609983759453293910368784002894626406707301948222656244970021284012217347570587184638331335491044006992245747855545715784027064376580194253613227884028116784482028392291536959418968967046202592144588419234432698817544689990556208683421028263379352672081213947414022698596929463239010026648132965508689624342044438589110664130060917280843887298340143902361192766668155737315089594460732162378242919340551889701498413087522316344592069738178834111258904735356569939556954118058246558679173701714623154764956698823113807287016124344104049961532124350081426195376293324196459380319689963650880974837788724730729784624563278913195910446212410465704098361944239853983018086884939438679514131238376356081950485810883689118485615809676685590975715519980620450299421562695463406344283401596876282261748723653638940928644006341599710834332723287728864694903611286457601171566072730285295506202262737164045873551120387805781238367589611302929241746249628961365511700648232685706053467893652921406501764179953519241450206952317064639659779191130335105365892933466776140016645451441014012735262636042887915162324934646090616518561807326614143598634914571554458671713343418528733155395021300207850077180099750354889932992070435895251994637385184993179651789792193546813894273406644325077195575640539532399514216342208511517135122038274588407747522563207795217506078577529529254937962834986205908266292281641052022284961418172094741039583753822775124573361193325721789799649456880398391272548033573701091387643701629063392449207289080861591248914875513098111695275579583749420291138073262683285332235559041803731602016962313419637752388932028435203451688084872715924424085007195422350487137053488045835900480418981852454140907869170695801502765734844407897742258018176211771992597709306021111742063330020648362552797201329381994724377914575660415294183031647360523695347919393115035827351039614871096198134942633519625697649182278511590515251686347756312482394643548344239171633170074825873664821167016895224425542376204479029390871437987829041720131913291630568075173372865098202317622774090586849799322298465696639322625588916961682264199679270587941365507359545598077622978208526710300061611072393219279474951724445163297361429884428361967270149554137803082325867557545277181229324071237880938354758361056606782673965290116868529833877662259967589971892894725979201102506345001013685752360306389519012146044153771523394459499697004109986073030641135871075189794769552064179887517126026827952593404496306844921576320531225912775840066132050366052089112785932185270869849975920901660230427314675256213455771108889055821322414164883166747777896268593250547877751829285783108524172114681512500507270141557024038009598308058846363876735672752232380962139520724486291052214930602588017272723966098729362574876811476196536538731017284695292380847825573771684113141430809074077844394124641617819746551334714919705354638647609847396867063228846927245618909212633841943890916737511484498378624142411756430165238967409316751937583367218121954834171094628916803674081442812825548384229391026224236956222934140649360230680044557930954433719546486594303161192928085546034983913565184393494771049452662951677759241596167694750649475518069435598193270331177633566848085675511427321181207919780730022250997420707811556126325332816783524942753843331878375334339547585921794222085190556896355618945971440937789127274181189878739630917573749653681260408801064936256369223441859217544478500889549320574524367975589905651034886284622899370750445849559275134168145652525704232339920241699765350690749695423481983128536559762668896081598989921312641933235869484682083851687982644771771705052469672669053903650026283006756299966420924592841020338721242212606661082245262129298218653848542036121152646550412697427256198296605937746622339220045964907158871275931368301361025486968876598378162076283432204801924174045045255969749124260840442383981505681304220121383410849216572682212743286105689811962789757306384916872478027385587677569267165281459415606274204626132078335829317077453383085502314082831728068223582512567389139383319203621623182480159547974358825410078022768728373549431774457834144009391215279143455030673144561852850515380806841168218047727168837269472494568560179751028911551680335925589807348036063779809041115445881029955000359015286390595268216857428276725879595965300356797994051426726694173981243666320875238314080857510440988586708593200831449339651606789019688321366164543643311096529334641144996828343464228290959185763405118247060047698673784787127577729412356970264513304936421109335551276460619771914162707205106798956203343384844082678351616724404968151514007188019021140718365349211421014502526792905641779423064450478049730065668881599834652977017310735926258090787101500361282472217752244415969051536298045730255337176175849217855735201141108330299313238953152561744521032727728397860908024277821406407243642803538818425189991456471976713608265003021939364270929108288067594325194558635891436987796781836119214986163968914888340004445055407537113132919718525040825216385970830887990989741988369180527733448486137763254956442760928795518802777033598832229744614250821655384271990059829017295769281197334371765221087619636922101976874650366600638085141006354296985512131980465694287126173193736932348975911053738266904424173872330887402193353342523368483023393946955718918336557337193650135301027076334800321464694426946857456782541447349723420884807886628503678653770541241263594250631241708103724613295515622836801986877177252288301239231768267857337097143451729822472950845952362415558248164237384404259141462531135179469292620278380832323241555727056565678364412422436104908426690684991045668733786061010148273366758188705307943082488874826561510977009053175138725840926245377465426398528569205863960510866779618050354837781298529943856362521149008168596316831768603785724717468311388015476211620463622391365823341175348355835408537481562149164187915767334444382063252804094030846668623617266457548852751525349609569538808067309327640084903090669118834617820626770561643668958924498803212870830936203196683760634333399535378166854980689519470258983927268472880587050812198482008608718290460315358314881087487137302665643138877661187238647214129335348789340566001216146322746188790089088179316329205028176518884825609198755544809519063525864352562939442188108904627139204689755959860845125796771051384351327819796537802168511157896588219285903035682295968840082875755113859575266808134763338406118206740104825190665367313780661919953904243274743911969141556336873022851083554196329958988766009184385065260486098834116863264323848859589398243079452098515349652495398366023231936841531594865254611658554920985396357404266142878901237844329429837657786777173575407559335460439597817671819523471850841381452719267236972770052773519861256635161123723255589144068200572258816634111295646894021794592672915553306872440432129269663140286671612924425797547610074197499919991377207340470461396391879301090482773940865892473531678481922261237983268748928417746589585382678903135682857774634315534761739102547189268260038213924447068956306098557883838805541384018444119013725333901630559335882675917729235507905125376342702633060394385277883300026950836647466412274947211622247799742904441381840676698535221377420555364590759775870859275731079458401674781123636382924133665015957066889730918871932629580642149837948194328895918287471642330152703165838335519473397197782844854612799555773841556206878078960002550097004143191584666574827269842877697986323961229211656165673004957030582927848916941467751680678781139821317380574269613288335335884189637938956491942746159466964478990481988913718530164849687106344734192742146963252192415016537932125790603500595691892344463061773972239723914060837983415256819991861445631469108113634482697347618022919368172925613364177018818978460051629033487708491204320806000719595334353126836869722767174203132309811417305147209740739689575826320903337205416178656797376969288441666697257233884128147950630610417011138034780016329721580479972024600864999186064277888975291724862721570190694460437564712482425206979600272700639010517528597194020400581842599049863841344461297365425757580724332743517337695470223360646451775119359827166291691202584086739172775525028029163433623304659090643652774956695699448463938563425952635480309120063634983255948149053137208434525076422597381945159072503169607664249634538464761914055967760191937690987373610289348022676051025662048321330863740190595526404791310897294322110959189762207158921634999069985828605137922165888655833101238698499969362055212960202256435564637147432912895912460701984244757020962099624004054941310324520355602487840438046819075528486475348205872996967194642254913104834664922963418324124025517918445115874402136520724753879440648640197052257034364319222077226894429191382363147823420762949200503835837239021062540662472352811748927747589149910028277154475028789359110125155476532474049351919309366215984920106855426585238451185451803785797337459254288417675760750933077726617060967943224722172669551181258350832605024798251069497910192738875094538074992442311160136535127563725412001498066698829787711408281194890944029297571829072974836758065255847448316390491430257908959733996988179174552977947240068474111938006960815734748703376838220584280981189774869419867338050807228480166547573738922514074709599545347811680063087530355422428446596396142165347169791766822425157087889192289460697819507140487248929682108088826957917379184375688778943165664221281353566574591548617511888778592878631143027373764056380324054426876696602500802188361194743160536965293963269085512697073594480055908009029749100140233661710257018348286096240963273060495977560274466836161555652408007267695441808230926695336039931327705713306016098840784073226578749721111067419106129064494965568443943683204341165613601503303031696706430605538439040003232174270701476375040068547735995197578843540037672974190575388857849476775802038943763670724409419298060312785614381436009941339539353883762431633095429950234422824778888954823897411761894317708132830340739980691314168647870723956496008737286780059012715056102032758979663198165966227552310605122404479601503446075135234267699322425142752666466447033654460556896162461521081282218893302702370744241338169550757833453104942882077580514376249585354934049247937901471503418578129005379178791599708863171217188079691011979203303527243941322760443159942027996927430697611908519771389836019938176697454683345221527206165277321964806696631896947011371003258690844962813571172338980417517651953464960892290903543974797033899484373229398839094573230135252088086190693699826023256726646641387321105410702697936664669230032177182185601350807704070515629492471449536436346451467051378343670537884007897636309760602303034924125064283592643159395541351622777417832517216651867337240656072246736314282405342572254450204337089054194304220108008530808814341188434864327116365721756758649666022765863534334845027408168642612499751854367553375289299416248687928734971496129917676960855564222435167681513108134997667712767472222577427071613542016843027410946072075238767119674656258097825566472381499277717000333498062260737313817910518956882667249922743079759635469115670239706165682686069274798175514870795080069088961865115270086625501191812467935661997195088888966953263008379954048560716743160186320168628624630174414479650138599087031031160541213936130999940983726202332640373065308870029181728944366011370873097858836400221980869855742674423048610489734278154984443398280596003184285754599014357790245362740393544648526796835051006868490285054207869075314890783500709785436055597239930928244768182955303133031579099649873872031137305372707278173029213415268320004859657180601463888574760123018660353629937877877586855163379613608954440165674881937586432789294684719440408383996050202640724620803963206567362456517847557293739737555023708210979360860923138971550973682245434149624966857574922789101303831398354754040668884272867425747922426165822998202536046692038025280168678974645680007737166961858694791433606319970038615441289362118721574177418089966617696700440295919489325831568812690007238467323802217029397454881469955182804716255705375518744094077830497662858468232931957036740899051248216922759828309388179631973293758897350085749332721015025481839411490626653003580782860478601859552150818812776788477338362192661250917373766758589556237508976788045447176203824388151163429393498958273985150646389634435184369811419626038373127060340865615116447303591125923845650351348983197962253896155820193204586566602313655064342940361691379481586987484434894693553190265996156277490805099863792676786062336799661852822906727844686377484441383339289192222005102002114989226023331091199053523593718465923071228154213753289998095265959584679072475895839330251046144977405686886148346016637213346679841267474405825826778852656378296974950256116222624977117216652053192276329142297397287575131139443188461873167972511464824536804486121814506379994378263734385039324025410357850404225146933931753257366984410423580733697025327320105149061785654268064810992772604422412162996954465617914254060165655857221197544266616700839412010163765714700076729616925965455490242706145877388513435005441255400847189095937262057244125764742593088360639608512716743022613978371944785519634012081271194355202759307436007509538445691825686265517977748445283149795336245009911783479007461032535038885032442224758354818660892328217639835583583571662108347176017684146879868291675548500994368641082970227792286273961233468498317967508787763407437535378062625767187861433854978661699328840547627252619226602943964856782266970332767983226456831889732323501974406248061309143471582963094312895368566487177697502670499722272749808647072599116369605806265772570200121390959524226564345322161808382424957596340631483355864878659722927623361453594464487324382969675179810268357850052016569267901769533228022635753492151550061062278378239140991979256762283676557845761587989724725926117203360497349365208800178242715172199790714877214892578664202492016692470111425532110284560085807394193043073199350678971295312496677459285949767847395469664050796924064527451096349087019441341017819807144412019259704334390562332245899467896746849210205875471653722767196109648981734131339713840005578796017007067747831243701948516462510285740874062809628779739279577579979749019196066211973465190056081810904343330539233239292946085328510586240176865918105268158640931265091619379658091292943767288253734848102913172717002039982774972375357298280837180748345489419367438150469896902436578743557006503160777940199597794859116341760566409062759600109468926241966783919771114787098680076001757466446608327922769715858933782833675949786100154943350369660850205458968093684311665559047625955893658169098312429879705727054494513788483492057316587981832370196619025854120253843527315338835019302194770711172573703674341677562484222835792095829049004332737061102263491540937286228009206332140152998121158961301345741801907096676457691501201010184120710668585342276260977389243490229422775348183871315198682477462104715483599706547860436635942160149418720966941275226332670049498103984391900679219205021014381349892080842630542786160442463247414442319556942417122683369388386040918870383879240883243799023958733363223116988259618399921343767134313212805011213525061545550601458627861267276727876898943884653324323092650248089745149838058340389508855299622622353763688424655026982137258272784423405668803910941898961900559983766207789644816284822647091189766781763719509217244554363053763782099136656119635810819707437396234151780907039332089773390337226897925275761054618254530474787501269000716771630451245334862633673315629764759622682130471526425629340916751312897844664967325982669956866004389288659152395643935894247172446515839624879253620842511605744265172232520594391437639149579395558300755339637789233370177344570896815635581038943808471560601202970732074832523946833955862654489152720315509161692948005827462850630198554317444016055213253752195242990664921387027302021949248966594149946503592550325881427254258345718608374856773574997546471450211497361933000769727964784332489429356083744752900314155398167680346423687669358335796231336493605335185272439555425288258227277649535864661273607805352286165945954195848500963061104501500944756632839556900121694789527553197414596997271677848291481112157252592628329766126822745858165265744248531196166624832052359640918827056129893349485125073424349371830487924639683344376103952812285948672818516444913214151085311081992581666430305672327387939081303887608731782755000927353468214020146904253798671295184183057209008803585553704944361523642114736381645492318362484681251795980053232379710976013146601347968900706185812459491236873200805316224809610125128848533210376428917925183648085021082663387758355847893144852965671970709782082196017417264573688009762909561105838419899739167071054048284688706004660927335655469874096315293168876810148794398135457505795822550441332797306330121320317459222689584883150717990776467201635535467604439189691283104616082021232766126897016953965654294517038880462400503788650554081311837967259174220963190361932896443118216086307236032702869622621975669394516483449723199949361447926349800239647670977446029076973507344114378650783827704411280450968557763786951829514136474248559359039311403717404704440286154485496024559913408205720257729521377293701345618190146366110332551521648147374891241723504026703987456424568368958142266452180424963329571693534016714861809631942483459693694990394585162135464486970790637133775301202526724986771246925924021461881717019882148205668326656863773427337639089964315259847644583254204486757947860304823655094916908358714489615285619742416252453239593845545319198183563771320705020164825801324266896601772048920691107417947894220337010324263946141376584113125730243935366182848733396159335123152209866038844719479681538518884983844766506024432533606563433341199942921951677976545095088686194689510526255593110451849150699055821237639458364796099404652531462634678040977505629221826973687383634852571649512030401132756741899216391859578500419132757659096430073719745584340257334245921350766294064882643094709799760816276302547275466744265591911121094516467272867258375476219859170006654991360118871771129639330220941241045986631793279441947556578313497537220010797687775729996123461322289001803412083002669967077182466898570172529681505666285947153091565773280984480785366688926023002314996544291913380035509851955843002687041852091431494815293946075943585355072234357019638080870594343198646448291257485327756094218687832521505198364510169429950641788554611636657868108644571815823927993378920063426646120423028884127782059583817720965349193621796542677379700580813275998542615384304602800558974846164971292111648327081949417838415869964611633383590448727861426339229799322097016232779234533033914318066445978465735887731620087123296241184873048165365359227215955704277259464818248334904581795825909299885773755892129773811596251427954403340767154946844784106991565675444787148700423764702465767625678830473234723269487286932817727666762200083834431481993961333839019603868023941720607438503866412182012592670966206516926858892107514909876388553973099892754716021632922116520481403226366979130704918627366992934777236717359619071524425774155631158111227246143921467132797076684248370898558257580623197909067141827210092177094368492896407221424351902141811929509054462617909742974698153488211520413054103168763306648768387909376542393044624202466956530462478713546096072537970353924363985224051824544274126204464910683372916163068908862033449953547255354142722664478500857668851810704740978169659945870718553761815173884549351295888476052991774201209546795997369414654781651211789026440304968808607605953341067191866925836997744658912671702784067434385265326243702726415018508681629675150963234214962964352271526156388315440670669110029088721153826774985717980073141627128165188946630545430607122236119369398062857768642980059516473357453369790149167622724080690391661469240797533556621880301616478676793631931207568052361740656036234846766248069672729532498813539206559567786665970885014292447548775237326635379817232526780298259134414207869896755881587998755454662934860269327685049511420152316857844433366555425163519720723124467158686468962197327091492400465348559315300511320375818054280045546041462241325169748541568327953387918306081363805772005189710946214798680262116977137408507140237282165337020357411679769770406358928929889287793196900693104817223775083206036793282432431174372927318687851985821003019229610998225304890290311878202213771952676894305642895873552594603078144927369475169631168393310859389698453165834671698554449284032293538646992884853781258419304336023728760012690958796710513400280087547281194394038715655062656307670099165660002793066970009221162162234897875307166275693519624725192588120201692014580107014845740027880759519051772966021799441737619922184274535028373405246334979598107602852436265766899409566815353092568864508279923688971764769621662418396427693595501712329393893083102262350451186168416867602078570545200628354791905240237477739705689463193489142606181626641268187201620747994412495706495490941685885315704211159995132713945257466419475316006693239558928974963322285171095948236424791943030313332998705191660427523924291160421456718399289158968417541688443962963871246933719893094383001745996810980093006282171439073187208313405942171185426748858608463176883152272034239019642131752470995445856032720775113661019133393329758059506781682986109038271217872874220528320094274866781250614394295867372828577358094226483523390728571893557268097834192275324081924348526449121629202136057711663131918788832040894879803029157291250637591616927302375501606801809001895127125872640813789893809398119299669261539515295810296751229490487761744037573348300014288527357950134737024317437474966275482776984050110581631912245700215316509403997064621351097773933928550971554616981921009631271549913151109900940545356709408355855221767954119732772855612200914314659548539518549365958442464028542818955459120999717334916328074598589790094507292083516217557103607771629758846190938402011287345320423392670901034141930597413449452200196006447899420523990555702199820041797552536192271655667657302281804313267582889587868802121108523365598647290481339247376334761647539141229007611542674648068487371208923467521598921862017839191011046075437037929369705102360717216399190757680556982795333473821149368600328339011619058048433829012374893838811229564413360153864267298907425040776326785050888372225845150538693729250982041264665928742384205155276148689364549870872458360989923848667423632500630480500350737699442156722898309511028886570471518195526379397811431636602024303176104528732054539629221329197483699765837572010451871814151492628460995386069363393875581044877210044949590890374906320509596855401342442610236176236827035026790320536470294244118173731867277346109471413713655404480488504921183136778591007061621968131350871367241431297401907161560280770887105210143451053845657081149381556510791509970951900447173774734008108111371590593229931698091008729672541727145747178153082612162373856353977356158266099125688130229865785177378485428323214090636245879927752205836601688572973615365920786986146453248286695289295657928360940915471101803330586282492790074650458899917999505799179458372335748363397720624887048743793767832199669969327944841310486647895946098911823477541756318870720664108703972426060175110951141908321179197329685668544771570939194205401138427891114556568989573746951033574380743827943269265436187826072826155222458498286877712626454429039946419136654617867584550700927001541547872631461137797892789807716344180472906238830398874047797297109054684021406998377422748576061899569078147923774833765223509525924902885495357104123766282779715494382529236095269583168671714823841998627840328793667251122935698685106803102586308952121230192050\"",24 56367622925 ],26 "output": [27 0,28 0,29 0,30 0,31 0,32 0,33 0,34 0,35 0,36 0,37 0,38 0,39 0,40 0,41 0,42 0,43 0,44 0,45 0,46 0,47 0,48 0,49 0,50 0,51 0,52 0,53 0,54 0,55 0,56 0,57 0,58 0,59 0,60 0,61 0,62 0,63 0,64 0,65 0,66 0,67 0,68 0,69 0,70 0,71 0,72 0,73 0,74 0,75 0,76 0,77 0,78 0,79 0,80 0,81 0,82 0,83 0,84 0,85 0,86 0,87 0,88 0,89 0,90 0,91 0,92 0,93 0,94 0,95 0,96 0,97 0,98 0,99 0,100 0,101 0,102 0,103 0,104 0,105 0,106 0,107 0,108 0,109 0,110 0,111 0,112 0,113 0,114 0,115 0,116 0,117 0,118 0,119 0,120 0,121 0,122 0,123 0,124 0,125 0,126 0,127 0,128 0,129 0,130 0,131 0,132 0,133 0,134 0,135 0,136 0,137 0,138 0,139 0,140 0,141 0,142 0,143 0,144 0,145 0,146 0,147 0,148 0,149 0,150 0,151 0,152 0,153 0,154 0,155 0,156 0,157 0,158 0,159 0,160 0,161 0,162 0,163 0,164 0,165 0,166 0,167 0,168 0,169 0,170 0,171 0,172 0,173 0,174 0,175 0,176 0,177 0,178 0,179 0,180 0,181 0,182 0,183 0,184 0,185 0,186 0,187 0,188 0,189 0,190 0,191 0,192 0,193 0,194 0,195 0,196 0,197 0,198 0,199 0,200 0,201 0,202 0,203 0,204 0,205 0,206 0,207 0,208 0,209 0,210 0,211 0,212 0,213 0,214 0,215 0,216 0,217 0,218 0,219 0,220 0,221 0,222 0,223 0,224 0,225 0,226 0,227 0,228 0,229 0,230 0,231 0,232 0,233 0,234 0,235 0,236 0,237 0,238 0,239 0,240 0,241 0,242 0,243 0,244 0,245 0,246 0,247 0,248 0,249 0,250 0,251 0,252 0,253 0,254 0,255 0,256 0,257 0,258 0,259 0,260 0,261 0,262 0,263 0,264 0,265 0,266 0,267 0,268 0,269 0,270 0,271 0,272 0,273 0,274 0,275 0,276 0,277 0,278 0,279 0,280 0,281 0,282 0,283 0,284 0,285 0,286 0,287 0,288 0,289 0,290 0,291 0,292 0,293 0,294 0,295 0,296 0,297 0,298 0,299 0,300 0,301 0,302 0,303 0,304 0,305 0,306 0,307 0,308 0,309 0,310 0,311 0,312 0,313 0,314 0,315 0,316 0,317 0,318 0,319 0,320 0,321 0,322 0,323 0,324 0,325 0,326 0,327 0,328 0,329 0,330 0,331 0,332 0,333 0,334 0,335 0,336 0,337 0,338 0,339 0,340 0,341 0,342 0,343 0,344 0,345 0,346 0,347 0,348 0,349 0,350 0,351 0,352 0,353 0,354 0,355 0,356 0,357 0,358 0,359 0,360 0,361 0,362 0,363 0,364 0,365 0,366 0,367 0,368 0,369 0,370 0,371 0,372 0,373 0,374 0,375 0,376 0,377 0,378 0,379 0,380 0,381 0,382 0,383 0,384 0,385 0,386 0,387 0,388 0,389 0,390 0,391 0,392 0,393 0,394 0,395 0,396 0,397 0,398 0,399 0,400 0,401 0,402 0,403 0,404 0,405 0,406 0,407 0,408 0,409 0,410 0,411 0,412 0,413 0,414 0,415 0,416 0,417 0,418 0,419 0,420 0,421 0,422 0,423 0,424 0,425 0,426 0,427 0,428 0,429 0,430 0,431 0,432 0,433 0,434 0,435 0,436 0,437 0,438 0,439 0,440 0,441 0,442 0,443 0,444 0,445 0,446 0,447 0,448 0,449 0,450 0,451 0,452 0,453 0,454 0,455 0,456 0,457 0,458 0,459 0,460 0,461 0,462 0,463 0,464 0,465 0,466 0,467 0,468 0,469 0,470 0,471 0,472 0,473 0,474 0,475 0,476 0,477 0,478 0,479 0,480 0,481 0,482 0,483 0,484 0,485 0,486 0,487 0,488 0,489 0,490 0,491 0,492 0,493 0,494 0,495 0,496 0,497 0,498 0,499 0,500 0,501 0,502 0,503 0,504 0,505 0,506 0,507 0,508 0,509 0,510 0,511 0,512 0,513 0,514 0,515 0,516 0,517 0,518 0,519 0,520 0,521 0,522 0,523 0,524 0,525 0,526 0,527 0,528 0,529 0,530 0,531 0,532 0,533 0,534 0,535 0,536 0,537 0,538 0,539 0,540 0,541 0,542 0,543 0,544 0,545 0,546 0,547 0,548 0,549 0,550 0,551 0,552 0,553 0,554 0,555 0,556 0,557 0,558 0,559 0,560 0,561 0,562 0,563 0,564 0,565 0,566 0,567 0,568 0,569 0,570 0,571 0,572 0,573 0,574 0,575 0,576 0,577 0,578 0,579 0,580 0,581 0,582 0,583 0,584 0,585 0,586 0,587 0,588 0,589 0,590 0,591 0,592 0,593 0,594 0,595 0,596 0,597 0,598 0,599 0,600 0,601 0,602 0,603 0,604 0,605 0,606 0,607 0,608 0,609 0,610 0,611 0,612 0,613 0,614 0,615 0,616 0,617 0,618 0,619 0,620 0,621 0,622 0,623 0,624 0,625 0,626 0,627 0,628 0,629 0,630 0,631 0,632 0,633 0,634 0,635 0,636 0,637 0,638 0,639 0,640 0,641 0,642 0,643 0,644 0,645 0,646 0,647 0,648 0,649 0,650 0,651 0,652 0,653 0,654 0,655 0,656 0,657 0,658 0,659 0,660 0,661 0,662 0,663 0,664 0,665 0,666 0,667 0,668 0,669 0,670 0,671 0,672 0,673 0,674 0,675 0,676 0,677 0,678 0,679 0,680 0,681 0,682 0,683 0,684 0,685 0,686 0,687 0,688 0,689 0,690 0,691 0,692 0,693 0,694 0,695 0,696 0,697 0,698 0,699 0,700 0,701 0,702 0,703 0,704 0,705 0,706 0,707 0,708 0,709 0,710 0,711 0,712 0,713 0,714 0,715 0,716 0,717 0,718 0,719 0,720 0,721 0,722 0,723 0,724 0,725 0,726 0,727 0,728 0,729 0,730 0,731 0,732 0,733 0,734 0,735 0,736 0,737 0,738 0,739 0,740 0,741 0,742 0,743 0,744 0,745 0,746 0,747 0,748 0,749 0,750 0,751 0,752 0,753 0,754 0,755 0,756 0,757 0,758 0,759 0,760 0,761 0,762 0,763 0,764 0,765 0,766 0,767 0,768 0,769 0,770 0,771 0,772 0,773 0,774 0,775 0,776 0,777 0,778 0,779 0,780 0,781 0,782 0,783 0,784 0,785 0,786 0,787 0,788 0,789 0,790 0,791 0,792 0,793 0,794 0,795 0,796 0,797 0,798 0,799 0,800 0,801 0,802 0,803 0,804 0,805 0,806 0,807 0,808 0,809 0,810 0,811 0,812 0,813 0,814 0,815 0,816 0,817 0,818 0,819 0,820 0,821 0,822 0,823 0,824 0,825 0,826 0,827 0,828 0,829 0,830 0,831 0,832 0,833 0,834 0,835 0,836 0,837 0,838 0,839 0,840 0,841 0,842 0,843 0,844 0,845 0,846 0,847 0,848 0,849 0,850 0,851 0,852 0,853 0,854 0,855 0,856 0,857 0,858 0,859 0,860 0,861 0,862 0,863 0,864 0,865 0,866 0,867 0,868 0,869 0,870 0,871 0,872 0,873 0,874 0,875 0,876 0,877 0,878 0,879 0,880 0,881 0,882 0,883 0,884 0,885 0,886 0,887 0,888 0,889 0,890 0,891 0,892 0,893 0,894 0,895 0,896 0,897 0,898 0,899 0,900 0,901 0,902 0,903 0,904 0,905 0,906 0,907 0,908 0,909 0,910 0,911 0,912 0,913 0,914 0,915 0,916 0,917 0,918 0,919 0,920 0,921 0,922 0,923 0,924 0,925 0,926 0,927 0,928 0,929 0,930 0,931 0,932 0,933 0,934 0,935 0,936 0,937 0,938 0,939 0,940 0,941 0,942 0,943 0,944 0,945 0,946 0,947 0,948 0,949 0,950 0,951 0,952 0,953 0,954 0,955 0,956 0,957 0,958 0,959 0,960 0,961 0,962 0,963 0,964 0,965 0,966 0,967 0,968 0,969 0,970 0,971 0,972 0,973 0,974 0,975 0,976 0,977 0,978 0,979 0,980 0,981 0,982 0,983 0,984 0,985 0,986 0,987 0,988 0,989 0,990 0,991 0,992 0,993 0,994 0,995 0,996 0,997 0,998 0,999 0,1000 0,1001 0,1002 0,1003 0,1004 0,1005 0,1006 0,1007 0,1008 0,1009 0,1010 0,1011 0,1012 0,1013 0,1014 0,1015 0,1016 0,1017 0,1018 0,1019 0,1020 0,1021 0,1022 0,1023 0,1024 0,1025 0,1026 0,1027 0,1028 0,1029 0,1030 0,1031 0,1032 0,1033 0,1034 0,1035 0,1036 0,1037 0,1038 0,1039 0,1040 0,1041 0,1042 0,1043 0,1044 0,1045 0,1046 0,1047 0,1048 0,1049 0,1050 0,1051 0,1052 0,1053 0,1054 0,1055 0,1056 0,1057 0,1058 0,1059 0,1060 0,1061 0,1062 0,1063 0,1064 0,1065 0,1066 0,1067 0,1068 0,1069 0,1070 0,1071 0,1072 0,1073 0,1074 0,1075 0,1076 0,1077 0,1078 0,1079 0,1080 0,1081 0,1082 0,1083 0,1084 0,1085 0,1086 0,1087 0,1088 0,1089 0,1090 0,1091 0,1092 0,1093 0,1094 0,1095 0,1096 0,1097 0,1098 0,1099 0,1100 0,1101 0,1102 0,1103 0,1104 0,1105 0,1106 0,1107 0,1108 0,1109 0,1110 0,1111 0,1112 0,1113 0,1114 0,1115 0,1116 0,1117 0,1118 0,1119 0,1120 0,1121 0,1122 0,1123 0,1124 0,1125 0,1126 0,1127 0,1128 0,1129 0,1130 0,1131 0,1132 0,1133 0,1134 0,1135 0,1136 0,1137 0,1138 0,1139 0,1140 0,1141 0,1142 0,1143 0,1144 0,1145 0,1146 0,1147 0,1148 0,1149 0,1150 0,1151 0,1152 0,1153 0,1154 0,1155 0,1156 0,1157 0,1158 0,1159 0,1160 0,1161 0,1162 0,1163 0,1164 0,1165 0,1166 0,1167 0,1168 0,1169 0,1170 0,1171 0,1172 0,1173 0,1174 0,1175 0,1176 0,1177 0,1178 0,1179 0,1180 0,1181 0,1182 0,1183 0,1184 0,1185 0,1186 0,1187 0,1188 0,1189 0,1190 0,1191 0,1192 0,1193 0,1194 0,1195 0,1196 0,1197 0,1198 0,1199 0,1200 0,