Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 2911 razy

Dawno, dawno temu żył sobie król, który bardzo upodobał sobie grę w szachy. Grał on w szachy gdy miał ku temu okazję i zawsze, ale to zawsze udawało mu się wygrywać i to z najlepszymi graczami w całym królestwie. Król nabrał pewności siebie i zaprosił mistrza świata w szachach do rozegrania z nim partii. Gdy mistrz przybył w gościnę do króla, ten powitał go po przyjacielsku i rzekł:

- Pragnę się zmierzyć z tobą mistrzu w szachach, a jeśli wygram ogłosisz, że od teraz ja jestem mistrzem szachów.

- A co jeśli król przegra? - spytał mistrz.

- Wtedy spełnię jedno twoje życzenie, w miarę rozsądku oczywiście.

Więc rozegrali szachy i król po zaciętej walce przegrał, lecz nie był rozgniewany z tego powodu, spytał się czego sobie życzy mistrz świata w szachach. A on mówił, że nic, że to była czysta przyjemność rozegrać partię szachów z królem. Król jednak nie dawał za wygraną i nalegał, mówił że tu chodzi o jego honor. Mistrz w końcu uległ namowom króla i powiedział z dziwnym błyskiem w oku, jakie jest jego życzenie:

- Pragnę mości królu, abyś darował mi tyle ziaren pszenicy, ile trzeba by było położyć według następującej zależności na kolejnych polach szachownicy: na pierwszym jedno ziarno, a na każdym następnym dwa razy tyle co na poprzednim i jeszcze do potęgi drugiej.

Króla bardzo zdziwiło to życzenie, ale powiedział że może je spełnić i polecił swoim najlepszym matematykom, aby obliczyli ile ziaren pszenicy trzeba dać mistrzowi. Ci jak usłyszeli, według jakiej zależności mają liczyć doszli do wniosku po wstępnych obliczeniach, że jest to tak olbrzymia suma, że nawet gdyby oddali mistrzowi wszystkie plony królestwa nie tylko z tego roku ale i z dziesięciu lat, to i tak nie byłaby to liczba choćby porównywalna z tą sumą.

Król roześmiał się tylko, myśląc sobie wymusiłem na mistrzu, aby wypowiedział swe życzenie, a jednak spełnić mi go nie dał.

Elementy ciągu można obliczyć korzystając z wzoru rekurencyjnego, wynikającego z treści zadania:

Równanie [1] [1]

Zapis wyrażenia w formacie TeX-a:

a_n=\left({2\cdot a_{n-1}}\right)^2

natomiast dowolny element ciągu można obliczyć korzystając z następującego wzoru:

Równanie [2] [2]

Zapis wyrażenia w formacie TeX-a:

a_{n}=2^{2\cdot\left(2^{n-1}-1\right)}

Wyprowadzenie wzoru [2] jest nieco bardziej skomplikowane, dlatego też w jego rozwikłaniu pomoże tabela 1.

W tabeli 1 druga kolumna została wyliczona przy pomocy wzoru rekurencyjnego [1], natomiast kolumna trzecia za pomocą następującego wzoru na potęgę liczby 2:

Równanie [3] [3]

Zapis wyrażenia w formacie TeX-a:

p_n=\log_2,a_n

gdzie pn oznacza oczywiście potęgę liczby 2 dla n-tego elementu ciągu.

Czwarta kolumna tabeli 1 stanowi różnicę potęg pn-pn-1. Z obliczeń wynika, że przyrost Δp da się wyrazić następującym równaniem:

Równanie [4] [4]

Zapis wyrażenia w formacie TeX-a:

\Delta p_n=2^{a\cdot n+b}

ponieważ kolejne wyrażenia kolumny czwartej tabeli 1 można zapisać w formie potęgi liczby 2, która zmienia się o 1 dla następujących po sobie n-tych elementów tejże kolumny. W równaniu [4] parametry wzoru a·n+b należy tak dobrać aby uzyskać wzór na potęgę liczby 2 wyrażającą wartości kolejnych elementów kolumny czwartej tabeli 1. Rozwiązując układ równań dla pierwszych dwóch wartości potęg a⋅1+b=0 oraz a2+b=1 można wyznaczyć parametry a=1 oraz b=-1. Korzystając z wzoru [4] z wyliczonymi parametrami a, b można zapisać następującą zależność na przyrost potęgi Δ pn:

Równanie [5] [5]

Zapis wyrażenia w formacie TeX-a:

\Delta p_n=2^{n-1}

Potęga n-tego elementu ciągu zapisana w kolumnie trzeciej tabeli 1 może zostać zapisana w postaci Δpn=2·k, gdzie z kolei k można zapisać następującą zależnością:

Równanie [6] [6]

Zapis wyrażenia w formacie TeX-a:

k=\Delta,p_n-1=2^{n-1}-1

Z równania [6] wynika więc, że n-ta potęga ciągu pn jest dana następującą zależnością (wynikającą z równości pn=2⋅k):

Równanie [7] [7]

Zapis wyrażenia w formacie TeX-a:

p_n=2\cdot\left(2^{n-1}-1\right)

Ostatecznie więc otrzymujemy wzór [2], na n-ty element ciągu.

Aby uświadomić sobie jak wielkie liczby wynikają z tego zadania wystarczy napisać, że 64 element tego ciągu jest równy 218 446 744 073 709 551 614. Załóżmy, że ktoś chciałby zapisać taką liczbę na dysku twardym, jego pojemność musiała by być równa co najmniej 18 446 744 073 709 551 614 [bitów], dysk jedno terabajtowy jest w stanie pomieścić w swej pamięci nędzne 8 0000 0000 0000 [bitów]. Nawet stu terabajtowy dysk twardy jest niczym w porównaniu z potęgą, do której trzeba by było podnieść dwójkę aby uzyskać 64 element ciągu, a przecież konieczne jest jeszcze zsumowanie wszystkich kolejnych 64 elementów ciągu aby uzyskać ostateczny wynik.

Żeby uświadomić sobie tak do końca, na jakich liczbach tutaj trzeba operować oto wartość 17-nastego elementu ciągu:

100353304550901575979151515150971918359428775676035474889563845161672534218231458529013050645403124844749842395 559267207616623787679713678085580567675711566143612612377494280900994318286988152730277250107794860106008478119 613685558630400352281747406051443219733007709701886613392343367698470259028970572228245267454022049784034790393 197462198052798148858946655799800389152800205904689255987460198192098197994396057216598829931683190388069099763 674357555645210702385371708854747186938678251752312858831040794503885995621889174227235172254761332530485048618 890894550275116448687639352145019523931020774735138550686792439951767705597234008181166209006264760579837135143 500620466524159902220238697531088527824776432364112329400754914274210390676352984657355443430917645740808065895 752550066560411960950544006886834155738709750499135694536521075422992462150127674548121412103379728157737783893 842291349808221091130663381281831427680191378613049631979867191765453428334126544192017315108170064912178560621 985601308413862358046643546143750135353194725987066512366727993053696495780227942392755438332521838033129740497 660015345955611645053640969084395368355248495984065496081359046355023379220477468754063183268531557892013326014 105148942018611838164688029668238819099624354299176083243602218128322949212128100287934347655479912661320937525 244511880798416873957592108135638505892789630794652155384767429510692233335154778241954676782469027255954988314 581865716706388488782166489290986591656969041871844522292832383957609340759532916059197761053469925857011971125 940618017047103176131674299153302874583571076505632295024957184713005422275885306270850938343301059001592771584 792909490794997042693415238108651685780342328371780289856635256319760638113356801420127069079220819634501395998 119362849832821807867421055176294723138283154948199979449785529278206393329557403562968189396902539830078039334 336748320534951663609730174073528547824431314305821678385927418578610238158722402349314737254129705391019018237 790983310192081730773746093415878472351892292175553157645349446013110830496855258962898005005793876418140505580 383284705503286934058277985510879196154872029636466371289598251995545216959961424722306789309549112006625986791 232441972478144791386190872403134008029790767387008581195305164573555391615345978966566210185088742275210531933 298343332420068196193782243504580813345672803353471860289688426803710862229990270637477808853741485417881075508 654565125155913736620245689904600099303341026324242665464289042175292624754451176649309455348261842468562759319 096346320656515798847990311374919864151653922118217891717022650675171505907298477955791914822694244525559061419 214655353781025103980548188100459271971217116454104680678006624901954167553593573731846818082279736971044013063 729744959286720471907675538581504781195327922460165746193434680333752548809683769270559532082258420125997735727 331159080909722313854500178078770098335553505353977437568861028910473437077004138264731193398889359112407173459 070589828383062072543884800329404701790809230767639951338120180808258306121268894269327163802563661996421631039 818574577723789688756821053783435687524644768331436174369462867935583054118843526605083596847787648996497371085 033669104952114372214250539551247449684385313368080093605335338622848025142073807281150742416117378715639446138 504136229037362971649089340129155494939692573816973238677286804271362649419302305295754028059042324787903817641 718074254714511275194196110849655999184112960523551804153670037054198738692295004027824028972660581540636595596 587199829839027867044771078467623012430497095391549416470794228293969827995624225045918637454559970958516223182 546978819105652752966784466969905816370432796293573938963680042246898288749787875883524304677647796616213605920 906512621188329959317041803238579652084248793390854046148166891102884994350265635224769658707022763075677041130 094640991974032805029811405967413008600988553270996417550788991268476747095966856266697913575170430216403451433 415658628258735852760846611976561963750875736745618475698472906013196995328005220388087894491899428718154841418 890725475406684516947389227885669041155772507221989977059255552240594043627920541690772727832426328649683476073 157718269340217346298866419495410936786084708023482666620694715796782423841722426892187098252480699670994001223 934478290946883607852695050686154013481655857335215124673872524586862064130699323840084167905696992350836740042 176461542771758361731354713699784059683911140446118880762688763424077800977063394820957179717488634227499000613 553377002396933663279408930437547326544871139904642384309674450292078304639593682051108924466015367153607628720 973449151494468281307891562932933911319113588234218962478212404325648736714920766028215753174564242005691828799 867073234578208985020018266175825243554874234946693302671382307649647691490251256271617449490937715960768713613 193855973758859735114299302825885678336311937023052512485840739557411975781204952828854675061850353406934882379 176286148528197967410934099023933523173310348802160183160695397721901198559144435097597730730656303227307104479 093327573826199236213317240089090482956078102260498642800730028479745800266486714096367037499941106869175758124 724163753583654512254237185120444530805919908862207331000099494611475459365571862994932229006273100326929791118 616676995797686150400366876184684696246990863463323118992507851474100207751576779479805686120142745677393555053 234660146231806518446769236407399643356307281817698706584129609650958367199978918083093275896858718275357975366 808992168925706954022055469570391145643390774354079437717282979821189169351288823638312577616101002429772641630 115285257081220301155115933191796155895621827834325853088396292963785022149983473439869989849050149120992552786 940039526141801610423153154418503217474531254972368446063361370237626896530042629606226247570069136294402638095 693417668199058740427008821560678638346715966866190540897588059413275104656852121607994892264495400928617774563 439464362535049115168362923454284599590804717403069488028905927015068363666631036571973257813019018382856703196 337802855160329609301195009020640912975727655370341480069262826482195602974136038030407160868752062777420455965 945787151820429227683203026657960760603538777536206383900676277810747145236814044237582261972549249432760666962 173575379808120957376735825692911656001265042454696995686624513368968837158860401186155234048372908238448462388 027486602920446847451615393660633357699839512133763669892211500056649544335544339183664356038784227725094120428 091555590442370305303954246504130239680780120404654101022701560676435834358858337802464695943789773189625537940 506982431009218418054587942625075614579747714963403804088152685786071354359788997536593642165569257938480337768 079270253549321662098065860763636272785602291399265480606671335632032705125655057356788147249473721219661297233 791426763026267086012990556951138323833596454023839345560207275431717764057583771140395448788108725664179397375 544473240407563500741252109444621393789490006728949091898007846904113334707313402553955158942893241457001010828 315303506800552598697894351192034873421495324830676071387920865023217753821309953464869610729557852428517185388 422123649997252998362013558302385364175566927754578102214425855179600880581743655313117708008334621174091615360 660524983474508947097261284634655095584611049177676246127786093233042868856459632642992052606615599622354155674 165113327864597858372169207863194458308661081503619105630019520595408753508275181997062440700927781573648337086 006272171211671107131495030026176104100719725916819938035272110427862027826622260262723169378700187579807673621 809179362919230989143304978394519575629843754755392193330875063209754906293682827719051697546019628464142796232 516432858669924194692547953685810884222011192970043440164034129904022781911360519179858699969844009633455360624 758571071565271456410282452434498114654959839871428829841238385521740043331397840093718377723894178146510319973 364569778414770145885925155365479520836688451903124030165568630259379569577723615151531988821612062016842780466 506129676900529539194858966659750941013878540206008346351833451088360745804573502762266445442860785152882821738 753284024756568603348092192962935647257317778497207178028029239311987864228437663463316501640234405572686056029 759878920054524599860027832367196742163312795632791304061118083877384055664887396277884465543238765476504398369 891946456308158863094707048692881160603530073366756134505243804583626980487445583017444494939204720597434810991 647678798539622781311362284826641030500312507676878364229263666448765712830817660974224986820849291651671345541 743887832234007097620472483479259534570750579842128425489413884183609934937508647680078564966904228040374985569 484314486615654777225474276951922469045031102579887380261470039594244155799785173285125036700148134584980026929 771431100823593297466572702708179796542272736758778474575796978240947862840215811694558718272040332114577793634 157476786082681588732314997621096121379363865850627530055173115998407959579751377716218365113220266093864603977 441619502776818563831795323586205250494268344796278522738099971076885199105232879809241485538014500009937077286 912315173511701207040872536969500360636672579575304882835126006504548446853377509780285607014213070805433580461 239155314445996435737944334783130874253099567766421053324051817841763289640716014511907568514236151851428231266 753404802129631879644482791235713962295965695917826201183014256253766138605324870240593369500616874855478241785 208863177903389725807306521945762775229895146439813444990230106047543307793136753561194997158837112895490658969 861957868806377557092993441115459382492081670400598887604670435060986499631663786626486726094970284513045604646 596174868468986326738125642103201731067454622743229027023292017661374707401872891021282703738012412088548501408 764062133600962199205011074340154372163414641081736037288439138029181987758922900628033377031433222788406002085 908810214333279076214622251417319121687468418124182148446776595934108440543886229798211806237357735209948378572 713340989358985817515208552648132539472806284446399639333958616815871604968812890336322755584165897624567892886 544252618687602235416947194751882963840877745045997175019410337167167983153331946325317065730517035302110698483 952945831864174667791578892757716594479692701238645794174650007920240674685264650903833608837967573746409635350 337616636080508381866376738497939400951923326716834980788566500419633657048366854757178333034846625975314632537 907211781311140668179590344757184381621586008534573757238418458527026770586676816041565954023017226985585389135 388602338075022726061491387488958682577919707969219750519654911227673436224012408375001640649857719247955452938 309943902803851462860980817868288690635700732548168985029818797196262953774632918414769234256883732421132027385 846333111520500652423996405961068548743512816118725136453960697165367824674843875428898315477147215591712751110 733140280632011676802684459374245800706529403098110074716419822822260973560622035156598418479891064123193895458 653249070764123821550207878196193592610805612539665354790528353035352119165421250118821393444761234538037207696 952984740891928812942511089965627825484581222388066423121866901952084146168545892400991052178401497319950265323 601683111030838352615284710852383940010439627172580155037968121466762668291711026583896949973646257425203893702 737912533492707709966935880942971416602559154882936813271587485370105054797565455028378385483497037899060562821 425628113272976629771282312166802576448299679278850693458697563025345448315887410202759699300793731386735469323 675974740843513451342120996562524868919342922030334062084322650948199262900712597331248459274952258899158584489 863584846440485999226846910414386875783933552522448991090656178527278477833660772805460533310659940435775539750 841159191202796661830383339035619139400423233598966645487869559836680934232659696999134849037653158646027246014 942682103392267939331201455560842902444774357651025329674183835852510346809833449614535088434163666959549527893 381321866332376242898424907670684072187977581169038823368483630184887743738799425084875749068955933575710508346 424510801802863542791249720834042157775968140265040186306520006915113439702165745809841553797718311788258284762 589956096527632233743866165841879148965562680251116922990463778604780282298700125799629387068704273998252898903 745401483590468149106478613640887959272277627087964166258658154108322016773739862530525221630669554285075425932 659645869168943922712426517475915936810099192068551586786407101321482519832962347265020853886805703798261976891 211269077394800517195832396725264285254235386697397348094155859926489209357535254900839209630616738362360551115 113247161195307581084245390173002225609457615930827510492053279178692078455927595909903671576712037439276882830 466607045797369327545299345225938031411651099517938078181636639176054631695527289970928807065889073580992092516 470714024449036804142639873595424985835635669168342961911809197346130392108018515314573635039263396304372793867 973850935501261531315480538741643125794228491618502807934249970247748705064158731411277539262416656281134245734 251198554526831545065967157695303643233992676971124993049082121109067023898536930582067617315068063792865524298 199439769661655410117641774625427945665115286398994555640339164650405903877278351990523535587251118343373609913 764270786390394263904937996422134476815426172351436065379260487007869116939704956145137874777767706973512248245 399616891881273811982815044766920188705421764434283172188037965408236347079279139388016509057209969519994107030 856945846741245423152710760934024092132993461368121929063245853833887374413669625624065493101676441615794264856 214966069043212518239405424511893477250214249621076251867329416749171235651919826883692433852110165434749209115 593859011149650449021227116471104048379368416454712117703600966785374124663451792429432083702620910774125507352 740800385949921939796565375469821173479869054786396191600424232932022741118239068932220086754082084070914570042 617060563780588112658410304769530801700779627294246743623285916329372637853694041544890381427285615671773035653 844320183365487876940100698818374424110893641249571356108989316255111087140288059475298244189950927796587186039 051771970985429888357991380031748905652291900032677019287879398928762810133913320563407562429163874835301780603 598749042499150079491011013208495821507417908679777981927515622166276085068364856511291493203948485684993096674 005643933723475421029460443123319821067755891123982139895270354472439913043344063730769823052413549932910930178 158549755378589083580649914477044033637635436413594013922555962460354817167658772186035425772474119327664020630 123439347684864620328040265786980502397153139413031638977896339135216541416217766643843570658852482742895267964 667209654168492384002628843318270271409077892629923261273704124824458922230004112729935576375289560561624578663 160273627066944558399318475533863456180882690719455909750454094062645367872021475269597292766142887712566071645 471972127637772476915371258134213372682104545341525676120869326004756903753151374047396854759607784366396178682 418139915544670294405490186396304945926931374029556477181943755366842219275969387004681889281309559342839974468 619783226185810099598300106112080291312565293823505277955026458430864600871614355695255018264753194542737653455 014848419488650365769030150433017915303469642355076488451618898966504902984714572209161503506374775108950320952 717495119405117214605639391574399501098659111051525409453584126428693131068286960947922873625190718518321466288 214553117675975948891498030024614741349182258916795569162513787603677401563980967802436760036664208212203178223 603558342294791101333030201802929065380578074681993953835949417849487364108120982736393955199203537327352724736 482727801544947812627899939994493357915866069691571543270938864336558493629793710871217955314120359977222251263 964082151990701941827095744307365987024969127756166115505479810640020724914058099888154353947446467678652962237 295413908994893905921298095929857175772648984036999271010003583010709165172125626683292293451005051394675317576 423794570597209387655224708528935205712598563576988594273511098099405777330757970358285061868093845023389506728 736747934212864352252408714459083038689354744256461695186940846303276763775016001374955379421581072243868963241 424830463118771031880119635411162716540366189224479257749506386369956035656922890231032249974986034368763794062 499747244405073073388976421634512146338007388054718622023013856261425385484875225092459518802246880053968455957 976271919864996135319849175884196463294098028429289072929202636760060338971504443767845315539832094483035035005 834261119568606320647415403892757296595396758296339634643966712676689420433561328368583462166600043304108979424 021904992650046124385871457329125929069181111366792861877895216441074088818696009699151313674033439526998990572 816131633586691969104760164286931335657493401931106515455927991296452117175915467394851886969732789685426492783 585780682583774344984696970512548489137636626864850635900924154133156025284469928656628133183461596733606476669 026667718970825430999604925223718443516681076809028215435171696475580515703101524839098882647025183585570178823 634332268416463396806949393455536048584706281861197934995406482488203400234139069322648602988396618897891140912 034743033312235074969510965915781756461881780192537611248987845672939177972056766642433116359613480727331837884 278641434186833792536929401457199288128303090755782554820470225391331786159118016616938838713814798497315557800 903716978316905565761024340575404314319907951556144239100401637585021378324302990512667780019129202948494666877 548411744142250346546475295343522912430964070078740062470018584170989861602555570081900631600521313271740708115 555080899015738802430051246679446115466505263540719483470842880838520420940351004139853030343695113758077666145 121332983592577382028269486307209961851330150757578101892967487569226083869724684157578961465555405963984721314 657184931120589690722632186954626398443459663836512949124254460132445464350038817464760085564194506273139342117 811001293457004666949255118179315740756270189712023765462830128659607866759400214074072231603821133024453029618 778938740508846769240368509872018362543981730179160326629470408596650335654778364761070059260582303725701405915 221102740381379113583470598115118100256502467522120805935278763483185853065940673465068268389195930816611895666 962260789313722734345798449067275709436442774052730583693447213786924494253366839460704919507680713138267998302 993212992025501410376639483944053451558548517887641458775804698583162036634086096595082202759301430348327164381 674495852857036773718332935813450845093842083056683793994859346424512569751901262225890386505024062091492896916 004180129927337003581721214722188089321736205016909404698593671384449362167726358614617654710022038106038534777 778766434515645166112302873838073120506918717227753304982348241623657205770326329457658866223169035933398852674 855332198328493515889968736063846357556475589491393555087901187204169367236189246698415570515280104365149823757 469247901928224567762757204910684452584214129108950904500111562219567404582654033723705801394020129040532318302 964492464593163398078538123237410159085346606731070241008617587537314561317255175520428499699443965742357950165 067507146393455001575530597983329324129440784865682188959925986632315632070982687415576494592048924057092740738 128752118820745660329295581699036357795566995209054886668298933898558980957029941871000338865257936425176836183 688889331182244855340156118829884712083357528076501696728091026684185016567122010039860955211708750617692720726 755566494109155707388691303015363166478962895103776634666887695277474075777679143377260306694106788258389790463 268393511151834396314581109520947911549891962526748207461891244384415628378948703685771145492720181752178089211 184563659990105041051417721989401263371725371858252156376313453995982160055688627717929249344886237839204903662 315316525446110849667337610015919842640704490192263009907559133983151450293624836316614669591809174823434877405 456579709224495075332030621240932411053540114061529062287197905824605814284654079739998692775630811538635252679 732166747436606231687209670390760525779687276854228145629270184556441129520543577001474207967930082701682710757 650217980399986238731879666321383237862007216805905953439030370361659732620992305670511679391459737493009643035 277646886176569896063593082053329770698260572672048776987940704673401073161889562499796116728601148169663846624 323835579638715043328780407239404218786311068901888870861295674936497097209250088441300749738358908366129697839 401632419816113105020614603316617469378263539304376428738511533037352457905249660257734327188661814533439223965 678045475194295625688062707181482646314446909707660035678755048714410435041411934304183887803108782692424183112 429887404818481980399231463582048464749166358275271697462549767357929125612304736934454155077850682197171620298 039952518302806111805761763859582684257485461793278725550443858992258660075328194472969205790150762749962491053 701154923395255951610313278154403907710072349962019670278446818602911190138938110796574803111377154867358673974 955335473726569277436808679183753491716174529181566624681485194893255721043434725643600501533038572940849650408 251252675659039413146534033576583141933088567751557216340550202506159138222184890857008802665838006713508954497 733201921409033513947968164592581640213155396831184360953223849504825544530896415861096763292593362810094769340 430110329305401156852724695573234672268676046256171806983003525403480266675829446319802573910444583579129636426 581525355475488005892236151887639888235727673782036352277831089172714662392913881723250403093641486685028338228 511852700108630801205311861206194203987240025328274386917352495807872967885081215281300416248071759619842315555 742565252674674647327975081935227016981558242929128575790308208315379592790069678195914225232597664195968596893 309612192554766418063784817104804628822505216488908237580592359234148412552569165293894820889777732158016358949 485155782223409283566188619154992353187768149371081678048471206655218188427733548660682094186506495518745622483 127527419114586864995118615699112953146802216386653695255835473105314050591886722544451145198520908077682460221 716382620910535878789636611228463503758636632188160333644184669049826331844989857419956934523231246233930690161 339517613228828722967891650933891188993315519812793661159648226258058731358114260285193509719216736154502826746 086635857880549902628197260039991550154930354026377124048683875558618838407852446787760979022305065366754799382 559515969152446082273808123723263802263639073509203044055421081858540085335693438858360226977366420251401506093 334239623872780468238252117909853330132728116556152418897038993037323229547505318456284822907077467704802070198 345355173125664670304331152725522173702009708083363322921341857346468468664397303444236442634545755766927664114 175153762588637011460287799950712885201335725670228569517319110205506206361623429341071078199061183183885175379 209527370072191365309613114012399347992701102998936652322605346219519116062355843307330600903273732950849877223 244084501860796788092589835655921484584177137089249565742174003770496090392547105230414768444362990358611139481 900055981869407405445080516973227195811683236991736409848421263451450526656637744708253008486093267101044587335 835084216502896349181938819806247700500246390676205684041388615567061478279833326438027524383303960825576573314 034245897906318120888274076598911294382830515449071239904377386773893406647286464071847568704871917979799019981 961626803873586388510447271361630636944192334740129211229761963554914737539345654150646640153666129283480600232 364314945392937119669143428832211963916371287072035087875822367395509310376502882571879801841152994135153537002 314185331308712824212889568672529205191094367939749015189960108235939109878499858240893252777765842042515092135 933402740856805252575835451361255623452093496995903838093063876007904589927578466259373039466249717875546056269 493130362091904579072831850515177860199520907879722991307965457544614947143724508850450069135221234999112964893 934506207641789437313861045400080525004822707140519613932324655436436425223425077183828582821389351045810502807 940637988540556441847758030636621413709558881655750575612927725220377990497358377485608359287447029951281547174 936579687308864251020520603636551305760797753642259117141197524269253363086573952868042172748944282112964664715 393932424381010129933086532804157520935460277523792284069231725239954374313863626665007055579792728616463277832 629894801987979998337984029930513358891733389340965559182967060376452092143611477237587617342350653462222744247 586016499558804929217365186715263663190092333756350348096780555372684150335057961745526630475283572175363606998 298455660082420221028458031724150388579764720417021629513842007798657714658004584188855405695100555937239083134 621587187567456580391322874562108298786583307718453454971250731859023614918722751235598370710558932194919702353 267378730013505550878048521273471940607465563323869921297403679016535926255515414131798068313823661167766930812 911518236544400966478555611906433646194861273559339451996487487128168253283164413112907622257858297829446274774 675604202780030759227222220367259954322050914757477791388500250687143392492868650697224922362276865921507008178 680645598606211056545916414347622161476019482932784707518653829592073414964162402970271277930253896287433885465 186298560430458560132585186672058518485649321685707391277995218012606240978303071573875957697274237349854877602 826163101093729019874035917431440242103698181292123992611515271582402620791288324651020632972557511186016465634 502546937599509899955698309952143084529446438210914162821476622298098131883579706479019549468680900241771198255 715870026960338903622615214759351664459554071018352367613922064719172166162630671618452057677980615333330953348 489921159293783463822103346713457641787546266941117533357363638068418147735090697510635714387881407019380652436 228286614133521652741228168590814853068734955533325610763409590639455404495500921881468109091350353617328451956 877086830537906743365501405735257980279808484484342649246784042910409441977672909705930418057194416479357544946 521752716733382772176064339624102113745771345152625038918540686594630438743574048475032137504365847978531173683 938927713914976137077559452199804688627580698217941983615419528255969216287086529818598912689634105786884282355 386418485686372075356594738301533050899219846398339049683142305694027385108808262120660360287592977263279434300 082497425404940674498184886430749869781693738153832590721816950958320001664590498331450122829583726976215115735 357908932979783179888955795926945156317169395758682915676272128746299289439576565321746589682076691513281447792 501729339295658872023682940927082108746810313601897835067723579742595475372125191746005981950138240336139865970 814288327747665952569282715244457697972199303614317751203918183311489624326750920533328790328845499039014641956 592802800761756701496905712925735639905679070227842772332436771321502383539064012584520485068458614352709266368 007655861144895739809773565434030851367335978949414433767373699299445195122280583139360850143166609146602566102 782901503740577378279558178410060440782357539733229891336630010679817405279976963151816215685829071362662838480 744269328755861453905405673212959696658212382135749166371461621733825673909823535731462358748956787154189897817 881444120706679569011534106347418170377797025260668622191189511412262624183635636411850415574345658694098365333 457180285904556429654414700092528504301379349937618196104392691722240005189182651290780022597253254536789003265 629973728013813986213968670315728525442117742760675101218559729965304415091908900111822416723201492019138962752 369693586448119562118790769252059416682705851833262847652421436954455842096774892258994588851777578265617998728 159255972774238515081246710063421536936907077384402801728976251555195516532614986272857723734118010861886087324 120831609269521136174023650044943644312397620471919837069361317335391736987441694686888369311503062337303445274 845200003777792289155177744343804292657045512652207068250856874036121216234265499435138592359587359320704347698 756656486681304369359948507454230714168101158721724576423912800035806671381950810954968071257874048200055043323 954897950485292800452310917135223214276595191576747667267079026391202064267272438368525781617309142449787544563 262280504630826370356213624465175211262432737551359309091775012038162164171600132087347334110024221701913402719 396628038165485855127215518939638299203464047272355436605453439414915740536970834484334974120010896260939441024 211509441033385166208192925327044344850269850373821888519250795272004434727447941830282253000468166221589734192 737531534720587850063086131873445332708512582906888924295852398926757778792141577416268384221000349775736509651 182040998524690508336054392031398035337472715891213699472516120877323238704311939126616232793465584331020215695 367593739861773106256338099033898767142610765817199319567065220128939337302167074715257330654026524852394655040 936905781206946080334568006372557709996903752873859674631260011542733574431387225383057094462544431591331540281 454449584226869625458132931978546594566000605910392914661391234537808579349299429830379452530700366342510311993 462983416915569162685885191013162005112261072567304916172763161811794115077859827263852163828193904419586354000 891557530495015236097229740987593241839383592699199376760488586760382939723638507941283566729378887534171674778 413306324461423292474383933388525620390876409733356236764403504666390939727086087153536986671521079718069158822 742779893317819919059864082624192735335923973350577723249777012892900127265550717238595902505938826566048105207 815261142268081348806096803070749965905575359819236307594606371799673166419357312659573985224962891746381515114 785426070604543849374238739952944735357957436073429323535755228880743732061532576989861123245332568484869164163 142427467285063332047921081608343984978555446441445014583089017119537347507267448953231924017368347058366804087 351421273753539496333871418392252221374011074007350679950446498769440985197526722202217809980955448131745237507 780817629139691033018874969418280098813519294521303930979764133997594060369036205211973962849552027366976024863 959883696821900505559595357358589769419975932702078891341427699965692808081060118726581736902947535588981161156 151226096880986333931900221065201453652848508588156582782550689889654448621602034498325926054277184642979988105 938684208860669219781132562784338502101565204503818698397027180611102950838095663861959531551297863090062125690 021862228645042840819692837439618786800158189256240335763828806030401905753300260558006910228433413369261347760 094515541788059809149767304640615469953192268171247642451636554764063721096695280975441992879480446760033364299 235675569269407936412290762298051324659364025972380288099488185685419015843320373574509126615021765562149708596 901759620001384278625116905873305108144542792134879080004017393617899232152609144981342279257094323649605368258 508889898692492452475361082875427987029465462300377953268524842412292797710372398072276681351358513296434849020 203835631964155737935919709259563823057364818352317565289524182483969251257866476206392738998128237207366917700 762631500001821940186438491848498183008729702074724176454135439996046318127247480022098019839192655933866738283 076781057584049692962510944369270918326873821959750972277037366818635610504010318466357396544567253116979739476 436677716973737965291711091677108538329938157403835106688820420801543209650912065369920893596291978078001863271 427167749754267661607276869066943147809163662151750531837335210617309278059946840859502176123009989235369416799 057109140459362360119575236372677453785524141630875621501364616861470749867996002214462123172683726244876216529 724755636686987529221954113901118692554484394007543727910788619913585577571397764401974012747603436807242055903 204255724156048225771840484697107162466026272535920325633572282861050207700672395463010635284558134099911580095 574225374010174279190445087268581173994912229417738066755981725323614910618530041483606043564720236047751462076 307919776692393272672040295868275890347749045457505973988841874429806833114556598411134533811566008607928817141 809390902651588457571655319557514871956564137656562675414648558757492512064862163431190353435193278602372789967 585524103516337697699325001059885628079456142329038663473620429086863249031005351343671198142509689955277613501 498886333310105184405057304605787697139777738389919864275002845440829502337272865492756802444731571042102555207 459988880193628362518009844019459711691441195816313344373880327875872625783279259322692931060647296794677076602 627411761770180436328354122546129759532591165612448878837181265049261823614926733527697530465664043817220580912 744960853087718541670279039580730538053528363114785439672561438816329228633020544842608610487574318803361699873 371727410196048083912322050202857422051620983838497156631070778579374879019067272014830807733116744811618393984 035001664705719390768952284935519160558676333491748660209947461993717554356043134643987895239708324529779580821 578160350625721396440631900671793521133231362143416289338699223559900042081525084573114585495910139460075573126 032887460004839633087901119703310304121822098919102690089519025390206330258350991752124833440674040966456603689 220529096521869832352527587951690206553622223792888499439961397012937498077218767145916387892909199761819557243 839707241081314424603576343792377937763009307204175756018604250415685710796652020330248412459180024025030439308 038339572788131052121428047434978347820963593139400069430126628446883851046718815329759370612708440621818418651 888197997601359125233136199144315446711744688172523866555723453792535481258403439451980347960227861332099082112 967608242389064622150457756576189425329734650829965862392041664679793230409106507876714163135829886516140531813 515928405043765045032008774691371937582259496074917307621799493434030925125111252775430246585535861203552023051 468287932140612166545886429248956271490029794006195122939675756274002973562904538316716072709479138664306164705 904536321751479101482295852466252522329626257518745695283120318819515899343779255794838116218565140987981526646 058702119501954940576116672707623696008059380973041176712250742583223130615757192796859644047656896340621561199 893337048814486434029043092466471715027553873495797542068522565996489205375413576442481226074438321290330836881 979954711151957594444123344847439950159112252376077784100479071332678720086128717862031349654586880885237536279 991467996304082690055930321437933208123862365968614535311475643605356615107635220738703526271648564605061972153 989928370851389094594748294120965041310722969110391082948712555551492779526333795705190465697829898094895551432 561860149971969265411491663466167139300499847232675978561018356753377161439052705851388897840053822207925655890 145136185094507860577334003507768451305527603953886225324662408459738318562379249696792199053281929981350631899 402926476679159472629244317577896718170182147748025074767003827854424339310768035661375165550959985179817934737 139942935752267524076766153397635043087929464009729067294894645843170659205918316521781368860948772646700671501 008510034159110915889564664408024683737622619218905657242730613187413276840696990854811372080643977943903360837 991595391659718565840117816499499748443655878602466634461531502648108642107951634194712930347602852172285874400 870053264354885777098049773844351022697657179124854447746835035838535035157026398624420159168454979907531165710 625986942524989623185330991325550160045508291703420882608021561286160514221040765142945120320062928465334708833 188180605336254006123566038095722122419500174043610312277937675616570000198901626983989312655899635336283898490 808077121923335264594524971694727641335938539779556091412766609835579360587832072377299351115100642836048915881 641652041608502839556070811156773133049660915913074898033815257569148353681192030993296395125440584812189095948 908449518516191081471481490630774204151284363673320464849073053157673757552805602221762008772298585930393536046 380309148303185388133927420682196698580384296849563941397262631406910969981079351944130876766054731352149518040 469991183626341272218135048411745151305604701384568915280331446093623520417044256645644600355315214406433903363 967875261611328696840866426238274897521506282509215777439820556672451167267643955355301006514696696099893824311 376354159676508463030580088363601437450327336142336429993060694096918555907532985062676738649981234621927617397 913625695194311691425465496500520712920115686535413356404547032008580215197154449243132911831924884492235300117 479850815935269050737442976420880328466251802007380999831387903679290382350582270264945947130048361416623714581 497410942605888170978829446955694546938067329354299833411336301264712644215784334677345793796172711090466039371 193443829972168271311294565391819630963987592479154602749736885341118977223982296611732340042142524746021836944 762092823337921338524721996917298827094321093450273297520655365454388886341794812421086979623978968841394637710 254478608292891271191097595526062005672417119557395393736004078685333373614853411502071168703604710234786835555 188015439712715267681602538466691349161948048492898053087720753109926233298514830410821146493423299476052313150 945529664821092294890884507689416603092957239083690254276217936306181743633066825643454591326409228425770438587 796022089190406729471942892567117054769068460996027534190726240327641927608925641945478712795343577198589307676 492353576046425415402273015730178428007327023780619975347552185773424113285619284680615131792809866419823785034 203334382616562148328195307496262271672250165698031825636339295779561340168158054779971287870545750154498005921 667990373628938504826826776475731098217920151674666543648266225337343011435660418988675025911998749580804673751 701813632973140003362241038477012561626579918992155146598333706305670698711219673639862655690845624785951540152 800266042636964742834131545842770987045562850924779518382025143278756003467378829890984498054942131146243092614 521236849669783489342871144580512435577626676794687821427988095170897170993085891406118304519702453156856774376 258757990717060136725044339958696420634313413750473200406188465899977815939621841791845250104663345519435981879 367576967364550550371023930146443294671252397348076309609855765321256814574613286025936174030061198416733277541 209519327667283015429426546533087991355639256576298264796646858433188576891384004009340574432648643361937980269 721381748386807952805819484977539812988956311678727102862965543515332342923253231526282579131170286463525434483 582559805783613538960093145760824880480093014335941970727815189180822821031910596161172937526934390318186350020 694657035303045631475163563231948497445380790912508321176012027380834659925016688601782575334247118161063417332 998353935625213611264308576702030120109027939556107547285381172380978559374433193556912989341259869954010523467 423223187610565022497514461523033932567899003166756715341610157731397466720154896764474909163417748170185184979 5081340636068891459743669065462666453079642733543424