README.md

This gist is just me messing around with the Miller-Rabin primality test (and others) to try to optimize my implementation of it in Haskell and other languages.

LucasLehmer.hs

{-
 - LucasLehmer
 -
 - An implementation of the Lucas-Lehmer primality test for prime numbers of
 - the form p = 2^k - 1 (Mersenne primes).
 -
 - (c) 2013 Max Thom Stahl. Released under the MIT public license.
 -}

module LucasLehmer where

(!!!) :: Integral t => [a] -> t -> a
(x:_) !!! 0 = x
(_:xs) !!! k | k > 0 = xs !!! (k - 1)
             | otherwise = error "(!!!): Invalid negative index"
[] !!! _ = error "(!!!): Invalid empty list"

{-
 - mprime i
 -
 - Returns true if 2^i-1 is prime, false otherwise.
 -}

mprime :: Integral t => t -> Bool
mprime i =
  let m' = (2^i) - 1
      s 0 acc = acc
      s k acc = s (k - 1) (((acc * acc) - 2) `mod` m')
  in s (i - 2) 4 == 0

Makefile

OBJ=mersenne
GHCOPTS=-O3 -threaded -rtsopts -with-rtsopts=-N

all:
	ghc $(GHCOPTS) --make $(OBJ)

clean:
	rm *.o *.hi $(OBJ)

mersenne.hs

{-
 - mersenne
 - A simple command-line app for finding the Nth Mersenne prime number.
 -}

module Main where

import Control.Parallel
import Control.Parallel.Strategies
import Data.Maybe

import System.Environment

import LucasLehmer (mprime)

parFilter :: (a -> Bool) -> [a] -> [a] 
parFilter f = catMaybes . runEval  
                        . parBuffer 4096 rpar 
                        . map (\n -> if f n 
                                     then Just n 
                                     else Nothing) 

mersennes :: [Integer]
mersennes = map (+(-1)) $ iterate (*2) 1

mersenne_13 :: Integer
mersenne_13 = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
mersenne_14 :: Integer
mersenne_14 = 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127
-- Mersenne_14 is M(606)

--------------------------------------------------------------------------------

main :: IO ()

-- main = do print $ mprime 756838

main = do args <- getArgs
          let idx = (read (args !! 0))::Int
          -- mapM_ print $ take idx $ [(p, (2^p)-1) | p <- [3..], mprime p]
          mapM_ print $ take idx $ parFilter (mprime . fst) [(p, (2^p)-1) | p <- [3..]]
-- main = do mapM_ print $ take 32 $ [(p, (2^p)-1) | p <- [3..], mprime p]

MersenneThirtyTwo.hs

{-
 - MersenneThirtyTwo
 -
 - The 32nd Mersenne prime number.
 -}

module MersenneThirtyTwo where

mersenne32 :: Integer
mersenne32 = read "174135906820087097325163599245903327890779363690507030974654735538382721562066257631914797436422461610635130071368293660728159709054586772369049491142934772020896204050242188730034975677375975566408927899798507256190573103216371084706946529168988544530722380248547797941846968948877581472117196096521071301381477836555367567435899209675340655120074292036068123909409545431263090578167973446135882135220353524610720279709899877492086995072413691418815603208368185472912477598626046460960216257228388273893989189010461721931215554593257013799532456881185759966782043075143856381987226504677899075388614684059162796035611746273011187409173317780614397122325261492282373592588003879833504786032050864626066228106030298325285057443402167635765093406904801961800958032801840943252236944301654241328887972576597707801510746342033942261015696668033710931641854487286547810910997434248254117348626588963519580711982025834040830678398929492562678723328945274392069545197412239812277232640117442403915001592093787068453272796560830989864220128391868730035161189797333281051847717593738876261385453234335044055796872814771905608221838870100439877558870228742946530418575051799454296988244539725771476245577990875683118405325645424047983821420881056115848406768227013580480392581458225591719450118008340208791090201151741341480787794203353945535671236405974185773415305334373759286447268320946175768253446891335509519519361102106163922477440367684026804263792288384560259241858113553094413619389142622037784908890117491192874288213169263869789887820537599459612625739008254993809407626567390972668022569995131162133247049224144525578564980920446543691294374503324572842465207067844604002571137305630489676392230606204286990929670922730314552656991567467009332267114372195108256757884528720656782904755249884754650292415434416630210390638571925862951579482522360253035068928063952376713069899293452903710632863819872944691163805472049670778684198151100849663338987231814740959551466575784026730919422868593691012152301553613340256363984393967605676993856363845875950692542435479710475001640347820999348297477230564918277093980455192569666250153131737817696267702037728710102958667196121610908920430770780420591688644002327481890007644122190276903816169772117848784752156155927488008678623532904792799633652727754879966107481444210379954993635080980267918153473740456829727455985991703972913190899208766852416348400984486132002171490894644769925424403258258179953935132629619911559620308668693326518042454926510832158990500081881155869516585961458918527331316370465948417645520611856386918692883642238808324130279311595349076447894599901233759167645461049111919521598682849205163096876491461848666037174669533644881638272799841293063760519731808850990032658918347038655071059993548201385258976126404237300768119251483875652844785087824903684221672830387932398283314684330099066466608055464842080360020160109250443012277157375867202617478727780813028418341392074698081047308545669968591961224243953307203190906497059504393480557082110886792259161916958629562454278490817105976280970629271744169261939958690338413852377624096932228957836288262796062126862203560238519276997388468059295238185373317430933900518633188308455565174877782416812385102762556890496578434192757390828601299179109834538314755218032073643604599244352222507759693720465687293083969816786980305113743150726842306474038003823939132997287003932828859744581717268565498928749111889374076365982841800609570116403028678191521108440460005482412372263968633927432036000376058105442099334248606232920863395476255107589899763183411184551495078223977254659567972614623218692755349565832492687439635634931272265319334569566560529877805738171055717819409675191354318795111858836088771756010318122065917686144659162822738613758156433543955025757789142117756438996941549250768329299468855492744776389067964349160831284240132347236126184847487944192468959209840246918771479737046205523359886632828070006439508208089102383304593915940805255747294457355805128580194508515695985243384209438522895589148347342700085209810630359475434851249720229267236843131865829904428362141143503073475910960937240547175055948303424164135207809922574912574265790558879608159257841262802834590712953754667695455161911727548057122224818463064317123696991586938046030489194734669565825967761249162775329070015399015587985686494124424812899972104922860518233628384733380887492313495233136915618797917065239261051691395518623470740796450077487372255742280082298361340312781849646957138767879461645875748692330479906948450685446558375250119843903847373206716238967442800033788725928234527829303820563981919656508497518720699451593446559040641708664784373738219856564167025699650381281188307083461979894863378242251016204189666715910485323188935042587816886173327144926883050227877426981763094285766789941906177214492011263790462991278083112462843221326672403498677618847624264797277274572848555495207589488702882068407064119196694058709012789858378352193836252951508376441691927396956321922116497998360438191530965466815220281497880333134466408893534133996974743394091487867368394005947484447988895208904900501431041607545505740299722860299751087795558251567126627558529136588620425410911310374697832345874094399752713808974559290050985628603873312802653130820152436872105240702976056373846476014946912470597496441301450916486333634806008220148832466447814494009556050633526463562517017576078940680685353604938816600582510676436410833578154445838869813115279705662291019110800264544320833189463329797536232268388092488059536304704304552006557460145500287694088499796893665151068036210952927336738794147966259190230008386505090990399615320786433571424775468662645142104909461782584067707135782348921315151579730351986447930612623956437055088353331857258762109583076020850415740158493698433217415415321126620043259782093305884153987374189423274165492382460171659991958112304434178134352569230569094915726455777408431173201519286329065612846049328505352359557181166963613189083370400768660922082356395895014203256752425271221620332958129066801918946598643336937730672380206116153044984232956485874412213059150249402785961381536422971410632799100781115664447463791473516193364429186554879563311700750248514611845339453991914400602109723967378765396433815964517844796010997178179601323114972385211271814400379913628598932094488946215607561225399698683494159296656409390539111498490108942322367694583738185909424662749291583394731724194129058839146651398712263894220514546247541048468542819999802360514988601889646980276803906603387238617823987605885159421957357731562731394268140100322260722959080889559605001977747798296414362013481162166114604334871936078926892907315079984891601943495727802090598435669777824664855373495367555712103233069456808609777348064854534606233251550484622828119676571290944739889523766039835353483746513324353293608410645277244613619322028881522197357827682120803559242618739113297204454066307831300500799700719870946749682480164639441609113212708163727073308539120448882171395433603574210763682247932660379891534854376766253684407240250107653813074813621985378873473206136126672502963340665892411117478429454971579930648925004835216890913639662831411857711454238896963979276862124078781834156681770396574541587621867700948818088052854341627649821605349800262846595680397664575073271535577146725664729034142388608219320863413167674410896194802237554263865744665193505918252241998546279041040371709576770915181148171240501134233554803351093780395354815318030514667575013423922641697399351780741304504024815942152667132773264971604896911927122027547946484905940691418499100984186874427885689248206431778904064603687454347753833983781265942565765056838620930679661116644331038576810412563279169099590997219825668661762173580572735848293313446333531124564222081886259991395553174278858001526296807748056335953460985622245382230883055504330520924319318948293043024895294973701653196947046757782411791889996774915484505489195413789601555735267737212094646424118181445877647069118447713006797368081471066219231885451567343782694076071886468623279987295171130354555963884302232758848156987103303789812296775370910831296019548363971591310962510226270723728036925160452988920698495041753903991552435223540426365815856774415746521291286271741205279395641645962973701536911280047492314478837717573071509534213691035140738697600688722771034862292974912491599704322941229370961751527036881766952557212026704456724225215258949256171825827737451355258801935088695999793329274948595155009205569097809470994393303682896833034508983937760851583628606991657107348675591067331036540032277319295372658322612772046086947496652324517654565767122007535180362543707068021901458730599329058045325618406843101081629125122577077959724256701589163245673441460697030868531643546284721762291406586490241916613631545732360558843790287900852243372991145382006114262552711841831695851614719281288310263297376663492266491339612485467953281059602677084381362266900625331752861893187761669775998334193934730057544851291508247124671785217538490988369411329438675141401017729632007416794876539532897276667298173492323624028246265091556738204203913175539071072638259886318930023804950492268174484948763671782292921073234906398138195312058352303885180876107764096542469571395535087945169421603431885425325323288730068761271733687601533422264955549878064524233608793792924912299252970298449617203427574585116470763503201496740575984916416906796052515617004016570929866352662706120854560896064108889747274403016439587582612222507956096981564361892702235527757729750912004059993436871145494791025780920099333085749893098651674616977614375471431861405177090681350677451079775258819843725427245957112000205194332167293374539691471387512961522491479890502435471002652761459110956586934909788278509833343320682969859863865097343766630045249742098180164053450114197701140456355670975243264721632136619633471896051730937139793604539287395072320808992706768193387134050970861260689619983218833888101926038049633575229006858432625936962120314854473926685202771898591350384234464605904040132389618105357437372718732462419851941302118216578249232493010438183893606339492171813557590574355249802656449517146003506845899751928043921424995489873588150455075875681095147504384981820315269999644366807981182684081709703980776283054656432638309369848538079393965047803107711411592733941780612572485191278504921183780497124178949186246852551788130651866626344142902474132363147626628808228778356867961421193400231390136149506277371607111076581881843195226586428628878403522810581667893846145671748407468465953111220069300460063863903793768364370122747663340758124193709135711856825346423473965175647200394205047233415890084483818588664373373215783610477703627539462744966975584323471135673841055111585232106567447466808869385982147212447702627450784056047024172932222241835545800410731806912695662560610203359553263900722350736194999612330932211709439694921767446216430779590805544444278260318025857624910780451985554766831672800859776331004939329142702743198439450296821029264988926044353616603013445147589359953203880711892132261878585652063811117928248162106835516131694382789631852309412892227234398932731889398490279003800838544109232983548538163916868302997918272417161599555149352044836531288277476873835216465688801000866726103216548694798336129196884482710214369493055238823852566270622725654182497621610150207005477418336685074042476178155150329030952066992933817208299011479637133090268872481399121753763773508127732099528485179088749924750755685707573231950553852940480193768246783452693391489363153583594041293657983549717178851570303236229795370424245520323872223030632391123776544646863165328791181884505515532569249848682649945047818009777490145328146666682822588831781144289885810747515293653359565514320499111939036351373160295203176693015106776425793220912566493871465869116331274004880217701043388482627254932031147898295702301012199040097237844885051567072390884611199639410809467743299840091464324509712801461491986837781470515883985996403487460695340685356978432585616497905138282572242651526166753061881369549563339070451794784391144747198558214730487376291328328649759289575073122250844337195572823213610869832276212439631736305585713864826871323400848216720297739984995640832084491353820616586470333770931502659516716406956953010965324183961171653755346412884525365386395494323169569722771926869315483843753857142764059448452331453617541644136788676902613793048532662725161171843374539636315658546060673718827996566071079674842215318742161208858780398578835108325015176366387303873122643431593167722607449750166422318048066744021022857342776064386729362825834471892498016662714184136152361864877487402695707097029525386870830745209536323599387948858557186870448475908351418227524519557021553078973822917373940130552867497105238765035234838326524852803271416155364539233912806404099316927768488169540283197384308980769908021110067617025592915122205503069083007364907645254590250150469312231987846828125620807938654307654441827986700131777748339134445890474396487204013483945819881160894885651058114796133029158334716825112438267048522935357621541762850556235836639341058072749793643206879461830312691614728919291180312747972166917343167930082927541333253738200296826264495509072294227226137266392434314382892780306139574419994828093004621105778925132525689068051930469386713819890552369716349642883861196354798648054484688001880096225675032723013521742448066290393242089626937959156839552871092152715592606692174587749469471218306343386396396491752778085391802099734224702263152008692265427675129825057684136848563061715843040314819759381574668043065841283758239594318884185243537464719948575429160259489920004241919881712382286807626770836456681787422642591745400460073325942703925611159896526446609149369335492073113266480156033789959177986978340196997230321710253635140055191796317053750073275339433184908849444673777669228820968556919061122478125057529017068630377039125669157026808197417375025565878686626307331831171035813025254667907909428644351918623122268700991069944682758262696787918833716189833503246893576735762173930008435644240840778829626612732702141922426780008537665182156942062766679958703295881618190934237995481612240931142074501019540265235090740773927558304888826668271514307655179886417354138107141940332624066994324266831933012442335564574463033774463924691839926779726458341423770927014567706290542756727078182077908195898096672077617108427516778482328699045752580272888438765608902962705977894582146940290123905729576564060879971208977532036838931602532788801552473555437924474542209673362910945367497803397429146371920975351839477107870731672020699393437309655561686037732486877666823533521673867592625881378528042697445508457376103914798945969252139715114719988023347231922082578975607467998086529496090171689273020549809484268188845199416203697452008970628130943270012386713665550067377307228738222406213680965218671072112745452851479346239053207419386981367584969710172087483798281636581931892202723855230194311036746007078377442730840440713860175912468737515118854463913456235902818821833559937177299366365776531367629275514824373006445607689286691148147539053263659458273105479000742092904065540212670547532315759970046652087062291078638239606273602748169550084587099055231015638533405053611073698142151297497685652073936757962849191157153434540481308943713334429135529801258869399531482132731858363163510720945675323827167371183400534542803305385060254358170741915126261062018104299345084974960119417982104965346597589714855220223410978648810910182719858476673811826655628598649343700534311437221058022158521650926439500742979047244218161112210570127475169152928216201213878704224608837893647626362403338075637292682230701550310866944166894275605780054176407567695184457995030122714223920258642102527743150297926084391578674518355394002159318007479060270647764738174874545772589179317170809251988273648653655520893217692751193418764679127877875323246483894461970518961829149121876597941484178860270299409516787394614319694700294256866741526248326239739043876220889687323011457634194800176804484857023454220485752977589162882471193419729334156210019183081162752406349825290292070726560887683616776286558899881674038080609631319126722859514074365997075641805527912674489718289584960569017397477706758703610943558016718761169443385509795110363392989480972190121641402584079226541384577866097273488708559863652056350817290404546827235481892301977840142783289304152943100628539194263512984837306502303928797011969469032077292375633504600139455638243770001142150181556406794349053636772524937871649964453885175250348730429518511756253910084697219044511677779256635001547207232050718847150220183658027394844179161731125628920370390878982662454869962734480677886790968479042381324170407792795460055794544564053150715029245223952441485528385992581376391518402488400247866604948550840197812461216728867182030540116087735536330510059857974200519399489865662420606436254842399877006431269396132605913289551083965106866989546737498132155176238524959990212728593685889087733790389989109680545214227745256855958524839325216181820679259038299356199683769951078650057187849171394183710809961193031641890967092958686973901511946398227977343741167640350860143036353877316029759067975967383250151711480492820203310663063353429556560752603255121899702918208344082788845253953919108465612894744729111320619934674630008424822827276368053603152686719827841665589770698407906050487299884026441097734471507336773170352576968754883616593970749321307810912302198164800284738474923134592879316492154839670097160950969957167025741992508135427354032992530856759251427076927050392295866741288294468916716001644263208112667200466703843747442677362329708327111928258476049619255164589979307372685465646827238537868932950594950864274741048924513619529182598137539953387807857508219835388432472069820802553447898081798708270195867316886187451036018835308794644893250791373475756880938451351334117856415986492763256309561748070631795715696812004811265590945130727633939523113571634575368565185838620044814570742204545842306219989281579527362387166451727678009578510430581462849648557873469138229448553677185187505103453151127483113572876334826650129664564070666963670682324212222870576813433576235306069133874620378627754456879688770589421744744629544777201041352511008098328901218260974479640053288786084103922601746893621815228685015800383231521871653231535057620108073013387911095672051383106748712025494503087982966986372168837118347487709405402305917014491142643355936072810323954940616256493040066103651403941943827968746705089735926748947245589223175526446418851066550192216654962344479699172185724312159339080309034521867419069990505294403140535980571301802839628078821336117036351000742917096831009551310686905994769793684844207417365074948051604221201240589109894273760222671550072293624038708170161389944169232099966109682151408433170605803228253459827818560393885593340004665626337651171640188951562856940141582490922573649880552889394279961276906660081153996854461041358669209857671124200192911195559310703313654885723690616704019215461982935176950653860973914743100174881928913913639473142077751064800222961861683603664758716969344146407543464049675301247787875706485918801298508740473995579466609535043551635744244704391680744628147954819362875255789280636583930777011560844726232211168509458990827083252241337752329609467914697869949615878070139220643584166531546996075268835672768594423287009780833925576833650766172222147800893337212495284238477501728534820574090158349700430625475309531050577620016695751437831220082179065213031634230149899780298056577421719494824975623031254714433838609198371321846582971270252025786697776588046643654995839301791802426009654636720467853616898862000136802385863025240978498349642812256220726725095597312471066571848181767626249592693816993169243527334204810610897027017833946796510570286644179945836948074277211781917672666738375744947830658382150492652348787591683446574619832032625740650370652057458528051701138145579274706759770230411248711357815818953540742112290576434946218759649953934883587834233639172009956818791351646999920507745223395351243723647041133039878320886618972513014286203115000767282446301367052872120908437803266561742854820721343505472508257520580514522774024094151718527084522355843499560497771266974818002220424397467124068343373800739639162771417532638059559824690092556527160136085080356144183990679059007953939534615525449446373583139217304165560542638131255091923302739014509035519968204420941324690585852482595455677176745354705467371644157548431507236951421282933651216134279008532049426259871234288440100267867176012793629397504130163556674694410967239838220299296296662668454429847741238265208457456201744722805909610999666184738805615318778582231400157179589235833501863550759757890338438997267382377819451701291764986064984547593087750979891288044090194253844048766876936045977899023006613956336644424468811781758851068227003689125761221226220541676719782660830520774484079321879360676124847817784344443379195842566315780171168007716833858732687456553128519108756220173073198950854952388174627390317136660290771524197468794395934132454516471151265187511788126872355000484387952397394685488712450490961477570259726619175539060651163125004624425278642697564174959457095987736284321730373257309411477570630443761585518074849335354832834482316583892384181125378396553028085405618271604730121649279518072272999863362984101373150670153922794890491468032672431902585983667805019250433227936586298186208395911987086115746732600008205419763475905294351250696952029106591914308245670306571824274787619678597824573923438983199279734379304173460722129779387973646816730456443829553031714480030963401990526522304164196658081410351300735521679884517531928697603002658128739407329466796152318123126649392759587637031700247614242628689203233469456998411375347631322155039840414017441117868076445226126357911405298116516252511373397712011332296531127725609104493704005176620993274140106480487799686523256596770159270189223109961538576513346628332892850107607809837536996444699050162839199270999706905904675771841935452847173949997566216976586321526494100402662466606678251917591095009461428462894160490291826159742227956326955713721560113749469275530469301085106951071362713832353147773185392866295521265971896241700559845332562678566511719366681391601283242719294239819517125351521725260069203221228679069875495918031409363734487953316329755829418525312614010684888186723372188264439334428799786190238399309937895847328128627729131740670739185692979521013528986587009428560747511748067893642143895280146038569981786560528064637519866405739600173277640655592728826273647707025804550390272532784123578856233066794557002641279279610141683417323318326159651716625641466392537135125401853388448441635465746844859589101187622303573088745840698734555251692996996563223690822002800820387177498268079267143090607253742978467979225092661999654622781247152399417708065754380040245888354324392934621571776011726239217376300794174342859867381301853575928546699838563235198112449502258179495537906185681809494195148998861334378174510481893063175127777133846193067237702429621967033947260299015307886673010453782170889479380327089441169650324742950742537652160297025467615697283779394939631413739973237960351978099560786242413017841187478462757604010514821178588364635015296586301222536106308500169077089101267174570418075535148942201233826353521002124604456405370154375048911264955084635972234104930157018957693243295499166697526503298614009001585969506076101046802103062023258212492244768404284488162326542550884167159815044342310696502059442880992141942154044284676583723912725384120684941244909703480707596893492558881742198579337753688722872788717379162512254249790682824366838850347911289580350021513064027087308299180798912999961103345723592207698967402502132095743987335959044986632079852880730959694780635106447326863491871412854137591033633529562288043919608114213246831609830503999129478596048347982345816116728596150538509587958182794302760117680970715798484392013362194215967697077481746319947033585516626070319000419642594209990932930984822958494387642914129172473298082216812344888729098495237469709118902008223285813708689260428595822562536076652617500099360449450268688445569867350067813648023779328851004514243017762747562793648936931142244419679990808872739753774868124729911078716791151916641345547568254056583979328539025648112602840536132590546985285230808187743035971361353571290946576008663936141700680790030429916276234601327309882874293685804358317413143523490891100451248772343192069570368870199743178576015803619583424575862020905663063349445955974717748198221754651713890106704645191591198132841632083748578294479411433141311740794912952554784596460124624105555960252225183784781291211764330925193959876192908257856142317619931600642575797443551794185920922305286829946091451402094334190219591965965465487926956680751251137278508082769940208715800082585927058897837625168366259136521208992459546530310282537455795020569642572408713623381956078248524879428858370531228929286635034123256629282800387931635534849755087971770914364182419888126051622967345546215687114176864205949500261573911213379108977271133615418795672580812207627233178839841343883622884550712075189920422918425212365304433870702847436663915075675603860708342609683293997713262897114019100116684226636504761861895572145398386651778601801226378355923734189202704995308694026086837068295980037300484360204526284952501430455220389100044139531059476227937399967539790889646394459952489928947734826043840142892204390815520666753573721219792051857500231151505330895945591118166674455486516325864697453145363207670238265842889645701973725149147911006610847826404951372686501216266533376434115033145117306933576007801629221851708618243797518357651399284372978775470882680348680344989500240908169348031452655966819906924318954608037176144218106586083989140642254886884709511474672667203986392792654593432897197197405150204673677506652266741413375872786382086609274537630143351158022100669595078424983221895268767410192640995298876519243892059117086626782530692027501704132533482925029094883526988209286706660738235676219292942295484879654881326142329824277893276674341696184410819384980611699070306020300346007555431358462898576422694141757291999669095002654330714346238751373822811383590229958222730057611551173660432557388288314284329175931860804486920912292654075291629431331582425949739174893295329804553829662004867898643450296831078573215585455013373347229631799126430571594956610089900439302595401341793773265192018626621753709308321152182958139173799256761495478476371720654271574995307219487554360958698748881450070607574656249161842100223826407280073173656444402166735279167323618139926043014531508764690871792111625100858472209035682189667347522078308200911071704692050145829781314781472387598311181853967653409637988831678348510981840520932290733524453156007240780577121988393900034821841412332049853773097059992554355088026262073839770735937052169980142447013667155318106975371659732759571451072475933628717325651748414536827537398778229334970260084789896191443677308785710982165258161451627578368048702532693519374396812438706894559186592808168769434879449946901201198657781119590764632759476430296868269582636231008526802094189330463155903791109994650124916792678005908517157955903418160625080795595267190536688972528620450938026913177804333530916849681827077748417284579208675216673672690190109255564764517313652843040968781574620330437838697079923936356547957904618288197235297360621403757783373774919450211834360634848778406142732400072056946132632894980132968153650293427431373481995600032175347834835108017907116892453778010879027996921185320840492205563068857577981275236328785027155306906216050594369262211955556683407347725668798509292301200948233828942389931970460662797417773763479547598776945719781719170841684658880491805547774547298306200865481950256339022618832549934531951002194872344382970669900149286815022061169903868149403357842960364806308906068633061242896625369923228080897514532526632356392894153405234910662262218534499620118817848225429550714048684747756609388642182657564638490689117191494894184275719831460309205735226389724006402471042726847691708675089170209356016799323152519112519752936380159967282008408663739891922332913564812022318265342957908795565602582644049692509728879843304636357168778280072594772202014722665301999837295093698662796391772417895020818699599009253555905947900423173220956882828979544981661816240433493843443821156383152626122028469197104335769232037241711491803277932474862208606424432045511751815508260942924035296193523148218892531567264666562662135416529523375613215332548213334249263809244639293281788019194770273119896497715122482883133751391047796662038612489390667376202355131269780607720167670252422511585724111078270303742553446623005850466973451904021991088054398958405631688273202402910268811902016846103434580869188762304219674668711975927177608776299897018060761078797078257797727012095725991225844219646820767150166122743422652357482541963939537434160150859194685549806777871624465995094230463697696436191149130937289699423989009855813486733469915510811596063285567063074738462064464800201990592212141816726945522678845303660324635749385759210824144645055850740525918333829623546324688958449142918781564307769323346448309245383969103379233255192399025402956187751200595065432505382417901299705111579730028250603712072774163066470010407589411988121161888846158213436148799135092286092514602275719589592376465182496864264234352759275435170491812064535026929157721234853868883758313060235117306312450526249033557001781547562891026938117450941642209476732581776725224665301721469201999398158212617033223442569998433247324140462130505774359223728394774170975445810025177144862934210824622727627569685905155608887400856952686232761416960754488492406628128964285349265309294390272356544651679071640217264665498039377569824652937803720785568868198878423629775174621676023585595100680580931233233092053349861743487635654012574745217536912151688167018015542677653932184115511514896068413169856651219016665217390932926907723492488049352497895904959642759322909255331593438584045641165375520937104377256589794762333952885097476772311179611600526102421196313639783238297585944823801886626337351474104638560843503625216537158442392216909242327301984745166948410829154111130560419329405712164393745456232021753457375469534182995029714076145546330474681053555092778511754771917568122330635764065806018911004692806365830782430375726699089468381113539835373239724342362955631457270221674749785974563927628856168376461782295404209602691073531727848184068957718964636371310073903973008507298458637926506558575463023208334267435555965193806627958662616560673810345910778902820318476652726894712659196891070928486701236877340373288941871178629526710060509379504268564686381753015982484666216272222046949117766374048391807131800342998476017010535837102719117197826222548737977023144774982721990072894569625325939322226000974750043817846911759547292932898611258206751136246587952640808464708454411484768222126429695207394438778409646540412895063477065726518282032429877173516701257848720976125221666935602618830296063211035559730972919536159302981296738202580887346845246054220111721382570705353174452092520461381512101013946579733892678081425190623147812441128604823685374912316373282433907681575891582621392868860600192189601290947392589006263588665229986987869029723106371919257390926079582702321710760470755997643054947812655536120135560417618278031083713852388195918597388401306967685528067224072090646140172813857114796283046520166641015457569671854737631756348349450028929203802456747068607362175724614560919338996294066577560626273508209636796988880098838075587422859534376792637759504041993579788421763984719386433344484269384494164266193043763229193785594383325410720019117297330569223237764800363835128712771888750970286784762231449249857090454741951860284281910573905921884722082693793665796226213772892134456592143105929251804970030487881952886961235758593265998147186298282309699904036497010976411361263201043974141295066658636493693626097244053439196043503055720585878349189114438731864943297538851066886757786255340401397959728037442025830871592983679859456953980007871584109996319278009261005875774425522781637536625303930061218335347389271325996002080493421984858331366117045554827314618469539992102732522822105679044242461443858938487143856145473118397240247951862025196049605020271774700424666970556539196774015475527964404549404058684172430707570815401750846730753311594521316635206896832137935737540530150154823773978199457516856253982205328588439684733610383192085628909570080207553387370457563377095080303819718041239514451967914256970699669505235944321902856840813117984102413294882096524009386033978500506502596956203553689198060259982305961911932961475978318699293038562736825222860715676583919651291843444496406368520132463267852708468503523261207743965375684293248224953539135433802983203180799169876797636511411886818886435111877621818925832344166046591176782714867429956540257752807540807881912745969107898829210896983970186979850072408704934730143728536466132455261218308058027046914530192190667014493837860546075929819387599882761619913222115469822743842895983477882777715756686823230676905074897483155716789283225909097366593656150288150955093098751500089799745979168223570236294671175211499650518215918017527497049542925662484320993926230728700229696290662985062346826758738410396018742456064229131642472761639887250092288126650284593326931135084471560627882830884035945911228272118489470926989938928601794872734587174270347990131894448598648874965961154446519713349115703817301796978281921843828531144724045340360285437663808941403925728217554801136619921334048975083822799586111928746475161949424392037096108058980659021417331806047374668887221913222884212988151281247574845213925829649832784790846870424561406518115830173548503953342996689897789595911859000452117296118733297862721210839646703485298385423475545859763208611863434441115798874981382318788732618752450793719553806163927027969626368354589858538496614047508199505989278525078323101765060344613317634540217211866084473497743685944965197893470856192728468350178483360786657553913343372531566298775528924558126532946470942218183716146524922884946895111915488917046600507926291983608413769948861492817907873751230623856229544316794207237192005514561890106087179817840501796833681430717473476823625952794539739165986825547603464486382590970734429489553415405280386707298895781959594847919338352242401491666008366962049583081984904196151158995585223306384225684534650500817526199704068211829827784015943502431851168302405930972662848543913444463381429446281293142639059937829233432443616950798689664405414396503463393639292071964127106638922653898661699697991610906575370480618024713934334463774342941334426779785094044989114448037051574732875366266423686679426348305108590842470831416103993680861572870112141888673207215669376346645744729128422033822514207311263797960571362711727427641257739949153017409148297241727802383448998055715445041997776326208293815385396524996361270286604259391168161580643746217078375718032916369332883868734023822944400012637979926417254402420336566890932568357186213560574367225096385303241974471117684341700450599917496369700973420985693659287999362699848100164344434946559470120280254613063344087999015116451196734689410702649277093664112290523929579342217229860307609523839705857357437533287382759014178731824807114805162788914943194342337238438182379410292072348377979621907453057538776715814796539721023937682731084351654690285110518455570735783067230790912965426274269210255405925933728952767559792240190420392927710776840565090208015724451428895953885544103800139950088685910548912265584833024782074074778274219647468210409449642442363017157617246423320400618425775550117754148148543291366479329428985370089909217472650880627136885742092087718494078031698772712500767719247247865375805065943278946186514383898623583010219485868749992437275899215136748693637077620215352528338395915349190585150732741228284609416681249106516676716560004937788027045521707515009183064401178019961236059744215338613556909865986840306378702487619187600292700396937066850392345709257259915733159236171087953158598811687143932845365594805070706283364439740354295068466702858555710881574807220203290922900970130082931285348413216064744233633312142242130608035634641285748023518591256687076985688223780962831930663538206110176757952682289618655884441247710313456042409491594161054047771429051657543314234566401802464932180059822161133974235666643778381485992090536995529013111161510726498927861429939967655562887066387852545399090672859075447997257601331010042422808723878735871205784613064235082910779607695319475157085639989723883603545989864515251399955938622866574950591358474937912115331053205893722686719793741330120002466558204931600240421772609278611896438256519658089479910290536087905900957054370070466604301049445062806572511072527325865731194462511820358910817628296252550655098972889852145373376920970516529712798889313821267063628327720142994294780122127130278652666707473653188001703327117880530591280340955425890309490822988690918114367183573226374531612008509755830478280832991890571519262367352342991879113700762419608345354559394041327807501612151331095063679827006047327956484579101617680729550648837999977810170783346783975533558648655633666642605238724138978633247966580441766556691796989426213158038563391575848395082554876838692343245736875079457844882026931428394289511753081300481282330880000815557739400530236489535914472429397044659535642504603534082682042259390346159601307073759759840003377352346173859787463720272320229187015354677580559498632276859561759147331296794626928218086014122941808247053354267156405235079537605194328826882331100835885393865620011176489434748090223005418419847316617366966282448079813403661337158937092802855882052336252493012476953975153799600093177921293916855426406276315882349831613253173779084848987604797366693182512024043509761054288590954021559880653559619284444750453974512757067528710916793777385575863432927197948586705418614678002328724388642206837991038746606173955033886263202526853327580091764455272351115283609483736667645153250759122044895816190105545525925753835757638574340226576844316547020503662798415103704241747831879812057044013155259501865979822530362524300802221552707864230985605190838077696081820201893623074406060727374652392413723063649998991299878618752425514081308701843332271415785775785228067607723647359084478804377595395676146130232256689660398254532849878363416437796764210483836729006181480176733693598505835196765796396424094414110312976921475481799253594896086370279182969729909847648798190896400135809899127601909851972550346860666605183693605856135485689057568852098211813920052774734693575134335629860353911915828218595704143437938455577975201072969676591392676202990583494706535147764843796284126149681007303311931978669545936084724756420270697189304309026024892114178442497017654444905595836303106049310565454549521597684460249351138487606785153633216677632330112296706080039527518007817778698643867351512983691472638506282019660658109245180975618534627750979689484573627962066514736246621997919840149430963367149973036017243001375118894645179276667699097720256214050993901070023640930399562433568785892783313841134706163313061590248744738954662508160417525080516730996340135511254397164078375778475229773330292008473420890690282807519596944626336526783693271315367818348061634215256878093711021563146804810816393171582349656137602625961819088374920049546448062833960267676766014658317546132582827125994853375967616894877380190694296009586514421609109786690521448256145042434018155399898462056091710019838915052763684981269934561267037620556368257245989753133537729047564275641859228121466907134578001578804638251724118455978381274416131728396363981560995388276733318111774890116921337370042430301263637370652352924241611221427698722594446608709751930298979048403558433983800102985699470488554527091497691696720398556351730707258165840173481697961082212037173860973595034420387380907311320836789962805795298367334835105817523347801401706235924031299056857946184592236164801943718838697547717968419469864709036945894932220067640421592932406849609686468294632387796226150489870140041611333676412729505755545367082849543241706866201121657861494302743042031251702138092901160710651117991804483034753024513669572710671192449709586162392249583191488065160932822571297343780680249909560129453270403596635898652420776045341746675117508027689589631683796169854291696734736369390692320508986740546237980032868926642085982678368416847615187465915427018186732519263461890484802670598744248868904856061166257486203762662471625208772053843948510278089143821165554983629511808528927516129327702229878381010265483492393639199664232153832618721121488599228871848962109873482511445612279960885005287898538875095018677892735656919350949764258778972964291706210245262284954439823010815500430400139672641264274510310323629551118808808128972860716660871077114287926021896368415133938430073171621504764112056779704665531904571076281041101361587388496618836196101279475524570458214702538361587198145581037749727468342132309940633490800654302782983960287914845273371719592090814973325322188643018449124737251317684448507397018467319338369061727333528690736798696613544994026827920692202270377761168365135331446799326860202934776615939583597240401999428301736658281894905015926343244735883063425940804429609171692212912211187086242476017556722560933485867816084077167333609888678622731245465497103940125039908751932782396361195900618413184349045782296102785567656718919085707425804294863809188269554849048388567678219204322577912985510608954112347159022924646357574671815112273568897112042747064913162908411038936902187532216946150697326524387387071153900003031039313212453471789245206349782431992208191941825380224796646756307460420350866163863089881792540973809342311985703897459720245819804215746467328871247464681651263232103689890044058780051056532434663725073884666069189629160076851739784513195070424822233729379575284394505218128088943006948546772723793123498550038256299531914943097939143793955199825818802841885001998603746557172279878129636031699111738528438894886422682687659963400014080575806727375915785534211676285715117361786839636097029709418468823918290451001951636555791260561392045299685252029263788053460147271803372466427658385103808114553857529710323717240581362997135170820604790281828362103058772645641767206687108759364005238957553878346253349711371260937280063128434634188323704463207637810684576744190422137872017894720531334446947137048181949350064051924342793776865791391882700709596026499586631051581212512348633668341126042120027282558149369370668503234976045973649934781254632669743561131004695867948972444283914304271191887411531377087801461506645327815788350759304346290390699457348907636342621138584776571468002318157973362442712837737644882158467329118124598649315102987756463924431756441331783535595656138298576885889276826056685024591183634096105972352555630243601645627350704885873619715419166207772824710996064017503090767409264692784705635245958141619021169158612220009044931508443846294432740298230863641801640179241079978179061305552600492273344325297036413531036416402333193149167175404002669017913151160328809727918556526908340636463170909018497959987632194908534640926946999627484552315544138411791071748138984549858701385112919232196229322701400744581596209111913311651300118191299870586398456751013668001264534064929981346343690636581193705044066230274781966038154216752123243320607697920008980161354417641058797413165372752208256255206361804948709310101741225185016564593864432601609543110136561805219930832253142497945723860603780946035294832957036605271524979159857173176500439560918925824622351835058617285200997758467948780222302990895278252590830876758785459220471854830641376699448312961250106979481764961707838006737386292095564098877535935350879124462834591823366484890802184875322650296278377455295287001623040670650110043539667679126817401197095627362763378075284181072479218198230633706799598641754145292598020513893290662993604084364071841342348528112212314542121431307487188938060635994338301868287218477549563689868450263382407018332240061898138204709175533512136497211776674447443325999582468895497122183532473340350865899143053078226895431927195501181100406661264825781824324579375786944983406505011650883693950953808147611224123953796275571072233551102398039410197910581175285298628351378928291954527307259448605793500591553911356820482829774381099347101272384614243002150752377763102880002763952775383753560921881118439946240475058821359773725727111781759684798389046097065722537937641548759401259878138805727259187394910478715588389780714785602337477719976548032371732577759839924007093595173411524916480843905700610572875429112807291773106130469963786212050277492469475414598935996354109253443454417241371411210177215280875904348021646062516899332200476710249356195222860934291697369195475187010432839943608490864302960684007505434666927254692256711458571313829199709707379897593978296262619510924541890310736669783713154682459485875632298941742886552883715411879038082950774936956525761415202617358125759908423674077840595901039821687021894118634610795852552048826276557266999689607839759099715320222752425915543562087855089665124513736674432746210575787936078775766185839134506784510377524076612142730233192425729751982680658999182728101371605639965687264350696242526179628766030384363800052839046952782997024603475803440265082441066510840269870661283688302746573709891317725280073070724244395843796571820173420019235800960770805267948099358055303929633947935597933345417000335245594401958838649057409482093352209046489954349835084902335149946068481665262528893164428064342168712608284048288233211185358575259042244351819495616251505126477839441946846051626363459326376197564094950619795369563406388451560783134942941243890774422713356957852115777708059508628057634291553609384750635803983804629797269290074218039697290925928544199533535996240359294852395332481190238547185463412939351218057552287536270380644448719271703793112436420400235304306103501319810426499110535562427956278762438358561472518388866543039702596776247131892044271486141542458599123958042156530386296011790760489379480785011146249790914697493198845683495812588371476093036467415025401448059930531296198316086750395988701908310433768791024138912548487680141211986013993369611546965287894059767467102340708653739539803358759845682814657914823085461918624100718399935712002286642409529822376183082707282149319295095459292089763499534765697143032393431799616621381582177049072493801770223550295846722866220087093435766674519241980054107806430580602011574528762108774578589056554324756328411203179801570076241465912845651208013260231213590409349595802600346119400656036781263654992316402634399489504032565558035375472976488267205958355425683651593041881289982340467292701803897697251445651328974605002182564598435507109228045819710418287380203030767774936008025186958540840333902936253507784869680211350635852159671787205394018600388586764917101032175842469525890977214344097696117069517358346039358646564093415088462182784940202536434503781658708968890840638308855327932826662830122617895353015711926866601876963614514132700131903918957063705054853329114369872638079738429468810371051196717381248944973715303274617818797349619826693056590748733991891306374660692236736686613352035423156011938478385614112886482162745479973182266392607803688627840056612080356191789558966656849621411081756021320222665828536365798180970887659881982512251352228099372082820379064716313949064239687491145749141097983224151778013226940927022974267496928734459488333089832544678946831545081806141779667406067038820995182227151871679625361029769883475370470223163021647266056866919814522012445332725717612097225874017947872200319476873960886880737356234386597906920873417848342258524866349401940491882116453390116931533946879701660383376448934863762696634859841215198685208626128040945608459864080045165935945469752587854124259216016081138628608974655514570170883841938565306299390757648463850047591505028610500208767857685435151668670062230224635897604458440925834102132053404342579437612605344298187052766842503494314488118209413329312501251170166265222759783635781673226507636128507339518152342873445972538156193447088686138707154394122659179201809417295964170735312188080613595595061732474006638882956372952186270162990796837272251866861091539318178489853268381776087101331332658898504690392403254356892272237982144858768495656395621921405913912380889278230553281312069258986655956531469919159818988130122770453874718406996363357834667260293269152573110622883261384167908871524667158175272444245924188934209160108037242978942095706151502036476532644347332236162599286209087011663321768045782994089094276752038486551452473903496152121924080649035810670374906883615740831318403624697495738818505652486253409867626227333504217649851863311257494315708891922974657239872919462387917884839208309553823313518473291261267909115924044031429866743635529531813484914165306093235892359914757486580852216545956635751562755341206446630599656215252159625023112686491894129434169358863801720347773594707833139993438085452327508737095770449817562567289969815610053498621746082819492200321945803443063878160873142839620057332065926829452201609424121399155202883799738916813601720831604142970652779207362392338789595976413235735560634149555167363854112802362062651167630166444406819982940302248657492109213975685580429770094528130009263824261889405366353529266210111846102079517185708227152127995722838100508219754389263593720551235777511374112123990863600546031952769851939914450845760000523481343978159549416684972874474997770861408684138474790475314600118925125701600927007347136355529759231976210294844559326696877348039992704005601862799681355131702165103066260348036049422607678907481205642020077685746280137934985042639237114748872216604125069729613155320588035344702524787398184884311341263072752416698595520836936135845815048933607488749364395718391429158743716148238178792396372141902593395681745536886271012843391522570566413091207158380342594848273744063423360973018161437937781099567689001924922837022259254075495075399867121942533270396719168291056078708016357944142335499715496387022314013608164455614790630210470849198154649343664877001618366689079519472441290186782840211228820778411326411303408823276557445059892643121547881565359777655481783558187616349591536360961828695438126606590093403005397288971704979342955115518162726864811171648950113310003738426853594302740577244203075122316213843800106100027253071216390007202046783736951944692833813812049593345516668789206766477923959831298328919891968138325737659827831682910945149431210160289639957880003977320290202062260951310721558320669503597248907175621809606999057616611204488475433470443466277982720281824687739390017850989554695593878615787022759134472266213065525106911784484997730340452451042531800339674774219880993694849476299058940026474107399126816463253868940911008388105812847063663067912740732399056783842247624502985500051362793399555863803614963958331176580692383125509147800741060595495499962739467492373351871838876606354974328614332124427097221715194045153339598569066617034300392046874266058962726554538151313359886464711263553852464216513911076875953646969039550487331521144831154792918387032938332557986608882611874327946057415844664713738198421501892530090411486055428618952186939245863187236439887799242143125871592030919560969585296693543263131259169316478766324212866841336282825790909542948088735639424951858538773232829706936850830595183717677455767527326918541071124557506822734804984053779990443119993137599254806155540082698703476790666380587982063117722939689035558049039814058135873994792533067384824032655347902451842979488007400330297252026878030147148653757076820944709624339788965916456160207818547095181728841147687601690346392772624089715876273733845522146941415693833726564366498464928712525841764302695747224340147115769827816549802488583212737632566129109269110509951300827126246881555447714831975127663820106974343793988388487449749005217331109578211510961866407494933466360279887087659884473804727985407899633542613058369940910294413645483666165606647342510343554087104883879473605373411619383782634262121028938027854035836729409072167366174670437265226280298866048484464849501274041107067911634902020062539595148018080557831056722554458921959969520879370613163155844675362813134516553881079267766103126843661477026022252880818339432224271358457182168625257353129591065871133207123196854193480620858621371055017327432731080992006702129602037038348882127577222062732636280774908259399844450062196853742689203280525732309562611300720105523443119350653093810001907215032048938160868745347990239873763991143517798498002222350257145918545859458531946519143128422770601180346916288063247320963715636141703581848419417159577158696662417003837478400917399265102222881389612898220460776389007146830068753692076111214765447568232226676633167935622568718180804517221639460669323093555424673251502234441122610565572818607258338747967959708114619193226376870569914920782978567496075230793836172430728290595247791345634159801287519064265595152895529219989864115917158205307235242765933951245267949352186911119015260999040708523882606643288215368811679138504339994316630433370093427634594108556013247937162177876019212432776141898979744205242326706467084577253736062618510209861619823205189012704399560677234716032626644039879407617387247431556967249572193721827490806510960910346758901383752692717181227468310931450556750834456940600736418625976287585258391766980443558085210847836118844383246231897246253491402876045143263742911024438939469428961916431423511767934153026043433406939779679085732679071899084021066896098131222972825463023730464647698890601638917939418098476508265796682511308467925735717616106260695832696133592122220005968924942076592455388968348108788048601333238116781789733662022155248775253262514134773732565010077963236152739033512672779948807851705449350724613170603539939697878920576780662539691895907670622530535610432553423983387629124901853156328701369051570045681893461917981715042912854094619644674457759983350494284734961682668707378265984890030395093158403078517792323398553840666689063830173359687636588707601341383698273993836359696958549878244241819711356448648419237003137552042652533189285088071391863226156006497455918576552935722147742947432009624731617393710884837501647178325424201000467479789184453521109171489063928812018171722582138549394619881083657565722447895548729386019692032463588200003969843107448158115215779587877514744070607635222413208511364783697785611026705610848721093099275642847448718739025250146506669902242209656081988384936723993837227315995911408326356177404815770444105319061543729707940817850001367140092334511455262301138994135555041828876093274522783645625494791619016153374653783395265970836658983717259746397520829029459299590042364896293073864796354310210138182903735107867350200270632923994428943193701119640905075953304164486939839842176833434107147159256771489796592649619597075183883264262004642234855853740669290657898982830405317261016648880047745410282698865571860354174180981106446343820239866943385091986889645982230251268018242115148878330173284137864788100517288707103127362815562881462554668628340103379555228219086890495427858405841721841031727576314109676956447344417949931619922839002247176375118092930164441860710364959311732488496159966722343636769366468286070767795090041944935186778379718440232147371622113946562397230227430277510230173808737342305599116013955141440402415267063049168575967067440100354957631732209726861668235709612273980611648446732096730033381401293989015005534390062994832387172206448087529290528378916906121785082044265130868020504534820072472420815092484759488087956570238730535480155821097516924898863294541204412965706234581517357606548668435339515520720334079499525973322214244818214697950832397217459769433459602146788892805657779730485984206023727629663205306881765770457853770420095814850766079476363649285576711458627764867935828256161625895374891773359699811340201243804337304918295409563486809032027993208834192893565336758400572679454105151642112766889725222146323581226230749063332764886387856670522456947300314890752359475113521384914913396134706756721154306994131578000266910757416000560144190810606821196355598546307161321980698180858048644757566997454754663149342755138227830388284220947375803901381193400268979359352170340871345595660008098901432524455549022645160962211637965553151123579322989680395943987113672530665946527368299620430413273574314501904382091033486040609387173196702080356580733102014219389764357141272408920320910626940995705290939340382117261854565712932326789149384792363337366274477469259803257328263304766516179158426297133831104487692068749545763568393793512735241593340397117386801686449003016172549271292866548866992788984263614965093104386621598983710136646711486381100067969607745092170957015641679480095704434812490371958022359773375961903829743269209767376975409197870534562063429661487239420429550137126715861513509565310420075107409108728691389831775971796885044274097248540879280789198561822818766146084908112044178839283270740095148198368059125308100126891755949517827237755688983313448854770834456216162249273289797149779543823482517396560453765724003240648197302883367709753558711416833146714500777879414080882429220814366355212484249692933545735624234191361845501431034688678462400241991560835105286468250777953227516489363571638818765161034410390516678876526662463654432038586924618735201814768471557669880639148384419269944876853253024912672425290852085493328460152262226941885186877219458315973802444004320555059370830222071390455852279301213949798986902718079996029370288740468240732951533121428566589639427180345730371771028379091643622445637144906584460117046987136588524245026496656566530147503480970551598348054658650197996847172823607823661136749887021574184740183593460823457154707848811316306690379769509399218791771567545634019278283429029173641988895686673423367088161697132739447591013945727603196929097433445553469805996481109059857081839183398926178139713273776238694728221061978576443853988588183496883341046474580215547835427598174111972102645136568446205296572071856573358363306712322443504483898604144827259852177839883978597608247366160176381006633771371579293722483913831657574467352497077370649533563334703386889586696131874806348703897854020997854309440710911087032901879307914572563140365142694624359736722000517183907181775337109643739426928617767236951595954864864356148044739074508214855592080862514740371856927304578713961443313239660488427670092222839116418723571117679822112960203136856828173264141095747656361796893735094649115894846274544766989101393595845963762650134499977907507164005098364485397362187036283222143526461988631206047091158847550375518838953326832738399618607903613063056631595021600079269607580125857908629720087027085553434948299453574515069130435297365333093211472402274019180252015256210568171543371513023464820657578482636759656828960067124260244743932337107380902173779387248886888148451247088535005708275799936765936623905465714626634270611774504617334450417675196483404361222790309205177239752259929377609915558409674245517731231484155807188633024044744698747827183237853710412893191928605730797731225248832192491115250980912537407972462450498007237440726209592714032725076602968497358006714308721572461211229042983616378370296621291062740923275500273147806261344831009096538267514792572935674582697076513785095644160995647858246321341007607089683617901309720661632142029323132596541732369137042932224346316043727016318592213680619602920500515828986507303972472097605360936226514624444833147191671787916965876288861373862688967176411546897575993324219898044070184383760130644545739879537035379252133885161197485494427005443493367363328247870700316150102903913649451815908207289644782692660477007796864717061400845645253898902130485858659109119418105478022314463422751504716199836862696092030636690730056349955701049985947700310360562119528808634391492210026675434893090113001709206517424692128780285671933983546602902629789986244848472711134786974814888189348155628063823592607296230371548002964270029885538963419885329526259779858737615245428914736916140945012248964922236414829631593535365975473202246969865374437280726576109633450744611924705561293228985219538476568542009289490212649281577977619141701709214185305973228645673105580164696385902889645615585138853145454405016650803194943875873744041472524839672933827922861119317287888509464799683743564346752028299411453874808805986760445977949542978123663364530103504986862551485984335440953902100545603001906051744783452468250749880758577023403624018385348332000990716216521496165245532782462213134406864532776355827373116527285713335109625039781336027457239783563436899280652329690075618951752850745931226658668224403024631777903062066794812755419403951579484062594576524416846657255344920986643781013464493248234348600789122594868924025350708784293446997517670305260816604552950176401341183707873421867295431445728863778039818076365802550931019072253369812792364531594390446302435391407364276217939799109545813592848125395876015673239003739497841367996098053768770120738187639597787657779406293289171585428142732739220127120540818742634272972195036279367511901387598078452219516329017573689422559327663664438170178813681303975752277392171445415678304876649465563772127901931351957981874467463205112629088579846296361567808884643667363414344400981619686636485337333239477618663912520790155313964996526786293550019842556962127549116431711006440799624303906158307529382744964481331133784700640092608556035374449240091912733905302866571941246846572127585408078195096720925198708646908841022545561365576498060871034329074341672488141455074682893130268431940122031478457873842757960658050821703223716695488776006722180025986662783897534169060672087975608327007797339987268845992585504260170916265619305413836690038518343153679828053537469971605723776953711275545376277099363738891860807422660589522143989394293717942861382105662500277485413262409064201865776956873568383764479410476754813777682102326541795040066436903484926802665380145223106251449270793273189732496837121036903746255685226654710796427382349069153627604295414898865497290123768602713715345715545544827850021407222357032980771672725510545088154479011114737704290229571307631376995333394357371160071383093902253508425152716213317811908173333054805019908677914915150445727176980696520011348119778402811593086070546263188298524417878965698427169124548391151919056648843423528600491918329865311996548067796727643754580823752290190700189435070999991303248776544637547979553593494336368111322740090999947675296230612135096418597337084324610306295166325093728498929010394577962372223224348902924742086382306052108228352958811972045386580787691814337724734285383151596301120839843683760485849274406978562314888764007847389667157936379394591476177637903230322754506470768422025685133825234548597936998378192270392953528342556272109454857461210454709356849530558646868241833893212406841823030223041671169978176917134422335088162449760650011512837492869699522778819128571343396583797419033083236147879251423830088364823113253366196549490334353398557597821666933432789514060544507485141859476768251702156032621409625872226875571821427537141570237504432727830416618582017848704229171835891266296655317270642632470250119547268779219255551230807667687240279931048746783918410595685103585725408761491575629079783026720943940545127383415392987959091374147557251204376487403896996132743828922953512989829291371083056358089261551423163507626594926096205778510508215224031655323038742438560474887656433658113609660843885095616754627776188111347983389945387078746507001750503163925376109286358620286047791785850248469318731257768169398861299351375573067116175249014368722791091856354479918296546999959137489166423793747618195641976592273222557612244056153316507841573022133000568643328259780580172966977204159742121610353085067243317833369329988279113309658777835189542625604451931007856830742863205849467645970378094765140402205945403657744427097690108138322590921606320010227331820472395428855625539157580574487613404266439068946275755977783810792672058691248031686955279082355641482440682117182501491161742478182131014259136572438983784655933288274810204254934058647002219131633683054416910891859981613084527124197897258254120647014145025955148049927011564711145482697161388826200630024770882335089365367755668042552768061406908742984283646193310832659886546252377011295676618503481991560172773915028882200080831512561693516387160780269148526507864606405640232615496366071676503138104409687342111065895510000119940203489709222652500855927763941826047026063472671089079745085089229325770603257130186838070682203663735182290936815164293407661375557034414098607366465060790696143389710495908657387587398144933651426961922385735740173205546875396407423664893462968320667387563932922376516743045010737161521740936581170222180306887352745051136747075044685133537223174906772311387633092826802611781197319833506446800695268894221712986839907995210861752644482767727402957581441169799083725445283951536610709520062562190469958829335042196583474680037802008078823285662834361303677975631286352543051755917948077766629271417371795592995170040709704086176738524969533580686249262857589387059827986870560876794172966525581791300223644218981668329699737814248382018134762696788754677288220793493293529598119796833378351941272718332466417287961546843249528787709866093832684528276062997631020463114596324522930999300772871788068163519547483057716605035733453988538302269022290230373171036881299991731906527786536914757123818405910728421057316225760491568895856286329000725080806314690956248756211626618432960602339022481054224072470484878702427940200894521627256757548434990696668019300463762987748995171801622076488027799973432098671879332174638217849380376556313598536499254549334436585720934916488062874896161191710543434908215757634262609899818985550813005073281206389230831477113788105450248297465066769039992433384652964556420743589942087031868500594135680828559996821665322860442609411668817173028535999502551050596831451477180279194871661682923578533211018725569138254800036687632451440383320900947086212752090019008081873923801629914764523339518518783798845343926102481886484098311484486889069229357274491931902520782468273833715787370343523426115282032060214107474469299951665629439712065023607781730290681057046793869546340034088405304847657740307839331126762148821285519946578158818285171537360360378489894998590538625408351470054231890880631173177972451548243827551329671064441435990159407765172846256717684175348170325557688626715774337813388363133672819793625835934524979432768671626820566748567028585545961355397255021392637632210638709907262458927247360089951357566699489188114276321731750890772151558032144881909565709276321144078082053647587320620699631192931991224570152652593798787996880616092204179258209573727011263330215941164358099670210056089495586954944480277192865788978455736180726592060480352191987745540155729997300682118182479149289698348311660235417251159976418359360613551107057186633444510705734214627813614343793195140028146818641456008501022652986652291256065298439258338480303815939911596192574043323653182251580374322154044264755847568673362167576623772837981044948010179613019520044518436488714447059336974984543814770619937786382585810444051510786942187884651162565619750348076754211012604168370923330958654854557012232160863525736417989025687111651609841419803381531780726632219702397044282068292929842887876906029276922617348375556663705434427370107158164763165347939807729737092298025354131632682671451926933668880455624046968914108215174973274672124465649476367805032465756505609025164636851967589861359805721133078032129553345302473137674169381016521999237306169932653360871348315493433151243095697930189204468611360207560859030350976836634508852287246946005101313037176891083791138524750988426818866000633483522749819655594325492166572274499215112669727844399234544628047380067983107267219805245535419199924784097231799615141719770445453514007992270558375616696323421928688629991625036217488111069295368340784233966356500046024157619787246401220849265589100208470445120799633890268399896593792177667299674499002947384674176029677832223520476050025832083778364373194202522331293225543260188272227206027269449565312350144040076271633083917404212472525676039477646383341810095098187138248044050722827826991260649278269941291946249098062546306985683136924198854072494423245562856944225498121118793219784466546761453032131490682431679357853106518729121053206551427281766674158492416433636745497498754511480415714299430248927108099185337852136482540878261348060699634565169280346634529085429512889099806618980280422149813200553966602989076175523223428316939275387680918513836240188142826557512977930532638290484740127833434312721077020454379758691784756688518150989780006898429993619372655501149511883113212548406263813793695179539415999418393961811458014711251888242117719792047772877512490142193332602332739232347020329393611922195014842439557964013411182925879660114490838599014965850657725548107204536857119829478722218796318601071737604163346966230019321831573792432839650924035211468728477263599492763021328447393962716321224682314043247533172280406131931736554489951976353382895830327939095790320571247225219488960053901681769875900622654235258626392687787290983995688972458861394949024595997884249046580321095649022064039487243784241253272566697800249300556511049311018670878383182033306782159497721090280276584107147497794528039570451854204640394731716387700774041222842444881709783250657563270563442452589707207087186622901469043563185508482485499266868810066342039220025541737286175864687726677956805246985849518932321027756168713978356946575103308471160361176206570990900642898767700464107809849391555751362824283103096537646898987403524422449981773445555524033688385818059321920082758289552750367600181471097156243029568673359867817035491947066165386400690435545409109117628944596107867431261178199430774459293151465489996140285790897552327980393146460725121712233278615862175569275842519007856291308700875506772984747244072996637107222977154660285847540292654368400143126820118424754299179630719427864509781213435862844506170191912504571787435495964770451656609104948318576690772314243789185600541289185337886017806734491693124508518013484485479606033400536712903196186483367198022437043563805525648751530000390711105685645657714416171835407152544696358722241921951154651525414060630784265544260418204503425233404703052208993860119432175894255766184381870531036439056928677499630771634024027598576670726699890679104042203363927001826007625173752635554207014156862459327362715409880565232986532629854177128289123936374416136758886751288455120610450382099688637277806701108243483485643991728187553402726918495635588804279190397375252830074617425734676845900802701366723071324965267158408100238741281634684382887166806029700024772213880333823690918607525357955178912899690627915618901325436316177795883796099961432849372748081211617191850288882350143341700561046968806467806839213994824252952007512727271325906122100823519539353461057405082281312586395684367371335727061792089891138464432556136768879363724000001992242661489470975951749754374365106679943237831574100134093237544932069906459816689232121853566600887892259973149026024953661262763830120231347792971420513972477416957396308283745675334166706431767838082871814766490765450714071415428843211434020888256091641667954478700672054847627326895222795850267670922745634830851252313307609048691972990173944483807003166522484934674574891185354061099331949965267979509278892424471639226743641916187369474701042083758001347366696916161973264985153801352852550140143073889734055843478841848607595531552820730945831779667699989838122235146527832965693101980645362392928501816884292961123232293195798941046094575383155266278041575026090919617825820072775899577417999027075893799144344690851775642710446948499646744494882483745661189268970161740144959350145712715432828098155330411002882761183362452789208543891146576481749898685830297200004904185662024012302401840208741231805092323522624580853096886225375963231350542618497682518058943008748858675001024332497644032239672002105488123928455283117539027897019391441770200027908656624818625868235502983488489967771398001718518962779414098346906531097658121594521807024621623980052536584558710360533701583929057601271079977423183433153940667519614388916298372372979011887661854646407052157532286584132890798678406335838024552026136409529620608882221189377172273975639872248106633617089001739174433874004101185628624014648104427690302413766592860664890632909078741140030380768482805098864881035575411440374240758103363845476234362049839558796071370403956014745455256544843482266130889150092104784448857776129182741245888033058748353701737425882989356086565183570406491701591586246630982425676605675797731486391507415973339007765159305512660802310086471273963233454182838492421493289959708302602110934329553562328973968049065917117016544569612448289500833850895566476454093490447322842217805945922319242711711445733689836601639824392097528066861963984639091703460411545367254336537924050993854923721652443211527194196840019339148858031268038357990578331699972448811052357627764536047970745175679444854951591754968055201277328775981067831818077209957307140516490204279840745026647176621984341912146838952385237687123964080596962873340396326843555941979178345549426191176106923134634794439537050547559882471747968964491239940251039747852926144311125928015132707720370594402801844247099271673717331668587685311152085237209282124602248104364210125235531164682006967532377389193098919490756735507797388483492214090241672065807845426534950741535859139000315566761331304348461381765343707937781347500031299446788396134217935906484049575243206677711682584470072881727915803921367780567524356740067919602619754973392009772429026848569903251417868046146237204240548046314580703934553764705638558533648630768050394367003252826907174717042211241110885342356227019287405921722717885789776863296588741457631825073309188915041812396803396670787064861131611508171026194955180101051760590139809369191672100528451538474491832844523545045270868543053282698061233413367042797134516068483890753068456526943816624143000765112247639415185881495481929614414016023471424208794421312575161060956488409958211118536751513692593729882000719021791423900277971067037498348216405825719259021558977581915351206023184076253491902770643849100546358663832523481656632583011903227699434656270149264262769577229736215556095074558901161300565202383447299771072815657501770573844400664858103824065071629617028526446092843616286578002391912461491845526924870619512192851869302181057355871538739157119290633628482253778899661480695364417654651214515245351853624898004414531847058290243637090643615601686079618945060731381076621995455019459297894336353299446679806663689294206971017611540431761669370262376974465855085038440604935924815586958515111951291409835291995563315296033440826138112196559512968568196755181932145224236261196612343757005123931353015759057491178108864102572037237806604047708587346472295971701775740917006345310172561159526396671112886982387282272656253658678098504940555690700250928184901201630238286855983197655647341011668335410662882374648329435671075257871769986053312175063680560376503824755470649516330725314593934410732692023439321601869057819699545434729103208759446214605511908495113562408772492547557912485451609627321516473720077569128677881192438821351965491029128240594864887804797326170655070255420440270559291141434227219780363653187297462613085806628641332459534383132960740631377433227917905299870519982812334953026172696425789944087376510261634840101686019227592530629714694793870021552856415849121672965671405534865057661875423845550090722545098760432172759899663817206805086914480076695049752583047769793635293186976211345401405581734626122170490835344328453451872248320845615845568090941890806809168231554251678617922849641820172758406104525859148631343567151404396468803291657453998787879588736494694810481541900378709171371314911258560736880657917708230039798997132234194528417281678074422028076191881737731898002037953344201459002295338582264834970668742612176862052900551646590328849126249378432209161357207969160166272705326276466764357382787639991283592301611644959954104212760505659012253372567705743406396624783358146604038015653833096516584760595662929841038301948028219386142532034401820923860255679620596915365632634982817164680549764739666368953215893954861675691493074305264270395128634718526187542015968914103351394356285970154229895323840561758899188541989150963997513693604405512030727973429864932710426303286221625450163932273144086415669696406976101451996559720632250589887786577112724076581425230243422808827511502956051455420382327507295849120181516000998736118125441306959855256339832426158230783344203648908745748501161035056239469562493198380585729562679795209836247968159763235405910732345795674900236539715710028164818631159617063463077502686073445874871052203061300095995865493887388440996564243274399380516308268594596197844155193044121932621748429915761518529813842000023021609759956991504608495181587969029657277324955232557331194230403366014524589855212036931607627109047096894392015193138309845329547756402664165055400540219178131930135575161869416295132782544747060913460356311080579458456743555539237106734780171589183882417338670582876705452725172266380157872657365217608061704438279779448190925695013475749694870857468662316974928965976549905849376950463799727332540828122364247812429187601192541595449917877833110831880204825060730820869160986451116483109450357433623957333651259103492058479747980086950482815386936696404004370046807406929893414953092491113674923075649425228500979275490691222172061335106999446381317518698693461224281194986659602417752174000703781946039490347031175783137663639685021266990150473152802586496637971201042551463922610941550393848929857841589016752585545275173446344023812096560799854251746408704319753667153294139224381442104487867601523858682548116642566133625075179612782026906471011560684565142952725803823034459197005315536129708011332607792461561971201262414827002803690956623550976358967531602012535549188179047563148936367967623195786256173781235488046279540044269690977315758299460904604666111144492157786107079604518363743042191306434032403234663828458012842335567602807785325423364369511282817469339352247515121628141618840423067015317848329992798565963991143445325714151238460741904335963585354387422392629693361166051959753895131132797954768904194733010179725676005046615856451526534168555864550471084617374058637649141009870624568252288224515549911200907451635164433421281339798590395073179891852631581852665880052124424642434021449250374558812676046253993914346455583603046434377694195569157748662454809209114343075509248233604576276222144265524132220951487073898809505428687733045024663916441528870564658040459234483835465565148832395615038147084833131950359013387866688204895860937133229696499730684862085817201664368210374450349983715336373162034500101357378950723334286351794360967496370229631784889167449807905173086820091453552358334903741871541327603414951312743523126451533990116165402269334069336840272160183628407515323790616406215484274708057268901289323650140086703878645403647125935799395259871216978597274843278920969576428660400807861028112153648708356937218635273319438464004244054403873703138014535091487672180210555918627467363874198369986005235772762543302476040220517514024464902188671131721829415096159837210378683766257379005093334471909448444132843757819929410401699206309461577059003397473975716506732490072384827372106660087877150990991606665235606804349802185328075902906008124741588271988989591525977448959833504922756107461318163076326018259567262102298788268644203339898062920298061130596992194894508288665689825600738551645507985658153447887396048825199937477968371463773363871910885732499192796348595697201703970766905212985635955540028130965033965886326384905472529738984792466204161677170442374474878308966743641447097540482375421178474119468600261290121565888182680741437390144690910091587241232475084977440393428229329784391484797982026474510931876278863305110669544783987709309868309896553696658568984219422557196842743071872200163317709378350878793482757670344902533781341783424945474787397952822635815381535560842282330477856806668076298786231476318177038935013532761464517276541185378206803762064016626700565102932766908535862018779829876759970445821898878863240742225404112128603698895101107125235096424429383132858489365351384559211844239937073649743937562925410761019925559966337671168503271185979972070423686682123346885753619846495674133861682224471621179093017323980100747170516367300786130661415725831987448813333808058594415353120648261294704297543038557397639866357823419133001471349089009640265671446089281955963578742558260590472391475994708318656595885249337527604642956172736420346319082191458773676849576166327019719774257040233972485113619352658181662218770981764989192564654258705815101602107098250971845684713461507526291630298752636234519679052449962465129750394242013289852839829965429279219222149677308268272145881596743576566935077077416218089836081526517953547232950811327476176143975236053126563708252403419453532919237951596680401493508860775172185364524092104261714115482567488257965613306118082085802176159740533490603975785910573016131260354240798704797722900378560114636096361820204311962422775678999944610193649396690479434309982999594993473732804430862879616591063029942421595644678215257233949737921634723000605283361386357934446371722829713924939042024457722063456420918467396364015130604014221876080321705843159214131143190497779397305730857894865915420204266462646488351310002094621390228336431193229010589774044215429443462327992446757888437604669723130876656840904893924377189894710454278877384476435626775951755325819049119262349912906166758223645298957562223281506490426992730828703902439263672209734777499323592942918851410039511668210394854224974977639900834153589892392749663333275247069698353427884543063376584358153212254492469265601838268083796427493904578285730835051127951752529651961030505103167982509478652746078696341867632881016723481728837414577139064355589412566858994430462882226390133580428519859157453324676421676356770643184944485846493288503022992674366313406544773279229564692761521937422389734627583914625467861414858815929377294573145184156755635437080625706646887969416628284808650353586105154911230083023832463944113396216885820621720495191045341050953252936879101739363146323138457174033649655886396368115289968235236844210366318775276959499850804087514260851085287607438112665300319664338469540577390660162885180923961624844608284594978502848298163511305370343648641190751029714640048339613765661917270198270413105069917662010375339845530169140568851932925707240152460723545336363794840150760486697262957040291570201105199874485567970492214779044064207354908952611997509972577022572548326880857608800313306140201561437441349178556527462973789675493795887912158971886651325665847874548373960338356812519970271598865825128550358475312978383989015802771592208775415740369130061247529917976737661559448053295674260362466934563208265259341156995255065023278760862386918372086420798663072281556125503215507599642621249892837175901181508374837359575381163057847194212641778060222254655446799338856739157560494301186462084670938544696541532194912836353681474893288515996236926600363115185855983712408580100580597505859615363118344468934077698151132405270447007825025736235496541026835974868735280393556292857755196332343671155678214163861065912708151779131533752368245300755381445550761674127152525727625597554231026287126271687815396241908058139306129542872682973826166797777841174115540713562060292077510378575388405449704284325684682785984330572041314106360994056106424069191902493210137314623893858501206343282167846228324530241730444305475292599654686908127683877743799145105558065445727302808039715542054610115528824883872522154137041410650073947024198611141811205836235514933861602708364467739791755733969754278277241842524074216883380121841997328594867270530580443173238247309186736455791018512177147642002415911336671663004293682788948189118739671202409709404465745251308944723604802467198996251773348846511291941814491604856315998510684367019402832993430538185205967429062820878219944226904457278397816705954848551750499047156066091943341000783900885382314515595349392301997534302297149459222683359639962885841773079557411208966734421722122264733007941432549381487878191690480085476848271156640873491150999216416080116088096233337179171494711192633310573588403550885173075703590120997095531785584069356284593607390470939551053451016774697735853240801109914178714019493786243222594555928176410587196381866362969807836823740258642628075726829059773277974684092840335297464567475912655018878067472351809660216336742553148001794053170615358614617178199008255404659890784433672436309691007400169489456577108685302145888056502967802029217661965185728255705507421773795623086025570418808688682719416642957964869046314408315806575874601530801943065743573919758605433959109008518265559299412642648857653936170122184662953622378284802095668356122036791366969384349655032976898202534544510197137057982587849770809367756313131143087258997810325116210802336204708137181076734483608493846376491908097801614449568334366232193212732284805805359562650159792949148586514718423140054417215105409069495624306919743611664736377401678301093185199689652001314485894424948464299540952417812834925358860387016633166664494033252205366581572568415083757411948261245854186768647914675767379096799992205145589120902676230635465622444678447500675650424410372491338774407508618720049048018803001054629123691476299812452819423133747445479310004375325102271960809067143519047503817916882254184917467626334298793149024833173322419873074072460448536247441607973943344235842064365676078508724249144190651246911578451208053514454594676733488988882215359822606656049449546462802088701142484489422908869532463048828114879647838468129492176189044376665581801713020210153446694187011303199718449161477511730497781501493081675811173595487390122593858397160972477601324483399218839706961673365073288032631179328146671440751283805702600219471860296176809146353624871414594252114973448564401347968927672009493519482502922581516219996580549617270575792787657416734038144698897098447214390334728315899279404481267951627296094692651888529252289377826062567714467485641384651637698355261274635048413565675034752696852461524036514163428827700495569994979219553901798654305293924016264520116547349009412013323808111362028382858516904069030091479429355986044952497028350464793180225773546123318798533465674528868441826946275742052494382450888402268863812744710535589036130025665184198807408782602834734366048782070200056335416576926519182410643016163855239899185265788921381366015404254307496342342177160032695917059980484136335776705804119117871252979328108200808001036195583289597343870316025700428558480280966628618074943937055278930997090784169980942184976330615595518864265469241272478545647909231830594022760181392339508018227589552814668992927483743909758030543992891776989784612453832424942926224168972227009231800658528663905700153963380799607046823819131060025087325944360999479735462366841293890945042642609749669094799237464675961069965869350724126490687671741020801183934332271802897055944460100852646434270057567930672940988470279590814448817819167558680263208025489421981535441863241695526196542663696365296363675969052313670192945235187967659024942298998635823412050585692860021504479403556515886554774428938536314410686477337390660070271854151089915031587656861829015053805269806023520380701055159038743978247110779163202076067785974574260833643698200001547157353127013727525376806781322106472486268696484166976151748363426459578897022243584840356092603088548002678073363872397274203191964683966769916405312959455942851247063750647951259026532311339479791163595485265816144421422424158892471535592316075481522526854592218729301551251919602594513562995907006138599486569513880862202753027246745290334130491144533495532018289251956901358805943962596437051702243988423404391469268373427265607467822958176302514793396166566408986607850356887978287624665662418640259972406146876907326193986303341754993421635449949008212742842574710752491754729364025779388930321039447566831161408412532458882844416600735974722252980839564286423637562661667015649735813471090672392801662074312525941113527238631029024088974157421316022203479346967866091695309736645481823192800526068086345479031700780530573718574681364559421865923622871011689623973238761783903906424384706567436492434258678776581287604369470016937765012422538128268410661620977174970255709146867942965947827654038759272378628141543537615048749348562682109329344173890755355886011720696053869157755833300975383135435231599879891277386436013480103329249832026750566833417298013134576569334638816760742372316798774096994370723203183142854255560061240976727720936717171882768731694014239207521199173559449818496248836648823987237085997749929200598935998873472557366222786097617461911205916750619799035833289802659968667033296636456546942335149630053996986562214934575993127475754653024325500610854837772990152093490601680656682334360668074800105343690294647771079058715566763996008020005989986329956378896045071053123603515851069605648772516110094982649076157443518119311488838196795586142358295613841607582920483946395182851124950235816807983357034979831056373546943726777433946407199010270793412122832576117410922537103938415250433315568342037119795308305111701751821895320164513100980043664146228624232961117855636282780838421543058948003778473216025079465960297436727161104345375730392130299365850777684994710690776509083903321394290249460971405032180983444307945378841431267303002468275073788650082185983563379735418484757274765164665096856171195276715108831774251693044366477394478376276361327749235107620665048089954806088250517192982936447710490809163517378357904815181549725389801640087686742929959050826233333397899767213850181776779935691431120387821781349777959512388243767607248709966214294381836702808622401951626774047920630112603316280797080942084244129660196387814364960132768848950387200011142061545514426401282089384846877929132298141861873769875107117674016914490908732098668914751739845186821754895239657336855416408439939214008646931782454292114171851429301856786303595125624409270629607810737464658878268339590139907612720603312107893115979151975166833478161638905625089851696931911469983762388048818153141831930515219677735737411795305012836967086420757179844136367368885536366382940999717427791133736348151199457922129380275895350361286751271886892294077987088288015431681197782382299785312958484246477853846609043674713916135683293629708772832459338731697589413077946810336700321054252631492285726118257556460491069021298165713544628839990653889662213085616000575764397245039849081514702183007061324480846767278278998226865454154238340910938322809134298897534573682514788012956928209666650419638749264962249789812884208233673281057626296575846639584920623285542737621602714839909349873893277299527082474176813945105066234861648726730486238392441165569120540014128388771044836685313089367153061838956351736522160750772424153268460062706192465322896259767659530853753795429618451264029103786082312706324440273001397030189290463032775075510789214890998340041828822816371504821161390614904733722100689150049898666036064913024467033507807213034785116148545865597688008042965336594360786638539054483060942676345317560951543223106688578246093475113456547009371471270941495479462833093239596930830455266590599728846104818503063314611141659843801138850494418020793403035418847943856972604459971154232537878149803202289931239111005690490455981506631383294453701973804004125323069687878284233607690420657865364512261765970011371617037272835016654192161992827698037179423017733394857561941948273329253547285725985977212498336958302004522602592615862848089646413049706486878916442557242672971097014009860683818445926239023428114508665933613625620915000364205700388623862064893669610382248061475613661466422726461774646403286709356963137422003664751985037029175638303076632974922623551737824771484979250850749299668315297868739099054364808710459112860864523883226852369848767672942642956704864436256271928875817768841497658811185036980464961661331315090617859212657901353757738306954066257056731774535262362855412773771517880879115604184351673407501682229140391337322237439586327547842542697032213199391887502708263661210064480294390916153581010337545838006993204477961143393157638116583787384770888004253274354307821769848217295851852582191887846829731538491591084132654516242900575999390281705032070787244568905678865715118739469674660077221984528536225932394673655319257508581839451764918665259692334438635944450946096540562791131342013908629843169928203328129565873518748281657628424045044669821891166359162312474920135992127961014167325805829782559978418482867944323428511500252450328829607537405244588974600374316217409874662890185661597646351360610983044129929497596548701555123201115463362869026430422874338387063629362516873555439560230096378429792760380989857602747321373065228116106789658197238313499941250569487259171504258263391344031653656790078256279013824658766954617110834960502678696383613580745040785041443023150747537770928605067939199409682065193690039474749402897569646628910958383026370178141903181540676621484838088074815989609647772771757368561585105973398465273195767673815204735399345936476354602519939520594503113310844161905848418953074623285624612044327126361053479607774925487972065773705440414765960898533975347134603521247760561954694503300366879030568478828116129286325235615332230497169928008358356548590642136476291864854124009326193920314984481609172778135687919282281408805777912942844223414644641643627373719760116973631503924234610097425496135069641501764342794827604044771959796648225139657305554087712400241187631530881310901185414815788046611491525801630306171687076489605844940373177697230552116705846709080287050380539172037677465876639266346881654983771712756227359472327430380532311260038302359389771101389168307785882458708264210646839232229652020707219486967319693280911690332698160049763816744723565066261773937368982543514517341692883685423363541794832373601120203742655703121304983587506684418790358686738928159238351236783126797051993102751085272704626273648522976169089607558822962952710863831617922449289218764244295217957805492345409477608180920349697952041909013819031175985428503459508264012280244389476640417084512947824602667503086698439913246481084570949366559502188098509711960415715486744905532846768804920835551750779716311064960553465503643997017874648015387155784502752372650745193703712587764837390191495252054091984123400918413997281649286736055648188565667981146066864331412333609343115338539799165266187718183811029612205922422732337054890996259554080080901298932857997103253310563401185264741680409682657158059778176656840385638555797460862161724855209604209938704871141312461782809263521283394631292163954440122941418665671292016135219021775588600962668288760813391252629398537715383016841971481646425886051311631364524929555167162766032594588796901723439765576245191268590256510418855805181719641767725317146541754795069643167067145314858516012466633183764678035558691437925306980245868572427235852208813833207440101710917998978953978857250123643902533934880358231454719581223238595654285162348143223326672923200930056460994056001845782358675981885028857856264496453253987761493780416794211579107444902299933826483672948434477804821933197456911024618693325041380034890071968289664597528705115993390146334597539879848096962502128898007783495173350059503412863500537770743324399014148856817889510174991323420801702709951973412304502488474372803674322142026365179634545990566662863633145782783220861177321540260295138554976776538888427415842756350002198177564466795784385285647589898731004062646432961331031852862351602780748433353613253507708088941821344755666282933152694417272520507924098919473991789019234888291307876592713335196827754876376988708423652960977490289646478700521004701671201813734642125283482867934924827198014226303129885698586159366936094853822189007773214052042154788715703790864185924207700816622204135337793004634838663172512683903465414082052520286250830340511073924440808590951959858967560924432939755515482361645590978230652256678398767985119876751396622082803334230484182730838163456209366575606987668626285303531348311805221014121087034733507703783015275297971368592759522545325801915244577144231105295590186847744946881215439094086543340409540513567999994891121508826078844695598763269170971078966911387575737629559866671864622568443458725322348073622143960649126752159219061254709551351474589671820352104909081770252620748642067535349896305490362125916068309813752649291718047980462737890899138714497214139073870362075608865898066165208075973513853941143134652343353734477020702994573953164799021712118811785993984052565772767492331356856672277508316619280131747063582794344410597582860182148884129072387623487352682241231836148987044826497789049814126522328780033091253345169829489428683944322331151814709727830897359667246787753009702116134603558742123769563217450116535578587971597502401017066540862993351138891973573765679343698983183963898884318690226194398127006939302937345574857183571627206073021659233052764273163808271744670781146909250680826798109107589208274943301685407725376667580150287289932172429123975309695392933689999144593654799377874533822951090478670168404590655780765151977636027341481634404715254958810454347108871677390173313498655061625378150217176155023025651533636925225804887350127585259774977198511031299797260350712637963212656155764591910432562515169966695390395973624463965149646765671163711396011245347047893079393197543488941500166296921057887784388465469756848331249302532378670226620389680185423088234681898530539414431591891996048597612213322006464232264500136439285956442612182135361900696884919421211625611537004146946882764970815346897491480096681131353980195300394120297102924093116881332439756268764416323737689297057638261317204700782605064920146773828128717457315194092117074979388536313549544465164247343142100665529269192030116944020476285747365179350685416212661564643029064493417802062533729713020945124014889480199203876332695093373254232425812171926967079358643388021510202087021408302437076503050335635936745313225529349039706091022867715069014103176104248347974029289820929437941277671852983896095757689120714437560517735682975255115657407107067014124605681227729049847132590990367090837901165526273059628698295514917637967954566620021742896933309106348729326472516519056781451284569753021112250438210269946995653134454931916741959950784760857807006269731721663486802327928361960658266119409291513082715498561508949764701079157309816540290219168394209222941494587034709042117324866696103564777287336604929031744132836305033194954948484981333305094305768249321791770504721857083697503083398455103508310059340321326716346567860788047750134827359951076542439116476199154260091214194357931271263797403425223185347446041336465239147015666176557789242613738357602292598029588098996096849501142123947568648096453698726968947980520617965341831456895051113866772927481535857245710887664898913533486162671706201221008110749305472189208316630016526117810739029110696627727329097485748619610968325722689631960113320364722771045018323556039896138097195390894980890607353684924630067779493756598168305524821223324793216264307208930627083085739130543570495162274017243386138801718660327539889319016284532017592796742108383027711579667223052108785291701218696182873801089403515247026559093948077503510285190922551362556270290578252059472304770338431360792370926259949685874899861001584624148283650722384719835762175933778812451693384389495984509341665016183988379838020885584778692099050536641271725074804255339696952438988936658104517883299775528247926813160498011017204179390746817182063143238798720254198080766508986158307750846832499919206101716926717957023366173546838311797672764733164665715864388883648070826361267228729315074990519781449387702009677757454852565385968195332029139283614357703600680378292314794192325538373124836282398816301537391407986341478964636592492995710454708035110774605329389063596940925031207314274430422789772111188838418712763267551406309337653112776558241008283597911764435533328613564276994809317416602281871311327255437791981608174702777904984572561804675449688245058387603335247889415538013196058906329581379464216447539775446433135546342870310108406150851108065008601835075147749101175619752457584813724480789981893034386250548700202160004068006770409416015822775382689796255766951626743431698830192602611856561178668456957478487278518192647038541526999650554006420813472013308452785609129005012812169819510234227066824367939794579502436031326388773152100179263442268992536995572416902128917349908421701126242082210016005820657168862050623817770637699269938183600434944842153249734769535355970226754838468744541257606627765823182492720761738750424243337366673893931934288891389575398574181835537722070924934640203670982209161335220232928250069864197845956486779002434851113557241917771954338266389411946109314168617011385447376821710696134079563074024493710188327322511908578845055501382388590771112298173769601611385586484204682539970163910453190651006923590282337525503325179847268739589375824864328317030175561242308803510047614706061023937743583190733876686033800453129125841045781303986479186421377324528428037990386922778194681630921467976068679967876735351026212269626055410043187142606066937768236849425143691220563949845580074435957679043271832147743541483696808903556596787201787581199242931228837311528046292679071139825058470073087241099821979623059126570410576796788521393261428132751205653803559894334849079284277125846815427607117859889035467016001023925642370434248745752387028127391886665102682208687064938451099925914152770638743827337988734099474146721411340699842230364253868899755145249583718793179752854225469106008326966712696531038539715748655943492538914435915204283424466170154016102970469932819054661604531983992540395698409069104499520922646694937189539809942399488557931490275257875286212929490319735408053304384436266337787070015753791569459311479203812477250992002710898858573811495911893333336358401811733993188079633710400077418054596659309940944958191889727174723241431112472902798704753644739795069357838481032448812675042870025676353048285947933773790942638211286678295407309654995444965101498126448337235804115042409264577017744028388564866551839830090649023045142679132331680545978309961850752082396537778763377724263968530486966682325857645461604044926490736176338443639704533790831973563287932499213633312691097592514743134471923442616087242316939826404431160340202664792477168678079725774999996326501900763765519194085181946958690456746245058965911339730393468135487147725093488605780648411603282065828095952207635867242857597898518698124009706804058895119642341563082894689836957722201833036528442101913013554357491194286052872379724418183495642683255810855248475119275291770232314388310770133134686794145065046627824016004701613863266084621951929249095196494213987192737627857450385698113310009717505757352567352669144041652610770628536934206212774661050499156891934344396251242224852105168211941546430032730773503921501616317562112226592399993603399421847237615002148025363095526283607590223252679048814421826854164424302475104479904610241745479617949007911512729225173726718599533128563407614262394647672450848619160434335030454154269886319553198442534456843952085895008882749428638646298640102135274016136483206107011243987535594360165856803324631130120316778690749761203464304960529441281386531881027475568842617784187758774887264658107436974744315133237872113171507843782082543819177803479368022138619447064660241508857154701672699882544490603348915295722301809738589758317813509724180275763112348377500933796215623158836303381869168419498077568891799216183579986032505634632418924223902456951849429581279813687741086174541926873123483205317479916880324213096004258969012553431328805662097949385065206415225029089976120839554678506584250128391686226342059546064824065212266113950032404458391453365085346710782185668127959303786410143307541109891204719668362731756728913354028719358911116409619177172941924301865271188884308050260565396769029083065649321811368628210409359432678944360892828923390882675994898088835462389251365669807497196549703611559169602346500150824929316710782940658934558150590053005681017687167919215676143178914715873977984953338224261808137019701095501954826515898510511492330082989228990778380890449518071503801625639864488422903095423176126881628153846417633127577035473898921884702308536361366976368401851233081860620909348072570622039198096304402059605570764467218844981657639564551160019066247412333952061080536446302667000578216127685008592150340094575641171435433382071370125889734794262689546588287501581169436957395790485266015237753475288236960355040306491053373526950444602662470268591505051537751746007661927261397753814831314291142759177183374196156325121310174103647300215815638774520200149167316203401095227128211500481552794674250444353215471317420218820497804904574025529426387446395614828820943834222488873952484215807269089830903737998766423735887058026357936445742839926255112343277853181349872435414060827624328700127593196528080462480723823154970506709281273653840016230946179214806969309716663161162471602651988067007318834100179901762108843656108905730649428420981326117250254002300196630054789859202852596807351329035129406252004822404735435771120028931074472927042907295308671195707186507348245599433783557067365377824115791679141288354752068062934054106685280666747417938304316859032757255126442886919968326136623731324441370441836199958555693891130224236817468748547068965571634575967791674718783646092821118477345252446705180202195984401428119271369391050495699843842606039271282960344933949826676273418331616667221249915979053798213328136052029181658726486368306967439844256909234237353598595112392937415413009963721996290856266171472237603610203646362957427517320736959003827998231010095098117575257303972471350055828221775495844510369142509227345547165094869739141295869903235005651830300853715733463761326203303178776085360044143671817376560121505964781651880330819290934325163586201271849322649418735284163292875588937036463910329621608434785063898657626366750527554093091898856197139188273243914830109457906452841315159723697879722860736934422876659465220247587233654807197991713959992273395629960148536247400533357044070665306510532173523787457713422485680473763867614441987372612622490053409104925311328542069010981197330373092609784268707750157248522137756858259467232956188031385653726481021274421247203036777213131004480614896975268116111979254564220320207161539235014133062241093528673365353346914543664387917768043654141499410152371810915288465109000177516746250814273782650051748286500132163687988601874078632602364132319782654475834022467567056916353057224867084859692992894729551892960291903018062647439561257955077717837840343110723028601479415333834030432482321308891728097410551916041521196235165115424249934553836417829640856221448000354834236769195006300431948447012297504347726612357286473745854371241146875433919577821492070972232448941580676617445436421310189591653922891073357130959225282137829780584954335131023695225330465291902269160366531477230270203029187551442474166813911679200475224630211823961944997472555512828156886012018841596154830349296461479466588357671392980613245196268074520683215388733315557230786853766863312035591836383435035596135539129757199968682891048008925013707961517032250396614697007139492211435226017021467906954079315364517567691812714819822585438501426104869869724010716216130199266477792911492807682932260086042063749399600052286527786650381194804581460799334279982513994220466510730637705314550988955969550231847544564296808919372348742531703571338099386416385769439420114288272233225537498835026777316697570054569244733006910354841367187004910241982685995292790945917166678619400433744388936075316026652656136067959604243468533632423066240156687064873263796243851329552571383080382910270130217504840085728552532925669353003672810864519395973455642293604092338914258194580100744016199356733780336309242319296043450985410887716962120502420833308759296843877924905426819490345864426130869306963487380776104404014829990600911441331735249797793523819726986958332369648292640640675748185582720892496892284386208324651484033044355368905881288032445035957762930773499640568523871219368775305040288164051126161521667248243533922358727390988734404234791729454120721804502681038869291583009645183339050239127711479720660154440914007319398477004224039385596202082033925561721780886188377686355584080109385010477052861668223265442511452668394058393728970395574176320047941353680644549232110382200472352198062295960073833718737248499126333514880597981985750977994795692557861429039611678177916306633720480177545545991433202571252407114778900827362616439426439107913241754456986658958919058043610326886760730114097134556395037091842590362920450233953240905670214335336843060727267580826131526953361859633043568570245715386961207091047614168296315862570453142315188682375376592997575657157299133654677658371533845840298757586867239828776110601290172687533648490903449809520811036477212707316899079237117187717041308651035057818651839855521784527441828588335768961901322822930389692984846179772854878563657063666541662499368833047491705168423449769310153179628654525789366121249253811655974902889248570306003463715414686788532107127283347405977917586373864833594406574443919095503953540607595534304804836375296044711383434669976822817357288401301034288526836727200195480900637193255846200837554852281708632327064981875139982154982671156363488210868914199697074230918297578612513950958395705278983396229712093919772089415804037898608170126166886808689383543837012534329626503174786037177788468264166482839755070902025922747255345725683691182858193348048522270132432932518191714190245854673173292988188866343747552724636334070461671791799408788733956566640713011860314465079886032172385536146827471183569954462574131815634352564974688229825252235706451632048074094000036671621945866440988519228518057722047824710901937908293169587538431622747310555814937137219340937495568436576089196017289938691042037115123631201365020231924340560357497880355441015555981391673730303514110669696324085016492945714997380378294755828837387450193923794340426830241282137566396066596796076561703465279468705915845363199032021666977327588309648037456842086530768285962578990179098077854844137337134961477856183833490723133286329729833196650234348360821888325760143653416583060271798215725599130517325409479707805867406690341779052178405062011484946067425439263828717781998452581110663612975013367188455818082580946115847071371422637827251778783832890041308479472896791546792308344447562356539844343881664104319438154303278432059950568165968221880015453919464018186430092169435203813497911937217433352478357462122248796087902921316157164760692526688811217381103610902769205958149570276605706658511610577690923697158182307387655935709738805280291513640959430050786779564521318024728392691436096194187274432995129580288519367254331750341416979425305255462798302674361990470413336126639469649165142901552799551039117879869257061328577073974282781622760527621802296647943466869445819111186234730611376122121381793344747773674134239297733986427471499081156844909512418382699753615602654932764643062656860784067577300353897339236311750807990338046839502619329250337365346301296456402721481316642085301190766589950698331380184945970242727115810688259266075662279147537479617309403355281732354424785789529016342365612819099779461260022947097875964775167149378431118407516197068391419178670532674791521722999125611162170377406169617401150679450312043339386666300443801410155810118259872992081824674299904245760736884446124296974809467672742697291727387897490692480698525534169757926720593212744994320257175609066399212253376997492339595739944646633563128824687227517474451788284934534568190902324279408234346382960951432771638807605720220985571736252033713622574711406693703652135243371200922365585780014805399249247418656749416765454752224212177182558091673921919818631898188832491256600723446953389997667750297205707386357337904189027478718352679101948057330406626664783975664056181908101626687360346196242458907119329516644667007777667922129334816622313337744968557071569211141571860729191224363260145211050046387715354523009330094686973823302304954673787852222817602325574903118467938162709134980209586755204732928302183242511928498143424882703606822139157845159241785735588092308367077812832371454593573235733313908857559734095288217721993726190888029941567825499799670281371780829727237870048841753456201977860602265873458031861018012538108397656356898593009922262319728815472805516260327751626244467771663612002515915519717045891258736878565893009587673427094701127551110864327014057617296344287483941337911114945135385623340496874461922920658888233815219634388936302834370270671082323157673557867059911906206087213354884393166017754475861483671492673693352345020678288202253251389901877281259829117692461829354016393222638939167592616726294781265092490358762144737767439110373557037961831083092321163903959554844822286251582771834612537216463622807080488811140199421098376535287362991367025993893133153016478759989063117433392567115600038393457240905736901548574587892602785833805439700759607504463104733728502346754513804672106801100771068064722446204572071662008208331208430657945859279625969555558449015612367422777022194858572627107814602017593165378007480516720357330289850547551846087764786204821349295446437744986409133636404311283719514580756828381270971082912075779991433447836174581149867026373781204266538164185306305823435240466587344727382115352658530992343395230275801852927168130185892725811856312759368645493694921391551455733741152728683854150235642094312350971644372359411045782179130124729252550484598989259643686771560395352416004039719767982838790599102757425522001919517570853497568409082110845787738087762203982593161531421798643201203977873204080329797200511166434524075249328952300748168854206951451302956531740723184449978955980147696762686392718691480611736946770989538736304169624828011635685770937718993140898731872809086115857957763685664374702845027675810193780854826390736345255833748869987122020558640584080073073171182813039949175788684619632781574346651971612924418066529659325615595469613833282474227005531278185407085236979694601631257225293595014665892678187131179098419269002856208642050571883289334421840095982785406788702743299462816543688144591269613805606414548801317383991312261642387168130423749366224735961695593281181626577023404389012204364827004384094088215836029518205773619670080767310514510564695251870120369321887031319789590573380101636471545338037937715461580223565935161263336105694314065935984490094514262805500657275401933801256074707385579853234234338654259329235402072700273968758550387715036985050664808417240156333778282895184550676511504648150526667269803851800599208610212141350245773680088497378223555278287099901165368819716601974142063743302722024524544545265498764094867636254020055437168333989718401123984890510109956340319155316344177430328574648966759504352486027170882159705970080919108993433885079618576821117533747215679878435634674362396903490794312774315159511640836980963987158236226150184052271828898326333238634678963911128891641334319101276439605241486522108415858665560760850310606517594085995073245946146687570831771543651381645365503492210636589826069860836315402484739720760860770297160105638356319605515114733539408697394241249777956284724488441979076734311897274299263068882363325819457244790841775167535277215863033284781862422931450727675042250460986901332003541023804767472685870656577221286522370152961915785912943731376341762425230414620860397454415374843307391644657102264085240632791627419209984419481183944711570190608644815060954447305862051291529612248252350892514307170288751341842622030141277874082162513722880298670046342115155126127055822683323984384098660782689754969113705512878101434575765007768364389715158102896855509062128891753448633192657974550800825341831527743927154542015172962863018192092631015655661089823912002843065310959891120704423025100891802428481423236202865033499838332884190978914435685563898930681968526768882501216657154544625555356086501358086440946050128077721434598021457736226433038109187160454602480338925279038157350972320783532591745755778492615906863291514872039421736051603867441127071495262140501011289114572325775180639972195395810408697526377132562264991383595519326462226780451550531111938133960915595336523936674560623969879807307181179525440908656937340912794490790664597611022319847242387083128790268197143666571030386260564980840223926346423689593899477155498383430994067503142543877435232431179989394587926539891550447102545828374333795251070203431686298822271858600190970885786864165748966032933640015606794473746996434218082483240055815716663906949796334671801910686411650131077597417763894606226654821394686313544216548831808253148947334859660222730883572666797842444938610843829572724086579012931840342439270364926001524076102035945178731079800808524566708621408789974616248007953610257882165639490038524930297415775366583865154400089897146512139717041422822189916495892913163778778682472495041579787883337030545384795772853516929824557270295086705177519760737466129313286539141557983491435283559177883696016008237569782000356994015191407436623144997036059271739581659604204601580878154320971435440042119552154578275383014940477949780094684229157502069294521163783180302131138622521970553652656833140452879186299001632964650618655470356077156171090899155990112739585828033577505418650266787835606025960034328565178264489323175757347893249219669557757449677910284827585417163336930677950829341450836712300993562421190029298632472821980532906262549510206314773837529446911222039151676261221748134586772584740428085532900364761790426043036583849782998982526575130941339661172780289154374191685162723258495271693718362085745059431935637183368781871265923636550182030850025567973917682910765777722259529010849046224457277153323302843973281667888703343490534415927229781765663071117622470326388986232995746966716914117091024077553347874737394275785509592375315961376520208458220032072404949128116339893943302475391324958638164929063855749731121984954606864614722942939180747355555719345851949761777554560672399247079842229820398973362890402365324038028888342051700967446863269618279898393659943749874978062359946658852675896173250176487399504673806876328044995955040106906083331446169075188241952322442568644960664912392606182399294583673601945951132174290975767866162590320311632981411860528828729875796027626820642874567989721205954292075456296218171077631857706049255672326269847925148314551263819016887363175627784128645110087759894464999544035225333121186705902249612281281286555999970392047198085703971956061168781095270493671557620772026396588055310305286895749056784316465268859267725634591000767202979126872606695181694258207266116909268520315476856598030004849588445888745362238391359306584079063074224940968332227365485163094938960209616592032946320873865101226661721074263487577386207287028368956220182425936738463235232465004835921430689061427753991616709986420018136833065810866592403927365120594979034034582843339170789361270957603794238489517388141927161398765248006131704377155287008723272033881924736184543620548091747248158824406733566529028831856474528775237190304055255223609828691020786972030570836730269720763552338351947940478609902921104917498100505882762573898458721382455886249696029307145222394739938037308741742168714503788448934643440452681022193415696218264210804465955949821440883043165185294792485526752351477429122675640525198801658392867177592059164716972740845609365470689491485889594077704215015729924508343753091701277412396068308726266607234891196565748245642412211704866979885897100543411768897863686095219203338766578116903696510283002657496760330717473498840183913609365388170820328120579570078557901214105891451270671961288085460324028373319557343542513881162005128217901508541644204601873453319289497378850628879646040333328607282730168956108020812180424853478085162899169924344486999590736346147119789464365045222107148307971057334499330848074242810380415254773653631492589092962400383453052495956491894581676363835695192192975581378826740620186389587193823987627515245901539679957931239318730397043922042903938383193536853083119913191627715387214664777256698739428847859977692770318953557460987542920991923466848898104976200558199845386455918980543638783688386420087453375425672959689088880177455738755546102627376983005404513957964004599830319625919442808959821397803074383212349436032873597843671398312957637405397307626491752521378763903590517067894613445959129979800404292175446413865121535270264685297041019678744661093453219187403513254545880477336433266184159384755406178384875556282419921513809225851335538555903029498137901685604713777310897389947153920173978083878671059108001146728566304566777351306223863795107714954966921141676614754537743751417786060907437877932267344446232964282154520384732776218451552605111808653198666443428537705897450204896049519299143611643001775710779595253047831574231656620554915660329984329719088420632596239350196565115678494067556043124187014963662149189317588065928556610117589174057744624316801166185566579292758237860945780482302742053921581267694908332799857123678792428101423785353363279985786065253600904504461977324500460384173440942949360471368664745280684506496599278832734077769807047929208922935655773107412760922457953592720493794034041181484076038592879065912459666406195764002425008046606961609098243897815645957011907616133019305700908320188544976733462490728552367894394118059241116111610161814338684688633938188189742962364265357952042963833777778067264599203851170543473203586317698850960418043670487271645863912216014083205882393164262820436672918382093902486258403304285070626063679519684649486467185988756356206883296320432084613336679755049749022415666183910286030759120020902553353684622378312676342465694455545706610934432983944849905139873658165102890608898742403674493580982538126775672626805625102763905576074831584323314251219875187981555104242400443859471882390681957346065330120506237818977619388148716103847654481634720034468939549218217568017125193618146341727484362676203842566160465022903780568688049775599741553083945054284378889495463302825306840127751018474679726032328315214320239186145896406269005679225210314594932613029334612545015571912958753813152566612689171041326242342453892562404102941208634614285626404011722325381572622934946132944341776457932332242018784792324384793401140255487301928287939538985711062844053774921879220871094949557922036640313229587614541431809534075580395507241459027277212013001875636502228083887942072900279408515071338353680106680891588711398206808237701857597419904971970811596825631982976175684615581822912199468874911328901957007518793537130673391045536241059764767789064603774851054146847571014740808711631964804136299271332308002956074744429336007320020841671362499311669910581617643347433105310415209331303315282974574397703195332124023970153017085482851844584910786346656938001428455454649006806982666549918222321863841706463309185003303354404309469117885161599442743124728126677901707259038323803375074339419214879518892087782582097022542954896796439886366749058292698254353885134001061624568987655112176131979558402864914207767207096470563598120284300985827986417255864090758929460260874476597426318896859159548537456213293533437886587238148857025320072601708769639086257713838228699790459312871361267059432211919120621478710173055439958589095450421313667224269868653942103310579179414799814120686314065999738810727235629407074927045655688780280358817997371185472282100438889064942148950022956486444358723944016949358492807706602922851546236185727104840894065242814763665524163581407179887034027053081700887695924848912093992510072512053696655052308985085278339121902189922024757449206134225899533519437140296628877462104045844409512776825470854379249686877491400101152458427972012110257901999139899691038169673519972030703594066984463228619856327174475805282328414842430214603532642086441456179138460534744275739885609706568623764110443715799953575408524617977485112479015259741453876065591131427943993011662074568509243047329097037849327571787568555813698121198251810025319627836425348004591495271596445283357181322299676562258145329086683764710883577492524511870319579833516734663822308922930842916488133599296891979325586255729682000260620872978075170763829191244035727645431263852082857292272390667367746607737736855598123611052611899583313234295208734273250925899697365989567780281213315496421288345258460410069768979028867640086383274348020292789057099095027433667109885971387901131016438502375937926383936031892830869251196927715567947043108591708818033923698857190625428773476463549349182817760735262764075802367462996616070201588231138612568314983911029029608055113439309271304592462742489690186215161753107647128984730863173382957433170730096996451388434983152733835221130889023813826799796729148218950410101574278295329478057924591813005172813075940829852116723066221659303950048971524469832133338224551331226789467889330090298841415927678637376054726083769762234218905796067859584531126796730175846857317723586696493274495401493215198045004028106036384889152751445526337079315810419977487425995352966573951834497278124718658141171784436358702219570125770504488885328576706771986108482586512400682300875911948127199324955813656809798161917519098764691453291071542504383004545070151009637269832876189616483651273773538492968136023933931191152214066920392923427918595388205731584733833227290015947675402659806494625235623559276933323184497280199019166635186548850636696048278398653468802859923943105139739479200729699047079783974729588811009362801252515483895575704141999000692802772908755333835979666872730413684128893756471469657362010111189295212675866476693053592217820814892643847177481654312645726549803453268673225936784237804196086332823543513025560978129171758134068154073415598584465613240499604371918218713659298935076201170407284862072330490913562301624402645425948900937464776854338331904731730363143771681345016746887692201276816067877293563272517994761838616327772345405359105124017418487040970883416895261036991696181341177895016264251624883847289789931173933674171768537369941048273728195834912439760673994682892658261793618240418778739433477945776173200153771743820649624926296380705410617637605198121945722134694783871034688435887898362534253373069636513652681358534331119917448815011784862406003401801274331512917247672257443607242239821860326349842809860606240930335920909993168116903864800517542574351972595764983396349090322626710031963754436620175075036591068255274759706677931235458725312901287794836269347483461168041580186282038470880873853092344558673440509514772619031131896504350400919676321688355217407057306287909273314886189268197002135561707236254691057194173933545158037822444278423152857186066832706813482624369906792715772976643604370968104464504511683550853308759016026459499190515374763576727029705469702735199873229744115823947734579325458167520710668266848580604825187273080147842227757069236113944152381940310871067725258424890604432861135235276937988817672975777829668510248565872420818002184730512968604289059485192784682946641745714587415009745553211358928269322047317736651839337701573514376274399701183869311912770924775103146737865245624508904249932259031868467555904929858790982242333608663421138810592328471491196067771197383676755651811327162629460495032106814624177479996445903069745741722564971532680385270207945107492964462338793127513615550902333180200657485253135631305561291168493896732193379563528397264925655345802950846720030082285882249263115369391769727439886044284784149929738305863896019350912881820346903796011321286186001421670159704781036462177222446006609486363898462328091487992531022765942873310753419622323142671823357921622876185646971777016370134610917084472655874832242692634199092468614443969041385917487161298246168010393927823690489821593767656607724301406686056620119436157889678031092088079472591018630006371408568455985348103491548098379391106374598829674266303011490183065345449976073096838941151480500255961911266981583261768245509767221693824500132454955515701653816378924170948692687753737079787043351220245514297302871185891945005963130790902216116284044115680561282886787302302613515390481642794943612337855181099544251332244454042577037025192090202014195261710150215925303012863187554536149275754342082574639913587090801594164382575076466244063402511774167425023769425864633156712709662123396595507581608839085774581101996049429440386338515659607521630264294195907410724529875214933689411593262794257956957261635793336496563379003588557027882928302308703832132228601737619904352900411083090325980489852832716541681466269310567070040424299980762928062134742805279859650112424320700183539446999919748620303252598746368816137154450288187062986622006651706570948237706977175171931058482776468612766723425372534878301440889912286516523236915541914938356929045729836812582398486524953528286124765179431260770360443397546655575037882210653704412392640857993791679188399096631107318810706969944430365187547605825672680902511228815257347736969315472110149852976977027434654671167090634220034823782886802540873678267580734728266286554605952590055077740213389197720990631957956100605374124846013914329307986421022291170870995718536148678980959148538208812951843369725115496570551740721272307008631687339651091553542076003004952478155150427946545850343973025945864123260923892444372937779137791302666787908744195417456869265307915728935503990929257381182933576828511249449883307390513764742681986577021468775921811475682935096141637247894178997171385031825514350748483526817626216735436612096185900239095347846360278908286741839151501990058967681855358032188577303098938893047531140934991646197398520377857125248905482172889515032411890083579781964521448005026302312594342582132933750416910662681576032152371003526814365242406740672222592694778542194498549968124927400931810413861064010719548120442180159243460894473280005911956691178772976758631827441463464812434788658725261498920023975745343661841464197301417313737227347731165127778436677830934489133230597562226762898259336091030748567909207033033139684471603674921404286904174393511261945595321007469299037898839003261924710945831473385607791119422151338179372027667399672787257679789839040031275100238020764398354615497944395078584373514666693807446092367113708333553041628922530787538711295562109946321902592611000533625156875771218740856276612440738008842834211889214939516152605936040279156402839302685324938080233340095754978376776148133291784806065849512981921167561433874059462697523148625445993519000961691847151314968041767659474137602297211876470832709517160435807552908810282950371456035695619491173021344959239150706059673987811401761848037459765686631957476735243051440998057143696304507535563014753770661015059562437614431640419438142990211783924421887883847777354317608438877670767625707004557689593937796859337304881788573636453264522009624449528287905377645583982715255434872622252657340566677206866593269970529491436677057358580621223493979401547349665337256022824820763958287549197783190249422471459117569296935507580174567683913674462672784150269280772001297514815821366638037220071654736629291084092050196476255919932250958272935494857958874859938220940013981811751502691996776622549132636226046904294575798618336811727362240160267644612125438532971573494756647451839728270464698488190397915703592130253864155987528438612730067160123848886518556444978037526171174845382011572468787697710170940376977366105141028301337893205527431943197296841030531718467769001025618633844171702486434151513975033256154055862066455422475459820429643235653013299745193100193355507042924427065830969933759359843286443037931459143196793876132032420701655273852840665093450920010103346613126526451709113770672483733135959321182895801509818852434071044275629492568797859772184718447794616652685221990651467804791796672981490535307600476963203714111294136915140632000317662637337728152353370576840082150951550749545005072433851057804031157633614474314392335495912866365234628984630521282700070690051540504223209198963406043419047758317912222464369868847808311309086685964601577939718614879513186910367669060340957450815988140551362590022429056131206119057101131366160463844615674717517097989427606170495403697307184952766016660840635754936447541003603409401766740504570190340301807400782572465083509570413101061454689051511213671585359128753412232100935737011818055131562194498626278292128533680892003266742430805856041202146560598442161994480812801709211970053452940658508797726949433471241263942220764470923109948619829553483267712223146591769991113023629433088191779343105172478169316211288275938880802310112641785636223545765862617869281547057452460759479351322666044302472513124974068398409794884502570509097057813208235685105545696885331337063669637780214991527128072257840589004956334076642382994409208190709599795604494081069382154269420816472655593835867720536613619277051645850772586568299538096995988235611494469972371546210253300022821693302006559059402462223407628312798708320457771501977023998612165890973044978491701191386187879706484577929259836085969018174084798549656993576030967018158109327219729197472936563943727452576167869374265385272347885404331714286591734644220788283260070133149182961482579926528691843702331983707495130556521598051709460195007524334908051356007101801020138941010465812007603791843974942003693968441016771700738678895649370299439906528536671731560759848669918466130565176656058629320007182557748801258523148355955939812824953384435976978976578469393889909292560273099015448283681033486246012602796046423700090390176546386057053344381750791446429492000361164581121548398774875940868776754750704875043176572344476823899843459392028189181701550725326264872814997261398113546915600103555865965807060628775718602804955102672611867843042006977782792719806810577184136922306278729061223571377443558456850219413512091874065732595961741159958470386534999120052797965768806395380935457432646328924768533224866867724470691465098382678319496451623899534171448486531769640222114253821934965603156306248792404915407899970213108686120524834505936899368100455221244330596349575207413305936938108089054510779266390409528862166247746511720537395057470682335427829989756406832897526378274907509111872183714079924594779560920879243872407410607934390447153358878879474241934593206852562236836552583617618554700130883795104093964727474829569541743788258488497108506044615349663223684859279167431516106141845598750391564530308550531676856175031779579366901992191740963244979746703455130306048058788394415079516293748941104788463139638764251695028560651952157059830352831053950875433729815910110689514261116413761083272298920148841521790658681339698355391026727732381994388966437096995998041569992849742598477560384922947828142993049475789586620927392988131587359106102296235435900998387994110532356362805640129344363813988515654788679368576447452865252427180179440162597882910048860608662468957425414242666545679763541283148009133303118203484271393529319575874937409746333324406289321465354548170089587044467584683449076721295238739855298431190974679913273726117846443262573301904895889709279755943860064344519550759905055768678456867891731702609255318408862883316832333706884654766599443084668284320629371042783526953612860685568148837001522280646564878644291329365003672536799782522227060180648894364825321411112737211087098455647803723916841545740398579547992616087432467999841096485092626598498072725489071020565990342408021452738319067195601580507715768084526840867489157064754343850036808589190918317218821022008799744187869076202059811280798814126816578448097986817341940523033225820904769711485069178188467449381956865811079107817544373650667369162934911884671288583408986406716568038172417688426487045044718933084333052719701766295854123409514844640420856058736490412210286021147263612313828169631155390461658026851699129215387909075094096053771141950672478919501082473252333893110707146835642257558052188491672553005036616986833877702853304706301957680608112597937263188101871216486427435798702509182897729644869458685860085673884600293241103621150321275600418487032847465158693456899957105080973880167484576608136899938202546166852614731141271603693979766277826020087417701232838191401507302416123188095785607657490895217427962028643805438101487533940341603274378341472048018567706675218909522110440819818637005250636176881691762472072753541599033959140020825315282312866545876817252185277359361855070916334989835988483330072142376552752082107720405807481530623738018224951597638916822253819909435386903894270155303480659283650455572569644003643953941394681352279974687561296570376828346758139272286801840880667200439248112362351159395173747207614244113748599860487966003943275616653547703029073417678535436939932909401220823589540326568902544530531550893009055270824584229590035100069425536590935096487050428988325633826169430856814355679783799290562260576687587096856167705419855918976716490819547177172035864546133559607223162113782742754733777167675356120684113429707837220442491359468318818450748832658106063706137703030944771063487601778998604671577606150942141076808699593674077918443593429242936044878486924177051018360459528099185892218768503571255734560105246271822010245746669917008605434505908322159128432134605233806116591468022705666922197729125118249658546052382865486251925141242722766217672965080542537226078447321366432765014758052488661703306438187739126048777326506997063132964050124175495210387336399081226410627872399707925419808768225294653058729626783781859267741139883337477631849894689605638453239362238318592151919516306342277601616002130980202780709238778237450165204765505836460812091573343304096888729531050219461034031855400510509723594909147380744853293183294672516718771594449496999596189028611865772413887654397192451019804206755670846959624279801728270609134167149824974247594526363741529025208458085172147679259234261123758184616712864246835119135102199402417008027180645930018107365948947541148575196102463247306737825446228668041111158774915601391384992484574831653634314898033652545238087187346583564306722941910471342300333843090100889455151858671318817507476957270879182359281367039198515964104845595658655663194013282425930109279727730997826656259335643331198795675074099798981421279954677761069341790388763144589075401407557211167171112575223878411798822817730429836750626793184836657041039760313347482330764913925560396540568358942365320499540747087848734325483299969912741575548994902233239104150844442443518881685773014942825826123712044340594919828195045961237072963015773282566351706046126949630654682642550111959797785341439287267947915948400817616596416301562617397765030473100468657352413312753513683294855727142578987724384442444411036430828175522135992664064114024953652151140637991928850203774445870017437046601925551388696621053625989409397495974858293453000917384436210489842220898872462812498638705624755139387388493005545360999255489027676777273342942815016736422313148762463178427005560069249196903293494958507221994542438351671973990876386890852385260399667285112946133064488478913933272591012101958653741410363072389302955283967103848693499094433997481098425101395241765790462679402795487131810976078203458952653648549929698543129730455777063928176261133217026796876097690300183939632168659334794942724505742568324340079483185863862981931361135930357520799567078885600823936436717761263478631397131874362648287965222053908323861999903238393453278887887934324561543915948530204637078317642095025133784413395467167329827686921319131068335152564801859429198478278073390212050241765165809707070117456774369451790824828781280872643038679799988921173543955769215295824618597938943652951001029829847467291253105009551743109103233739845710213838367860239975037197010488228121353509037107497028029964876101628850695846074597673705805825531023875500453436991863919618735789110203692203607131523437248952796576695548982371126254156001091067841783488806605797276231568364578567915021924726615154712761480062986349388527896803248555771818672905371494741489168514051375925436752323565950915452570019334147620950341001783793865874363347423723798865158309431916466975837954764281905202663882303653079707743978104498848810942193657496096348486228383229212686668640616437070870023133963544269851211292887258437290822257021349302109060986970213538335100947730146799667963885452991194456960450131452611752328694377447633373594638642802363188621679571461010118298593670644246962249459282248855855099151130581025882211502791925412605867856291993672480975303242257669024215400888103144957918185908032176844084504084933244663593504951246550375579830248719496905535773701175365857434987675249054571375294535016644712940816834238124024665842851243196600261731158695926633094302008589529106647608207274351160731783355779516019169404269638215023888596840399561077656319402256040586507513004689404062718578968561464393810579243323509289376681501043014584920644577529774453187965878604810962613846641039700220565901274883790592910604403520592717072372122963489775033453593803526293287715057107840862788979653388983855648833258210143561180872010015988150277659138167321973699150749270840673605769001908934249040414210466710292119501801664210659921373570122694691422874543143712862806930329604979595747853203552147483890387715154775544719675248277609089468530510776083604643148117740204825016669469730072645838092491490962860715948195151828580694022634321790264138460160421324708854189513822571175591869716605129391807992607147816285075454034204688339149315515757259085903129648721823927938978507680011046109899011565667513604754409634047183922193520939304311149893022853831901094419398875071912173774525493407911276376115882963436512453682244908367633659916808462194790981169566066062305966130162787687647271072090769454590290427236669315163617787363461206053568546556355158998572299334147714567655163798081699463663829583031844145664519992257419239928568516791477043482834601297372805468341337607190516866087587933125262023195995133957251982880018641662500790612300626322754553229235049839228330242935084580700251332561814425132707431328356593478507331926788058931097048446640909274523248197008083932226574324915695871595004149808588487922425074407842503898104140664309300603336007638455230058867685743533553004354059749681560919498955826123466905030142166797804937634872640459910059861018328556235737015335148046693572759996298952768631490486748538103816941468126156085542499959341702679384857810226282972647793593945499253750655255448031811825363110462696298495859024597115861755147868219119634706334993983822468460944632811301960118051839570206022938106187527404073122365437529460412646654924105796969255223032640887462697766436674866044577853769810871119038957679693232028815123830961697039798213370952588920898958037131629856760944980896992179924798591755456635452761081749033443317758262808678757144199831782441316669966001908263108682800181739471679488593765008657681134432883854842490221803737181314076625951955952306944845456512623588992497660348062127524073747253271978579130682988679765273483824809786496263150492971592039659138257853702778903672359766407287070187793686587499556295165014006926367930201996802297718452093855060834213728353902017049721862638076266422749730127275112486903855686462455347308603654789915131657117610324405578521274190179568252848512110172252256629074565989606680667417709151754490926702066157853045938326161984779376753526765754961501162092698871823215484101721313662988859408477766142944716638964927201614622803952677105780047853768338804152572632380374314489317382818925970163831227728744680132566447840232063922312912008418435728978558116108260581829932805413054690920272629987717726692631244917666192682925524409642204874854297424100441953085618872251579679836718229316575213571800884555873550631246166840902461121753544358090466764824186937405968312506953924753338307688726477293345633859421820211358012597019140433579141701109775655075216299932565080528626311468209221321569617850221805218341134583944450991402562980661090328372228728861588411747564937985042001754177457380918046374857707297887326643719311331857560855996974967490777307284412859648088056949166711384986706014822314128614168271390624778191209637534862694389926004434047002439632189297488132877724830053494039558850109981028154699950217793198041849356590724415636710643331804691761228876125527233851136156805100521329370102615008893647954574203256750790847559904742950645698339265549510511190951380302820207664392654010335262441940595079458301227354979079623890384896216997574742100273624823954215390127653225367646789696461051588169977309084168584300569661950147815934268129135745957245103867939893154920470868837407596185968237860059300428049628574592951342855085531940447188634124360391067273053541832932867279971451195319130503296912258282381246581973353983775479781256527168813100435707033844882493838113310377593423818597551389089581551851907517552331058792299674544085117847089855497114468812428946919601253198420452643683964027059831829471182065933347510473036538867912924554952989016882587754692713520259021909716909788244208835167016679094530451751471657250950311933733826075420926979562417207849876944502799722030261671245385864447813550757908244458253278937485249752288686343242522204440238747862641389550189571414903736038484627651320311980584389872769414154768749263249218676622826691043215947320912028757453905709493432773710261933175138187196839668887486943319940466063817756602583415591688015501735913173141607202874052654189250978916291455153513765734014537935661430649607904770220234894278321176350075279909253126558606504774545926659026328681501969937714968332618011081863377267858296193627756943361679895737175861972282166253702299851735895177768349837819924179489058551141867906004996185016664915822680614276572407734527207298721309391152221885026218880751740325962280477276453824110158326746445482956251409431749713028642210297065693504895471440168406936331355936028272857940067945253800449119516433140554072553518728671259693060085377538979967332400385358775428194046441644332435266167333126938714475312007878348878174665066011844761310568823027580157020581320380533089215071822361679644768586618979691318730737277504544005099578882445443645741885423239739893189835840284340615395068658177036899024833805612850945203177482380104455760541123188158903482321141247107320273169795356113885260984465354337864298865685414786834173641048078537509726438993508709194153647170819887037761102803264660643912871924438939717740666868400830587307090918306610536924081188181230371661153237958314736244456996183412397207064893815336266132927899612804639476281922712980526531873490175545821773610280554328454744617078464923192038624935514870131270572518532621669778806376370781017015181046663567965729971038868048181471919729610404280718561623662249656317804813233478945099649473039705237914246332454780459905259257026667781140516296153293440417481032955631607579161283007963946725672695781100541753212480558688835119975649671580727932530027943718441580139429045316350043844409336526541006051492959060155542888431451705702359796149298791151884359817873279606550264096615364981242188393092557952213913629462854782009068425607458454030865322943640720237839508372435516844797652339286786286775237416416214155825049424515719580128143737055275249668137891691927955661461278391999989273595160194025608333739291927814922270405107097906755058336919383541110117238567026139069986310039477202291085358266035850086392586901233212816699176624646853061631307269515492867374914930735868292730662671695558137731387473022352808070673757101897402649583484967727375553368734087802724931329742351431834898890062472372572904300410307096268456138324457885194447097262883499976248877331315929532241360791418216573936578914891973994714013906161688810805644407600315056043230861588019935449890104336467972903009750373912137386053055636523407264263156854670004967468969408482565936499133231500465410785535828896146836887507390680771059301705789254660386432146208393149327056490476909175195910347232401906778340700469353556106862358972543572618449326616828843351739855749517937859255539236545161332933309806615879619937430683445442569019948782294123351086426076977921020648197442205398749685727767257346105520985603466413252057687380674834931091555464258851546638887582284518178775827955839357392147266297159471391189623928910034871089678395660268535929878390231793830321851682799660726974245943484232465335397930188538478723307864324882201201049143581726185226904982357598989992370753900298149332477686765267342402529225702319059269678756781448268746724345093721128466575900473552311377153583613808523520310941013703192470559988393511552890957593988942647355399905854793120428701088071374852493571536540372633299856616736817365408491443646518888263336910386409333015917995196651890125613678463658782304739875471955691581266371863798873054954161450706883029062625191973632710185122507149165065416634169040446131855834179658794603157798765176242592897183215471979159387619926845512953532343168555013321975421833497562182622627233805717944277955555418236777772197998906802024659083849897005312398828513573465958727365490457537141376008687783680044244930770309165264515672200822682708738967106554203645432943119348464335855477532485157673181640923903914303366102233163973793485618126903767219192034834173161470258535830237052705073731561815251167905996864283231285418977230701260654514029519593364976311942731352537175832390191614841351108327992288996655684976718882242259362572935838872513520065698937880700606951997177273960768980063063402389930822362693225646131702523747386373424590428350101299586590268861746635566496801688349102034946622709359899497790440442799931735512356674120844161153270212409880062675625507805844124387324646849423130039131911938735245001894000848860286042133403557843175556674995577514691405823088413225884820217178139570521159842903791881972470043646250615197830997876571760514250061208181562368883980827233155145692275449514056618970785720783108042888149749213306479032277769511502612786721791380461282662308367913881951823716812628808669571830657392081056128353616536560940751121948455613754656161516477636109986584951862743758304936344090293149062033739595215327906595571884053030792219587643742603957976682575371482675293468514470439753927266531302317221368691685902841868585003763769944645393852533564332214014160156298797738880385973817974287853597271073251082352854414213195558480604866622146950864602534184632164566701247428283860093727533360853378682550246201287035644895915627183072761402968271259529538288128993405657497871531314724181780538492704466560996675404457607722784812702228571670225350105993653984767319747718232167867925473096758840058762839268822702073609046183065882235766405493589767347073783263220568980696485200813780872012638731756938264775750488147282571420148250290112710156590920166178106773972823465049260410549445215285717764038076228166370516154768318852488606225546393261847332200367409928408158606487970713007856630414844118585975104970140267594305673909394374601579024571079129028703958373816708630251814574122601829868493451825697208614589042458440162000460681674434670132208044177651886457903196820130398145024767195924068542525261901626941765253562482260586427172679022114331673315081387918723573788026444470276708354288301800176120933454985013353893477925424444377496927108193766138219166809733313050895743645279174357846169565245700606575217948072256437667910015317696381443963735759480384780189594848147886965231228112191085126203756663229324647098407963245556252100030777320708599562047663198748154593531482565514659557789029801867305089147186286463656337984055760363788939113029474204822631924003583469477243313294057750496619136101334973027593513905117028828511294998249334305640133147221209752060776451142712498539691680449969395979465010637065626857979078334239647044696209569705281213213604668239592421928391592241744172937270590863939691734678296213234588558078726519729040289442608833367055974317959619661927659690108092942776268081508575383532365767135520994064148640224472047526546720679094270486833799547460546199738067511402440428102294326932941809522098487397693119384421339067819418681609623556660781126895472759353935046440161410740106890436734843651693050178117827595680376155324965455431200112692401793604559450632138742476344440673618113258620635917972519423331352844315880161052638780586159659710995690801195969486187613498386073389029252349432828223436057052635745888841861753144063608675242702002858386403801208154347592342211600373420555413754357184726293310572201102052623453483882787148164185029372846366211006462819345757298667716412132002165320574943737740897442282459026602229862255169772981088608639885223798998153685305322078333099392934805134424100273938113981140949457890142084084141669751847874179572215793106253739745370382439579840868357469706303742276512448131586485885911586394607237420772981733508306964945897772732654612774640877208888354724239663571071720307549185771301085493984527826185142027020891967499558918897507681751521392460502626184016615101011198373256443015942856678941389796027448370067005947771886872085053220149559986213165775948638199232097446316281807069038149573428311237569858583004196888084797292054131583144971130849543671673317706012488752462494826569342603836667164901154181001985968862874793359818044630100600217041928568154993049457795189419643998772427559923397782840496967812497203679760591346900029800676139104121319377199011144584466146594372272510594914910822152371639849526284436576213124875530193861174547598105147895702330668225169560222664813932661427319347620694724160960149082242395450283075671468979112196180699716370534891518568089881758784694483351787584221398139648429940824639964831986892983859970994658751913319946772303365832873595748521990110763964730973373668025965481759313708825884479725143526237769287102367313458758777953724849309781689668633759434526945659057516784573616913874360202267746844568284524986405884803544959086328085914422583472669503170136507477241201555271960608965193403067636811173029524192664908226196644565144547639930433758054363036039691805128544858342966213834584999274067976613902442805489570136945987191102852917320416561023370230027092584625091685975667885646548784001213052602039655831271908365060922638523360440978256067559245968569264489271767324692071185269013779986641239602261913761522068763434876964900309029565222775571388690013928759013601327566458476586107875489801393246260939568746544887487888831667375316207010400512972404965420947138114662560737789557816078015396536943832154670696072414965068240388650727814479469356960835690989333501561828900968250695082193009828620985903533075478132107249297127405358815843067289744235987441528211206778479330978793371450827647734142515187576321658147190263956255544076491902972719265546143513299083703105904291602665441367661600344693193855057352362867538562408410799989383446720184097243087664903266880013636405729542075263805717426437917623258468720099302677435073977690816714382595676103769856122223671140146478521302213134938463088792662528593756160484972773591920877264775099749504619505606939448781274352191608624498453492143892777186886783196411214419835565221941935648518161456253278837574855522355628571393698246587025297181241344068156219432459629824910325264928726407534983445812124839924397734852000188488406204070749935376496406906548648574310612988708494622624260081988126984904194675384700737417473038076664125303551014898461525864769411865180382799326611985839826608945029297779170413671501057578015602886324114889179333505442939741185412507864766074777234633846351334013470985920162127725384710022521304114048458550511919392251813811310704925948197235231279857487836731440805733227730936361287662829813522037749963600181124689248332031248989823992516278776566741830854304065743776871363560827557328142639446688909704779507635136305591965590747905443930271963369224410610877477187812963891000423918366438352176874875456150819911945749503183483770292263743314269055237935039645137365965470176718162425922900207743145904362233832873051287766606995606784672696579871110639404120461807822293430690042749601636769006364680691213543394423007272098729917980781077307415566441032734121246284982044130372994972472810372266846085048611441317107198455872104328926240914896803735249888033900420514060657859649576697887616644934161866661684133973568381449056793919257440292671315864974033177060404401864639453476330422282949586946890073077291338840431181719283001203344301590131868515212729718053214229391847272207109343725921987592160804370699801865894017731324985367772310297012543959017016078644217931096490442362817590320510420771504632865465927172572864400911645031485036237585828179949648261086809781378799868913248633302030539746702345535553069972474158350383312855209959385926159032053196268817414007758576617416493056179985745763910403292961215405470361602316409305282182550707671103302850092744604309862319539357251975278868457008969936805888961009682870468730717419450647966784317771616929997923289193112895973390590526938735918032964171299729532769807673380583661386180729425560952281904679398502008421447643265742490969462181815864583855595109174863373065253970651349656048024969497482079986374837690703593749566967163386138446700403676156628086255820872806714341540749167259628276982700399515096333197088175736197258887114390879815401191929929898752634992946169386558288353557503987471731682236723626710571600204338359100833899979848950166784105292257741774061871219828440913358761462063596394838800155434938945547550754801388443061488693867133045170044336971049621503685592653301479348896226375238643557018089557228156655607611928401412576626397977076999865527945712004018541693950029588996456031456260468194877737465830335059597135452057417864475955286839149786723447399377244956391198468473748373832818687800974257622741393328594730974168235657790879706162625288944958142962652826641662054054065469776915149416120837170435220669381943601784256555369569826250129894503388645048727237238344977339355573849742256841690448554291480347970868509128106632945716888005118027049442647003474446881297772587710578216640229473128119002094757491414410192329423116226893395466858492482190614229826449967434706258950814358811990582604061735765840456621187378235165092852216593123876938149192356191863053610602843162819059644937153939882458875554856243623664340343194960451472447864990616696436078562172901213623620328234277401312719609334433852922108729340652067620567985948242868790573044347585622646930339472436414377334183668312144411956599615025743380288082314429447268000642033110309241515471831717138555287540260344320165320482814567501744475561265120488146065403058327709535673605170736492894182670692315782241169589337241233368616916818985898965139765887641267122511913543633018466447521287852915113127409507336798156386559681028039729397533253827711544691580597225659845938081456648624068822517907716813871542669124458233822021933954380922169524969619624497831362611250912509252254108148389905841781865019094326214429117784893140688184450225166098824401470779036045623700642813904898915773496775209800142466937942752026712992093950161188838766693515799143316613267470714426912858034148595949101437168933308398912390751659909461532469389051942193622790333184007818878361968485769030839087199397749911454133819863732961964472355716361551669131568451885778310241886346172350312586306442717444386023583262601462524680283392798904554475754998072055790319595002518292552425141901056036658935859847348834930811025276569288405765953176658227046645289124298562310562492269240190952694802144463724495466509018510578567124581094404971824796904180114107605943996527244889830865205121236631552290415653377636383779161115393258491072794688021427970597553095608786458855345727947824912267177510019295721807077652030687420809622559832697517824331313942472621291434344609356117455159113249402657215483950816803947744559655672857623477607475164432296154381227244490425896142781929390008849317790945237612425173295945792665076532989593148801263471998627772952010555133568688801209633527566509427593977197328397592650682814963189916340040786882996422576567604817770647268699379868639435737151439350218309624220021305299698958922611336434099441193409959507172650493302507744066786500087520600239864196003211493487904100344887038788548719239579685891009062674671157527457922834997657176686938315119328287063703214434283964223787590018002177003982641629479368249913004049356879638937332010195893998666393757763627629956012423748501282076719392021666965592836807010393191916843461056353714499040397352171735936369458390231010486657856160724342874308304058639318628044036271833089794714894994054177831044475998688698608755758179174255051496610807391788213482622584900561040024156634866030473594838401775595740652752628833411634775785566429059698862864909885683871197379587268043268421550805541899076873794055241610894618091667547953490569716794645923778503713708553758014865757067228697536860135172356841652950918397103004989624463242724123600284629127153814663016844710170573107552193975786555271362874160016126210824201547198187423992321131285329788483538361133165664667214008560047814061605125697175706053265818648836997108462107467265032177030910419760040446077647782864698354031591242927711679299946248504982718738216234099939856588610804786567624550033798390507799294865428655607428544817231082581049724292239780055522789390814511430002542446872513339415584511513448066549037400946938273564225585895895515150743190655177482647876636686221385956268023254053575072018411989321453466438291806768121380227747162756774417754483099029305874564289614044467403172064457105362893727103369676484301609237754674905462612007831007904537243223159060318418360538365022647320540902220528179042253074860587246587431358268047664785023570481960171024206459930284768425267562339328253040091817885689469262999912327612103919756347417373227712971310409778708315822683551189537226558159498422941875263959857802498378760877557227241904790220310845533781656803726771351240808264953623090380325186988100254572819966779979381030297274600952494643311640406641659796269024309747042085789055215837369321069645574951571873595914174811929879311092350787779819769657231194496946371332840558821805942596075352730146285410422052365720207400971714229044899095746815170438241490875961031586127150755197554994940341554703814186590320752375974576298195923200504098804236632190475589819516502821206350150876646943333697641090818300830085348178591369343155069963601570333185028191972708554976165095781463658042436093426535845840466235458063011991060850838454544444924687831834813992278111121124058906554839946721841294725020757505896247396990810181600757130500715631964662094528300967890354636367903467842939212061595256691380157871356802461298784457529533142201229546459275058208615162770590121292343794752072579787002005792666621437596480593839148168660686164291935976712809652680329958587422044009030208721007087977476543956945093012051897903452418223852738547940299575770303511244107041217138763128573052549593408181665967913092901822275211031883761832269488132180969626642311327980925114207904883821295733912297702687451237211658496955650136609333132573216779160963497026203494071813217376075009778935513188600865497649413454122562731294020540905720415951156910466562827487819440616352652374620988658411941248177613205312453018544221107756980323661008666844669627631572409229862927489656663200531207859202853630123531945342956114216634964314111759231443936806185023256333257262378190922904247484164670119779363930840649109714322288657669201383155673647958666433695066539395759212858931749416607578347026778927744065512003408480717019279451188059677554296408606784972852981031402266782163232494502027859902062612893221860714937951607639996302026168367669268659148759345069495279379164147568693819221497071074703166391706480856177977461003594679909438863539165557157397581966939381325837672174226423149389953823011792474650439067383484445369896498046364278478473965902448262304378628294888126279083424712456983493263266158048822835455002197199728453866052652068347998628554851449077505256753417947338867742197506836720258967025793245599782810348040088080913231918835468701193835092504031233592772167743874584030750397666422433378211635442947795955262136762349960437499806684867081532696115049684781729443577712973154770583322465016682780304619330767307743748492230738651289024233179703163930020451815244773104776080169591067456427940513520072501996523957063619413796462844703085122880841353784694257526075923148972008901763992542000790962844337682963419598923632824226963691506942304989355533462598490562530460200564009911436306555029503599009503179147938578765558721388540445714539578937215863943903167038143329532142904387643772070177987801461970543333097346271215422316154613249997443636874864064593198740014583193411027411868983954594728854169506234420557353083567359331446522743664941086741628054882455178212502232750376204789482088878488695812959351661833096257957145681354710994127099109731521055714263625116731439179054328513451853128881412296519272481391229751510787903015361998360922884162915556290543314449948122254422372518331640441967808970734379540829292711575941282616542132521522731638375190217758050492156954586446416535215199001830279972557401839778303176271430904634165081825551030827138024760863902947523212255443647734209398597328299015241709715359661723297173159077499447480871131250043957421902407134069181163944100551953432344853971788390560166035317365864415501244934827763348529423327568225753708518022581326036022720249896409473379998467632690986637879512549723129000240121703785967980458519211705649197230763255398323373451800517065874801668153165919713988383618809953087250917327733234673534777739833855726530488711186951373051679684392444702025324926737717886912492285250843506473667897642814725681644590850039573598453152525743839447618252001002995986474934392031912373530348902797078283164104678532211111850383939490988769349918510395703052484205497822605226662396969629091262065708405421579671017427385453881863601239635798208298012662462880688656688777989794739872302382474952733470940541081041407568147687444941389305468546190328642878051102216570675333059642354382262444389937923402487074171654850263343076886050252707590161039326068922828789279408735886492248579102243624445707070984985844430966610936538653030364669594769671782848834376139112811724478855865516105430651478791023647121755244210225105336701244795227481900481089310402020098310320884685841418544241456596263340115449073171421848699807089407127405475160366213535152329672144744172849015574208307927108091996717485365429412868765890876552880251859193166077979767510760348731823079840716756967697886928395000594555186776373070043028432817707593310267138094307616965609822713795535831542604111354217015278035860062100810969225745587393089977095751554784069117485926147521459488908298728734270560215802256908501732123292077096677740014369902446472839291578477883584445582197956604063311601504542019132062107859366132596052636800206683810994088291190437582662409403176068823289108237226689648836305271010221643905693940013765781102908128983766470045904534528852055009168931184647853499055615867988537793176372243952572224038388288094723410575832474092873095288789727890384550141921136051169455868593264370074674844269779691683830091723676787392355714677535778528020876531321070498900116279614347663565905735145724094528102175601833017078386669146761133063607789175936161022778470467136874387793910314027327914056624045011288836524449659784978350228663807322131575592592373603931121680167217195123014153481116190024178158541252280379756171764391607189764867984997563662710778794047772409304137988054178773716441480899291170510703424011104028357123299297289792370071448287024605474066756699186564331348494802381028926749953741031867990350857779064436222360734834419069079552724790396380874838655333116394126244500013169383148016379927394099224910682453784853769398820455877226118574586703837411354089335869637601197860691549281205778219407867926054467371903141188630547745676146149409869616473841706955243896615675307945593562755745584801256380582246635663181861964054917831745705869779333271502411883292738188702890968537702558590643458597906641024381987539077433746553721069840324871303464809386177004586087604312373801922481465000797795444563457074996792595062401245469755254959890208639362904557457374754270818179102215255678814105726794066675852267106140104016568278625323604448747729874007843211318750130072545194638371693448804102016535923747705912075453965252500085022103125267399489759276704959346974082809702853584644315221054776331483094545680722421708991529503562316580231356428832020407361377827540596926622169270702962540872866642513195885377362142330030972253121436516319040935448009491219848750845178378349669989288249399018017473544772523050150716506292332423811560341015903313338902652318630116013496024559317884404195245829879144586476280530901378525565346274693349239391541086585005499683031528125499462255110317615396652424120429661841434068983334003975238099995436071523311936821658889212092432775187819412347698970821111733860532609241484105255375287166597307453383042931112374383573546233038916463991477502632615167145537317208782163309873987037377399881502909615141911972686367663735733708052401826932638421222389367015505835171364303170318161827342082586161252722029302299639253236599437866717620267432880914137365277489683095787031414013213302759544157294109278250230820996054387059081716007227071490776283531895763738094867281212851996796335401210421937804646251255658918279531063169972404490145918354522978134474131773808010322497363963028209994368179279039865272976517673071494186235914182446856198513730229513011916480653478288915292725554748514064112369866836300475929544893958915918356329142739068946290879881012747799109501128158487064917559636634963008990759641173371722036399443200014795283386116031028304088183365911657960397868679524460185181180144753361623663375695687388103523794898583118615864492834681136910173019238661783004929570500841038785352108554401144010632762377326511970870348654715043127219484827249295743822899932904358122904319606169015678353957463800492044015258976668857628702987386488621532847563450291129356182700526171191643353932255983179026664627173059876156110622016541563201965349328411679069933491388561016095935907163380737724507534516955947511403793333862580852885483569404373428035147486264094832514190450127456332662189238057617886251382710706521184693029653249858773327794008279924140552210854486073971445018402293476243075284566780671474867989883387156475834537896059453256871859413650925178544552329946537341133252758183825087324218916692112251408300293555962050003283306919237387547175022518508982003574573312360083100244434442387920487986634890485369990470516276082615067278796196540248196423392479592293525432180194658613952455204085425132659399671342778989670447758490653436025293635902554629121037283770618101915625068407221976104162231441241523463881598598450949210570773659909009233704595133386014128086059057345669019073724051175568588220833796438743810952157921464525755183985056162191924740606965830806664126786659760490112505985410798904627238829579516000168170257772281955500824569565517916777911749151165031372919063710949175309331020412334675012031974186878685016123328037857369239678902089508365770688077629183052702981551975499581501170833564373451663181353624013355170541473839955193408296127343228445040973497218338968977848217283226424455373655060708755162151709683675265527064252964131242168378939459736053501345323262059155916103279645488350567374376190701265633543270586259655823781841081932342796069964527449314781392874265721646511981961566228684570985146396697412231676974021096002262349197202615573087157049063896540023141651754288215584897310660929304215714605141789035782446650561602832027292388810577618299331950984333613319819341756428401464485996269156819393761248864861114165307039098061096448536417964975823486704246284944312269192374692737986149048488240050974323318793975275319216075968796160996291585315472467806932691192990360753124623152631253389234335898622671291795989737787150755442112095010575964227224709433482861877908923547998849033233248319552751246581321132004841786703954706487293676731781184382777303511067554661198236211139529600663064987320509252140337466456788934733596610154648100020568849797769133438764617324198915894206391106654273155491730567236237840125710522777258008702204432437991704240762655853505782073360042509173906050544711613511595203046913835700419989307526449585356296530488789133896226261684256716820344681464270031384396369742178046864523358053982795638237657003067507500402647607711988989962773641338695853657870617465782563628625595589840221992087040272732628113553953501446465015672552526649557290406021140905418686832826987571269864552580392883921160593312103862213748273911434956836923867130285681964238705214947479255137104276249433933305661390655556474188628377590977527741968748383435639568425666274040001674978624645361493196190753295843050975214210410250017927684969914049704713184512137709002561951013632551360955771288926628289751127198368996953083308996566723921786394400615191459514932138986976648361076698227566496278957879535207142715661720554981704288513872204329948782630077729482893437275971848983001268199762994251417056491441318413506591691425939361941005945871211553590876068606763868924313810763229910761008725981669444973889375842947538222434807845482576593145755265087780465556559918968810098585088729398139732473896842600273034886641164947679477198137161265090602889464755213423671690126669036134256389385826176110703998737038600180443416099539278477762362593419763986836804788196044455536369038479793856545562101570603077246680541639948687702193566258212674054273491728787111144395272758045953424375295021598413570442005686159514147619452628990606088155148565479291287374150634456866538891838149797693619291384624262547231825620127994291276337991854528979550833517547735506682006005251705486546455432123193656203252378455663599487163115444520387421702836960133147775283023037182487706954123228790539969469727382805142124390772578794852022679532248696102618466907106476469458729589340382161129349240717218644521533431511011360530686038325599040603137736600126946275025741270350521783914916319982344073399584532499215687959158287107037837969219135241726025473995677232332883078076317550151706001875932896420880097523589045101707023766320923924545717138043841059242640102298575736848009236738970566478690061292481687236768974116374731714633298430016454458507683457103674388126492115973037809878624421553649996677670672808653858032343376607063548501644946140298665681233291519328925632717306773006867585803756916154625562164286045261657134300634551200641695497858405765076997931825520085009662397999310121605180113014231525083290073338667697440830662052999998380824268582223122222218328507960769008545052810459746660612594961147216979409813347241522252275618951523778455377184046313162234334394237478874756833404701437375036302255339790373459068264850050943383650307961666408180798353390894135605384327214259981036120243257651917478816470045849891054932902584480045892174497347885458627460665575564535248749626622630459201557520657871334444844833494110773132867823167676099062356257545465813648862511395394583725680933942858683565361605392247618924838288415399907453976014529796179750655307975796947397719983439050080341967602007081300226616100052665941557391225510196207556917976301456264041782312634367186355071123585349220375621829759259047377649220009515375211357206110341457418778797142568183049019937508882064592804808701114033363890545649297060537838209891572682432815941408412538876605043380371339051260139010740719672724421321948733925598370949559669646371220318212605460132655534047998413119524250113649061671869734973857005403571055483080149048774214661645735073306463129781130517100933793690662135549094711387312370307246097974707038538786232296590743101813042035212551423868214708248332046548811286110904649684344823950435920964733270842181552390891512302563649429274246779847595949841689208002321911643323492515155339136722955803291442698584258332188411940209931886973695021536615282746947694584316748084870322742173267781325052418985142836284900507399270286914873049453336931577311008533678797012134542871553916958338551278877124396203232390165384198619693021361073948280149935168206170806991643930542939387944280937865157588000326126988200138210793790038190915501116240109429874299859221248551332829658244566531027190357931539121309723536377589490232594305733252914119888192936666426994674572571383423624434093334630842961343184540991276054664004675413526475226603247747535457958633833941288694848217065030977577562793962713959423941600896236711325669950685623995055907037216561661154510898503811520268439818300750711318556273267229330951223494816256227235962614550755682218856482418313990447168285080996329573189153414674957301141264158020297775351631370650563263635782780989144105252743575459519989743894462256687225298351464929009662275905422359380041883169912638283187251852310028724259809951837597810273218861835691931422801199597776182083038050295536358189946622342114608005135299299623270402202994194703523390251293244796094684110514294483967926714503347394534522099609111447779602930134321086887170681371827341320033714262799966154873997690043858199420096712465132329535224184928407159326192080481923582577393209082816675890428942234596026675347793837066148410887010666268580340508343497510745813690794516632470687869772675707934242641596089049625677318990136232730222675726371531866857114504340921845178920881940767044980086042295053920547958262167494472270503671847086836270696892282120641612264864694735493173121887619528000259837443239030562621858760239774760424667488901848497573391249908707895761725878082489298378903042717133844294603653208987204792924941903986498573822268081134227285080167894252982308482969006854305369681769547207420291998186867097506319126351599933629998849926257276598548139958216857590349765534136343089729317145242167311429903927834746302900912626212082093028622377664849140507640905661163191746700658246160204497748359709067685095816615373680038538658906861403571628212433690981569504547711952305260081474882507962139658112056955228972330196688656553213299031017275744870834539320781478998958471519656301153558853740445413832134129684202239783791896900124189999242493501095920287319580434112328463549729862488092635930703872537256438326388818816995927475284820342588518340129355769514065443794475146255513801068859408161950337091684114989721505797938075345780699904121511065145756576021481554869775536195942591024823855779409689490007680599034100861130082697123417749026938325201718315156723699064051204050699312647906115090349264268149315387683638851127959190653412852684980187164065090239904343235091095354299469489457312056303683341415447149255100696289777382214535844987422405402168316275562587185623628839958747930713868400699369835363638856580247515059644582539503990567215743704954751958784733498913801513403679384840628607448238922634999182653391084958392285527974139841133792994315334466675874659573368811248480027481442919819729504348324058900393509559125484484266200343199643024389437253458489497621747368009416496719452198545621615760921728560215840731410181845332547410009759287748244028826953000800110849920074050499693307017011846356286994382059972704741201979792907951587134398703356172374870541844333703624480541226647071421999652853716776362998182273804604016421805592212356956122717754381429411733593521736690211245345121104500308206003352319102610019864976782776985379925783747019755770732341824175244746651380582685710319213756505644716904853597948688234688496313354495300983646951360714599325701743050669387661574793628612016789819662330369158761670066244650704660340923182295938885837407570476870989007696784558435008226590530125874907356456842113078401993667403512862597353310952343907525570170386729321055798653661689423612392949770084294643065097019753390930697853953822318131275350907830584799624959902123084706485306693473016589546906790134175570282698263251079859656455787797111694148825607860850479071976265467503079009753872550745743264032390232308189805105804928587408357546524066675959028744517806314769451285383326568624165626748732006643635506949683357599799227211011833638122916229786711680655276660200284852132850518136918993773368627315782041638378522937922303018397730426599288491852159476912498082958882086441723862022759171795337308170845414837994228680740749121388726998826031401236278292138157798295044918369578132353158998608937475043046005689238791824705787073098959467092424794556818290891636204160097381397078641153379464032413231525477678245412484542654394943103887474007904142739176918383340027832661415535679674518058449937965810427548111941628159322185299384485582827489308181851295963962148156274376897006889296337016708436660006647326081311408171333098581126821925209025986926407154224690295115574434653536356093551960368954621153820497405861926543902405016282019232474552743308194258091552707726813492232861168883292172436995579470484770325100203747817518960349368441671187171707384845027459030956883925618205166106694925108140726114130577750355567070758219344183300552238316222757612723029974120400598439759448125702587199486527133492530588808014113462246390311745846423197848010661601100271491090619261882577825606525281357101872880591746265732421474042137445959313203212711141955749060996336872266149644361568646796756167630061036059873865502374078571304109888545224446193846890993067815583723200495926182425936130893314149080873511514003882551252808450202452316194339311229950760562244549374834967810818711333367268589931889264592554139380032695475758528471955638399273448124739957255969843995734068480654109165231896423692974416240466237150890470927129565309604076317159705769676192998387899887683359051859304484200924817524849105667169521171624865568094922877744946785667751421802966458161455044201624205505005272698424621593225768478785721197479016028561887105125931557584757849304203210229230640810485249929564150512287867322877693903655690106607664642342475541943308226803485751421388076158304536891615286662712432687762411812088220292657329774253434969674677077895797174199379894604403046702831663319295711926703263452871389238865664753895638923803904017861396522098093359625982864132861629376124170269858299933504672340925232183196699728813816072707039976596930259210651894192911686081073957171782289934308858800385028701895779244233779182800193488105224458022277538730832687268519078270690263792130681631508157389687537272827135159686724306157895794086056452078826604372554690505446972932019794840097569366715167284326521765229260933895502171967332725269984660928348652167763680774180411686445158892710819577466279717218960299457459659123049605289010369551187112894728816685078355069248349509838298462800542695246066408477947482701196603086927377700333284647488177651044498941378216012378208741095634521887463792276036689886995814342932737140936138395471991689935225027654073241282474024625326541038495815593241818973765443850052878484379563430217428498112861410895226537358671543277441713405702419519289613824846227689056770954155667857507166714587499484125573848343416996886901732098494206543795605836010144497654299459199890732251444434692683947728022315292819115795469704769056162155093210014606893433188810349268339960471872964494694890996845082693282795261633684608442221503162381181905894995923499375966031856651658915564865264712962949054627197559162572555307712459672075763700591842774074780308044638904435007570686910934200556978322719054265486236529738273645448114533892443324242829202139674353816843476274221278776803845316340612799527918706831277210585657974545655110357133675140251548694537039433032721306080446894675797611875637185789166117398596157401008678657525866948955124845366939374061118561486086421532308027549457523383886771450819234943784355786434222505017348286117970551910459479439645619123817897814894274492336943864438250068180802612692075700801272087905333691156404421231216744698948553872864985118114440661395732448852773624227739033885229004959777683464496417121947042129796396755423146061015498830472883208092052717381500515812344549759136423564694963784931728015850251343477964651135616737389600009211696610512317587898936775891964085963800129983023898562436904174027853133506002553375772955408115924101870010642376137377765740647408066987340401244747566717744271186326832607375939615629729103746928884612536765477238497714035993441616269718973200525702568541567417619124221207789292485131523399258132400786520337634652890591320482333336180110255701421778905272650867975573409752595769168676873540796442326419136156996574234688637435982480877855991957774525924801332683224324647398233041989312431261973312771046569369783457172365882519765545805732551829165984931463371321286121432279950653786865954505051465910073357926103171724204268709210759654042238080993529157601092083924011408270569558832813889802179074390398378281778708494955753179186467408896934987172398499327265296864178399563220119936907644543466283767881053287435194110066803498633883758576965438723351199671650074642907950752405672574635142588821820559587968628493653254213985604099535170386331691526137756835123819285427539637654452277055824008875183551497972164988672568101242755355935848907678598558834464511743170253511355024310597906046040004070705645942509989504709682220996808403234194690240955504570398336135009730727852418718511051854393320210317520903680304027753537358564891524029183747332658033109929189852889935500927712140592305256870283535491526034640791049769614647642873147961553672216180804521337153092105637329257791517768625364578008148406538776942634334687959525943242504877396682536306293261660866882575718694682791280812493845697410994037556611833202235700049901781446320067731736672696080223485156128931414279478128368434240429422069760664882830262121363814361344068550008067782846496032411893558019687699520029617581073927808927082416370940760280843015332429255734005398251696855923916699722726275585831699668381485413385295160444464942206728019389280832812464224886399924465504418644630972713569341870399036359675831016923251790131671236643270242434411737283867541990521976870574834061392620485475572696779010407881789851430261071833236550312258013672913681665392296674869905424863422246470841068450268174780041684832625456844213886329311146801043704815110610223579427750781495200647339172824369472623907250792106402009033738298708481138513884843734201244975791022874970895547016800105687749312397524229987643647414179791927341471219561163371138740524224629158165846495538705987311917646496860635586943481364522473656932863678844993999861047325614787459800651463159381208966465274464478631236715644089213303799801643556848255792642910195733607698925697177585098008468018972378218544768794445835318886453338699668400496047543072316703998326953169388499654707053071226725169717274180734436313919026021689129598609127721343010786345390176155665499769338916733621734070780163831652363152552384519173877048923762874068618795798949554421479328129387084857194031323548121793151637749423020244894905994749288984231830114906496890313585635332560495402743556676099627870736588323670833020474103977631946460288895398396474984877578004253623144612716533400121278283247145480822725972158470877096302067239936702917081434225916132060246869847917550805395833431670718846411104020728738248218961617777314974261216960776836852393064578411961403309792773833174093276310890799069492567658080630176463027159898971471090487813940252138158992609669268143826384145354058190145183096896603718373937636847410168072442227236862373990995742489153067919720950436452523912242326218773788215836800779434716767683137431552815289468190085575054889144658802602019103187413589045871271396829982221975508161329885999952437047975548293406173659524202632222641363929885024361491707464627588165873420870475162084807834129660082880368646219924944276042228136464521235290035496625168478620154212557061462001583091577604863320940410645149765369460817368433631824905947446981261066124547550377328411526970891874693120192264769014882583023102071910755420623730099720461284758584930158750116497168985776572873841560812228848440169659618319957408356914616653001319339834887171140657273329541512914644377089650172828441015254466011026125354422633928852310052974057714180347818956172379762247483860767339843312114670193310955891424984417214024131993799334593891071268353269325929558427765159652681753556330760313770099177294478098109730589414151614243120933092873963129872413434906868455423585751321451057287976656097616540642338413826739577647038065943894512963396171396887304123653422407572206039672423486706654824980394956526180093392002587298155002647825874852888633988525686743614506647141012454526106323334134381008683486677381852051194864077529433632250321835532878698072084673497675164208543168710178823005946491334604555488444543891610460932593658748768260715017784380778220219033916553075501709858066691904534066405966155333380793454581180227415496931377402241920239102606714611540025383422321595981560238349144867825112640520758118060478316552022510207838892582495150804858545369121552493378065710442683577763809225969206166030210956645871562007625364217180435365121152972032221690281969697606605569481672229190334009590444987975155788817275001179885920549672426025567822545311822088305006434735853193531768082783505635763582849080521987952391897050124774726376315879973930541213780075707444460069999218512774898057490266862063122186717545899771674705723086090476594770614530270219666850393532168242644712468403530581938842186750972363935429745507284121033685703784177853477794899879251754861337222500611626337453967306158309897420246732789935335868171749284210905580662636303939028506249042083692471454212298782423984004253804067404885079532139644334153208687570293798910241209464123797676351742814717445930335923084908893804407574369907145931648722531542794708848812348223663359953284534093174017136145177875327093230714766141941948812091073439917028972168543202551182553382011864989852742396412258819212501093803279018537668368038905417168953862654611879362952399283244084133407869755824750235728721037520508069157571554693453590250961025599778786852581658895670627455523766622464249740119827273018449121660637902449200042089178998294525073017511700087753726549541390521107380628452545316962666949751324013997312544865891378874505690208388844307761910112293080215140665905335061119154976956280138038083472990894151237384447379965075547702437449239676508156146556796271141750212013863579410711893666555518206384216646799688313692436307183059587823734297019345069886058075398667362769809415921660705743830301706051483416780158687191307058030130738199831967936782896564497851323654263456924521089205840505101837722254117787519822155674547781404724971238604596670436840775991780450076547409808812920347905034570896598506761441365799293502599353290388222613961123626334405769484189653069446017487090420185123240975039532687680867945227485138217110923256001348293420874298811292353773942746931810915567835430270872747214583265371964407230266023025270920212391206514260324629354001581673156668878108114678542001354326588834628425153960125149863241246221418005871099136799032675513510005221089861187671226715662112116543504590980661664914093195467118887842310616872384158676869059042962666689328047617005690285072360893917288318125067348352542954288808825220407205496578717096071149078171117535913458200179477659028883322728932850948228045165458664283758814000853317277411614514901364501353465074134206252509421862757207472154467774560229257939764001021649393795093166869719498397569351313652144436742139211970279792077167091132006198788320974214088174688557202448183112357739233411302305441283881200264482023469744664968594283436184243448628016964708437367608519984793295136397926930931325074543753702835075809108907731057567782153385798885487604680784938247853720981311069001893669746270039677245500882342133978644520328556220386623508264647520907599566901862097008769325532920130415537146868142228469745725142924861038036561383275719583471449731689389630570502809375341696162080176100789352092872591831875693659343780680174025169826371779995045809138763216506553253239853727301984529933844518268823335237034693570278730059041968648892845615197759273671831921881454104548442492745967468725944760906853868093972094244693333702799449059656243988828251186433343091784700672643587846378369450208199499446330710346457516885157872564039188909379674764552884458526415905825004426852271891447625964237572177142878448184958992770064891783873652629942057642040686859829494882921109319521499109555575783136216365910422491481861088191711262136318875190563510709605010798857138446025683113638153737608403258276821395893265945887077815778388131340533552540436466554236282588182247720520797629649661016307621318447190257517807756276851263222702465330923772364526892386302232639611979062417876531087679260511619830807472464489419184242623902650856758799684254445769593190279756521822144903106367878996421792814244470773795452283422786082456257652854264427198504953468973639368058773306915858393518431293065364075477539034506727538549662787939333410634637839905765879930541994494876024733913162466657380406976192963452847883960561324464261060408220950770908832097589015360578735428576929239203064123767890900265352573613619510438269733386159859058016899078524720855420557975333577854911355925927698137174923061784848578443267591794228299144845046325624588667788004712312112212026960014268632310436052157268537252620895198270376570438284865453970052791347764984899907110557636443594124212303906104026651415145522812190722261502378621427120746330766862669523886195453602088020310882564135301777025177652828186827572555764933601354263235562778247042842398495602978357427011558137059974893139735365212072720106327768238326252040387411635552736046289051382215518442895830263929260129556803859370247369464100154299285375218689096292352832522333222816701262313034510595694306796593991001448772585312639729574269218823744926907221458460935983926839089585793983352893599764189603575998363321650071594255733045819752746303271721651851437913440497420633488510171077166202615144304427526055221031731150559399529005783106930642952900570431165563784481010601819222180587186242687960728719217310161824398461288366524581384272429870155508162564404407181678734239859380599395629144089294501530040841495510405225882978361305289124014542066892056397658059898422741557265325984475252804359691944611429514571960736323915204026320076474435656067626921576253159782045714790601585674498579560324932590984803087326058093039801553309295869291478481829556941145582475208850151568961266727239032393169193652971731739400149078379987632782546982961250028178235755922562194463331615880152555872410688082706098085299912796248637808465751706080644470088276345492042676296860564139120748728849409665547949047020610824703851431854915352002428814791391028975834321329365854405122786122454776639225249285968234924232212981090134229283318866899773869943155230340037904475047671729485228435716677651014276541008017869668705882896158153304581101981098589541845939529118044139132628121398129712028147344260518651038300945317955677134207626651317981711654152902122867409986706270063229510291845818376674917055264359997968543027154657836532677613757053397860099312119654756474412826028616957279460113402021739714320114906888452672967109011731708098216707871859422505620984982178800102887364860185228805516594849963400213621655983076900037284980311893318514892464734199568435520313447741301567974791013219795192589029359355858196094486366222334736731258421821481714056584013700033400631473591417377706940990451005227796625772411075111882145869186148176811239564913551273919863948155219683473103930296273307453010091821563887764637671115703154963687979890677251392749108401961017141410596426420010854839407092078920706183127824738337681909099744199929225902116915198393418626707465096385619906908938494052034180229519219934048869025249204752612720284831536655097907263330478838546413021099801399317976956404786958031246088493442632021920051967480286022786462129032271061515988708674346642353436255526667985616407614834236142888978448959084811341718989134127428472249403204433374867377374820243200500184362581910864280444017439616628134136174224638754301662786968504785119075847152862616582151004230838464127751551571748190388828367268020120273520430791609241878162021988281567154776318951595256980544138083360484311055940107461218979958457520818443562885528068638367069260359184936599747822778021594875625446919329356879763210126831050834131564488153986807678394167030956465154877123134237787457694086241469870256245403194908611122960638026554839082957482953112706909243890568320280547306283293499897415054286285459350088973628319039329609919297749490837611305033614230526915462166649488015407041398557837975991727622041890445165142494772568808644188299054109712025705953152230593847239193256752770880182108719509712687627409705319633885788802570256316244214423671149220845194812066457316417864039155826737434658891792725386497794207293407826493248858305717665741467759074096072094364620524290438517126309486657898043968019130245536461110246054401267010132882206298361685315987970517921510161008216668654097554164122216656095896002478703805209436382758574611525836651881665931038861283148401608047817986133044780821897585131921821283379572777673598055330104632838508497407056821687513179557214600096240669814214199016066684020315105231240173094284340308050314389307659770416353803172301553721561277625869145334794612977987681873902629168227207040606626527347101350233031536680414853792073753821027989270121173934804141730028004820954464101598855299497475705841594047583009643887415034932796490018269460905461026746565460206394351924962825330965465036287014082755182769573340090150208532904964694947839230852332686974447339535192198004216635514719738563147407848981458054963555047640525916032842155317306861048290433758257182190696438894633237808474692830763631200433118612495468368213913548478945562687939197666156143450262754851558124281560520149225320082921306544310890061534228600677694264088077715206726693835928492717919664913922417963654495173491296621377244696184948072119263497303309007654346578993935984609107094220357744975861260510232382355436096778706723394580739829541443887189431850463318590942676121858382440969488384922274707186824176881158484848923098696662598775838557391936168441956489390265965764093390786694896444882320803612591798117295559541650675599187635846438054696049692997015968431735509650531279032920419128843272557825684604367433713486529840474558134023566275032238720757873894884074834357623008575436099976417534939813653530947820065801813063474965731360567447884197503796003507490041341045432785541240457003960462837655589348158352819511980428037266243366935874409972717381064036598192594750932637386343378469584332791474840077227556911619274407906155214935204535779548534301062765809320280600371500839983789196762380587466516019777313609291768847123770843046369943094556699713961167986430982740114933542671181188917598367625426635707762028615253635506302332966861161047451376192684800381767424924320175323592398897465068837539160534335238531961032750578259704289265332144740534309775766441709815758089204232899759467446841217099865314306764534138135468052101987228876750595475112796544933819565919987702626938295749898965961040259427929644630472862216655196657577385959472365489305531421778869322316398727126155703238648899812820994568310604166641009712027974551170616346787520382456779181333307013600072691386533388866214769021929072031720491575487272504349394885143887578977643841208338626940968479048693712852461087524433627807406379465559005340775126910680959306784197183541363892296405910857460711510923390454674102920235642930635541336447257824158416145361295818976428539786509412363001340019937388712688927203869189898428872456927328456876030164121753919947495838456249509990957795078329213953867069451764422962951723783988250802776111542254311143141545015866687656945297078600621917992754539059989499694994379477514541838899277372103725622482693326261320704447185613092424077179109792610659568661077429869247642430755240629942754411483232394120828773457832925548385919148582964173594244702281074240486446359621755842115291726508102896937921805918061528990012669869740219521592725522006137712670517316851696294947260454145750877149537908295060531361635362661104827463717735370928052142402953199436054428437965568381230918215955157851454046066159617127389057852966256736603579170443726802227512601334687539827245920321150805023512976547650796957161752637108572947054184902024192030964407448758698872500759076811895340393509811184739561398920698032299573067151713388397501533217749571497285258737319563585397262333299433107803430245526931554167362716466650420919027309289377575648692684591684356973694071496098163072455799002126695250642336202223238140827775317151659633039312478173151331348707808380101140359564028097207171811241935485611024582923685955577298490372332479227955769672812512716136584948850190575746268574269624778680599045036431261819223587455432232010059527741178080440477813516885502075833732687098288866423207398581001316626775741007979076042346935072800619867111468742929465619834496481020369498833504187225283697967153803063820383433983407557951036471088781758896826111725071399729436623812870392229155621067588263138091615181881035022872171225460096856135208714878625024846460240875983642773431374596182495072809473377985111320695917290421294558454698142791769381755282538093797413460716748416253350099502862980204758142890017921485577729374726682967943150976675588084331453298233770102195724196056186772135871308203457749135312750303657065197679409989932224874076077321029272816612931526907708224170751989782454592248330694354943345042220291019914410442477383454360365969105224578379798316596000464015956159027401136630837320044056798239793472852495349944117909703598204965738249608681084100698751957898044167359863493587498334015414283519951662518911952367852498655435330473911990037639215006518147197645556208719457603986922654111449018027259642286961688335846375600568325139834340102193258994842407862774807363571387915451512130596389743950146716214305196096033003024355636028828246783051161156890294403428594672682278841279482598773721996897355314116086025401929318193190323688039064551862500968265777273361552733003133432577026281390750623586387774659486228421890575692748714025192615916900422275496344143965875387179805869058364749902051063950701118078667304565187280776168415007844229188736490096799237952418347020057553210735337166402776343283034111537967524048208791097624775538774595691167263717057960160422937494245275475271829387362149983456520327346534365020357081670530838031524578101425380577680952666907357796627391889062241933727279505421170049276916658409687137270454816201582296764023610131551545229732402841307237088565594663706324843672427380592262167642323447508722546331446552104358375403422168636151381336095494428587697311124678018265722369917699142875962536216808105464641715932423933049457602571041230967061680870506590544802696639063280170869797050180536084420450419404382308966164278824285971025251639770131911555563433871014834124001133344528536111775568111538822813465528650594935444931131524583553249978910571241001908509059888961088774390162185552869575764421828251690801606969174902577656163404112897365848710715467987250244768741288148928288120104625148181388137393707077594817610827190791966585194001911837100332469226831481432865302566176584342080665813050697222574032028025957977529338748838011362131001260522411921599652588146122641214662812912822000338507285331751878080171782428902736220235286190164200785754869825986272599168958599651100395599483377895414909659569265964683086903822339268002372598617600519947718097457629912222222408069748351783860853478926476345181032641377008890339061207445617630821643677226868648758258882308901583808003159605374392252664246163074090122617896257980585123230506697814441784085138734660232530850329174941255460152747709185648369254422910526542477316348655560345861083394355540487942756629203972923534722903596554449942209392578385809855549767518005936675870983434159128820361339342501569355468259676455861528079972293596142608263452099882634315175231168255589983421732339764876817404802629459891664914434801973659019641165830101792544325007993211702881782997251376410315821936779588673271362756877163584552530116660985609458727080906947502308270864439912977417614666440267922812477361551081904880976678147249599654788516507494918689496628665039924600127213944069676915126364572162795519657657578924139820445557735723589511927302621017732254872912449449097916368743762766240855802576861137918560864956763633366361783523028611941446173208660394007186541332868306544862308451682404296197087004625639833005601427066656222300314689462820890558397377794286815887553147398294815344449529888612072572905749028937013064303697207399524211503238110921174874656213989642303256700764314158591047762097604096939953327741766456939545646441421902393820429539197693061575432659527911629108123598486312444071311892795580001689334363383660825417824291648523009096065773762447020524345658428496056339145269393667538164776835671802059225058894058857392303316868929285385075074558567113380417761618527082913025186646570386826226489822954845197788341607167792396482108911079427345126611203143520400283449303956364412655242202928319497122927653083456334220711592052916421673548800054700854686196635534329102681087934711413464306671837464939880858057579503847912752087280601523267312172940469293370970043762611734167771738402116059573441535119158406471161669147353074038236859503211536573396530701574519922773694170125048503421735002687370213890236030733567415771623170019552227611640322552752168954207580299663225553724400277795226201544323640895172934659137638633590971545411147099828814937115170120972397310505824027969341272210125961083271611023524080091969762390504046253642760074219461818789717473256211571890044442459555940891737859455899595213116216679904542205666908594549973375697328965227548295750076214237093733173072200897232007490015652296453669923501962504275681281983071347979753252869416984960908785102688465361642215544907842264538232596368985484102043812469031131472046876226704946818487451867344930919338630288333415229857426108717784830784618143331412682890204136303618282068021952608174193494963248077368950090580647887992399720771500767257553335387839744127946827938610438532417333551714222170401286663201775922216982840889212207036601943892885785349361219807288755374961307053258784632868372137227324489341832656713861421319376243659697820709569433509396528525776864578881160063773017312019741443986039014688886076154801963705333982189640821499079823650628740988934695619102392513558588433437056794436264709476218199344462125215077528107806017343038880327221000752819350161909099448876155400202583368225806667906845252043359632666303092794336659683343554356965535896740483511724898288503541162520054729618265429485109681637147318696902182477082826597190427174522959503207689707401619396066201016283900451893240073704734676391163514117289943893261591066127489420826942472409052195912551170564196791953301012966181820850665315915860642658884305110727261500995320576364093065724181006016317424985532219223941178387841748799876297402254538921651705985014113774265563107139759099956583634286120371860585972985924463888325372601749036896849829818888294551684970488186182467583633346610480888937719247102030829039931207308485129058399685911459814996167737456270686115064928043871847415051123946684116817442365960010686544251124577848607396864411447344814236722811517000051781623635393120722474143546557946129062598330079263973873549830362019148452173056299580709859032931736004514326758508277735879968272514411461392181301676552189110826405156699152376881816708355097015129761216893903711671007175480703301110788126188293998290977713680635988921912033592902966678405425702544329396222334348986727280713705444825571697417053824414383894413131742247735820840689528517741980577714646123549600655106286360912633191315763851190743701021537687443590257927208397473358019793684264194233118798796220357257608670668536848204263302491271593500323813059732636339301679254133049806083651295253495537945634529257362443849219554463746926798171314390442644304574235547616921709868325594614619780152388666192260328183598553263883806491835511833766563924882849321820791380104975006430786421281721270937638031185829135686140116586996095594383311255050111246724306200790923647641480289224992827514034491165277495106797923069458738142653508238923493988372568209819431557357420778005345512369002916829342613663554824033895423855292579153252200591119553131318812768220476173379601843603825234006569907510895180161332741149550699877656842633461437307655613458690525988063509143831695018639169838642138310889494985419013925144266971262645532763273180568920114992474193743948217499706763733464799265636529414222744863645260697945203351122100564380104093344350049754856394703028100666727981303179590623152955531972561749700770262616411350883900630498304228280742182005759782707910444151122109414754208431552707355102779697125574417112367109164328530511816527768463436188097178731397487335053416117818854325775217352093447408701406425457480456807757254636017660013354944614926822120985591207135270885928980779205366628314456293761266868817850727108437318955651212272651697196872126443525242228445811425199236291054930143124269662990457547449993248692866636230320939082018474524585828865750065593134293430509856418040001217130495598682086833878273449920994981575910176039403958721974937754023423613595743897807661272879716240763919335323541693503057793423409863061584358098697480892032836335930396843110441086825677867002345431724665467714078425101411350174312175123525589708892457258901395241819993385447933919901672574052704452192427088963815829652069476223756822634285169485733430913338758846063141708768871081686128071521664975632379620393375163527486646218969772062388051647159197969811522278633444912976463926970809968983576997708904241998677978423675237991211492752026269204035498139001484830477419832079179990919366760099665191775161876685976679045178952404339831481409581761094199295536841208237843287384712764778943970473773398289203635439628375838030699130770379249428947900211529993545904003041072748328686353671247215227792917369346256584557593878709490152341953806872318890691561451182357779495008518619907395553299600204540220263497171361268566596582876290659201249092025371003892880904566080231086528225958534241000531802245151308556977752729696530711106664054933175158634460833223958850483683479339770575445721706352375186449461768638633406866944502360608749167924866652748438835631729130542988797164056342701155503929939272153080485567394562924765028732286602369982854328405075413086901704921492364656147770130285877875170537431093261134520973110323106790247833400328167620278078009943829756970039941234890291300039465896367874211984662010693239950573447000188995687559521391356066395227780380459761630384278779643208149670160689033461668320983472299362263100766248813156521653792004871354529388674876880045672446169445114203431135987822597766054819761783328042039703186426777365671357537315505641225280968413089072775244407848894274887133748927074930617331315080672603720880997485825344749722701006042873930646883730953953782759352381688305794190059512614893221856799503543879737602739861923309124074704441722380416310013819914106530921728423205331083072474730348773454703163583607268356727315000231026046852199799481992327825251384264324227023629405116697363228320968552255925791965776687804706570567157009502081358987019367728812105636569882992821372799077709618293564983005797887503797421182656952260143457480258093344009078343340356763578002983106170253917530550533484093808552576552994347568699434872306092900309822434053389262708717640048073947253968045042241901463973663303568380184907396715392743606519809497520289250294158759777468713032362506140571878455654375732071573292350117656637011721226576903198141739786780110103422233941286582485110066275978367051622359121091070787186027551609947275833171718806062846806100162739089973458231104509930442496469031130041493185699199814478308119885753148078520526417798996031432592733381026717760489316890129669256073685401334651316405768250065418797991426844656105631726790391717716071351518194870035389033392883253894397761017748520075588612174820720298587656798865868630201737975057093125273656789833313536176827366839827852662011029585808028940953252414498151225332030704405523522081595939521360904886107345157794063357876736327864154278195972205784040471178141846932135572183915738256284118211901237432312380450839332177998339059185356115880268248154421180760172544975769988383525599880996545115282969294929486227854900238240540252882334123558323328013507251922491125313130686249214529028481357432511140343179193163951765979543585906936115701503274864595585082670125962747233907385820939825630075788115054899129171165205549427344110977694645076779396953043661498118500578060414365667757860472877596072522746733380480008037129042421980230809196051201054460738065220904286940997365301198701685205472311752130660811860058530627380040186387094830223082782971387289275862669055978638633911860506597101463583708291371091054509949254564120723622837842835325720048856140809937411737242093591551986319973743795632164577165066124846033067867052089727235490032769845526000773010244916876693343013213031824230923997191966578688187298547672781065855353455490744294230826323783230122642852870728838248031428342696170035443582949262659213392014943280199250823409176028921945158490632448746923611455860664163818741700312170578605329242749255153476500651703410599758546398196804673539886965302229576879267477791488461143981250007287014881919659162714017373599302066780558762322125609129667297890610444074745073654786160405002382171117039841088740352469593994740887944764034486446791630356571447226038170524749887262076081395549391867824993436950637588498112801579259671238719027952503084546946817342543494632007845380236249380149593072551078608650894620329190028057959249722060381885185020528986592508208892474550425613772953285216699320267882795146489386120702735100458160322185992292135955407942159118627974526976303559442972887760040847048975632520632816072327668361720824205914770676190746223518794381746357631957165441209261549078380135552882739783221713345416403191506670276563544138441034010259603920686688203431267270934925677249629935098611971601213322060789528571712328357307205217771080444341446848517271284309775684151714610699204422474359686914458129925637652072207307239552374459708028037735181477628966856199405911003554100154560638881046631701982899690353826466947260148428732240784961625401516030589511951740812308972373323010818941283432447460549230784177904192075824202331274036185407536504297291120183489115426106885038489966711122748412016750225085804961897352701295627540007057707363144688190957636091505493737448527590397496740606050841324234912024267690833505197901041086938140867884690416522086992700756971334431094369553095353530812683492018298885595352068356533929463839460350543533481148589670217159547416287648438189306725067967683690785943110956095977137265233644317689432522637785549195467817206445720274808623670645363778144562382350668245493615660173709419979160198953751475729775039098338181997369004828557906578866628382934389595447357289294715879721440103427694602270994372758661619417374548752742409989471164414849229621716687399147426411777059958083203572566835829267177834748537253346790033669272506372696584038792454131063474209948915168040116308365343457131712806632333090435365209288167231785402913931724584927926786743978407977891698925358012231912218052918359275506411060558372155714119532547599461556198745044969911634014390881866954729280270960264740858619069701287800153618090762294721176196038012726097325498143558104181658226840293923114699163354259688275621455196602963021844186802864978561290315215706761783798995124711092679894263742410196832126934704544178544595776147941035149960773662299121366817071918879858002935894990645219793912991163755288827948846943489841242891280113397890957454808560637827090170578993796081615744236553626123985238751341831203263751838552125304155211894386126090279781594581100605248801297280124287329961486533105126667720627644625045311764303998001246893982625256247408647374665981600446053001921666661811488711258598262284456082229423783680501823269123839123750436447460420963715807646331052852896782364059621596430019406797643144979549774118534208194508483961683225619201613363973200063426010225480983556277323840358544617235081471568256468512157389891526854725935977311303792734012660865880990662273588768889036955074289645773426766898633570276014162861309029133607844596432230129103547026347098726747668207084219867944957265144119611463956824309536059372372487872347660133965416869672100239156311335979023726479783161228898007610820412422966823631834837104487588942108953148098601025684671829763862283763811327755043493862495308472799411137276411144039164230279645786118897166556198004421345391132070079761661637068485506106994363509901032639459997167152660273902667380932175957626586800193572051973686687003625932711315488117128079400184199533896236793130981036541500369962312648761659688701923045856573225288776283725304225795276147012523098365719536539195332706984676382231470183937192689975113062560549926907027243941313787753038385332478705538366383121175368328695734081128047368862182033862008126606546030814308043004436939069451982468801489615672431573918041084237697656422918585342947132264296917030621064410482789097236124669771636629620156022180077666535434192116382396884222029020827090806126694439918040549150401415475774024910302295712085948813630762478690333208382850794514026756619797765911276497512302834633395300767719486482472386329736023091875452746212108157371879298880095554688217120920987309653657750635179247779496697775263612221116944053797095462737119999576486945241246984736988358144096348816786784243511022188161451661663355822608573196622775831852482405261060926900507541465345439445764355039258929108825714620664723275740707152488190028904164912893276389546312205576302948972400615354588685705129035237116254735474151965769387832541539767351905541785498294143832917909102678752323979928605860360125448049462941474880516898931046687113408621072730215084250426116238896838894700495891447604330427348581721831223727175723120819075238396710430252986062643472759061004753660475019048077071790066666552905122937821534038681429854849927280990411575611816646618574532807962959119779052129004577479639750367449097552295234125996168318574033714488219162341933618198968004433960896141579652231977315707902895826455648528467683165977066415692630884295899665959623534161775468182710483445731974300561920272925622088132653058437570089236261853676577471053547221530517297456969871384152053884751146520819952917067465430217228768824922575477771021125351350902999864932260791987068086091073379977357878748208379289672560530701328995812575054190412624718166114726048941350428924599567956738456303503972399173592198891518386362632932698135648255906136880063645837079747732397797306571160520746228286190850262260210474401643191296111071417234536870438941706266104848312504385849380198806796071925849245062486749346604608090468751744449786275097607759666747858009692001048008702541412071711808600141872466895769236180037193555031529839249117686580241524361506425277511198365147405082141261789676008786134552437653975706503091587874990765884600181411440894115062407782752697576449331072110249930329567947528216713550304179847063381214590737573325156508813170536944083905780327201556080083192826542203593764260486236970721429846268033615775150958777960220110719909640222281283242521887828344036806112368863062023761263503302363418623113019733766432813385054838071267133667233759465185211552663186700675216084472829661208153048035813332961241790459117998505594432114253646311817382129692839624688199906532627434206530956571635175417924132911473401794409122269242952251260214349145799409015731200830532007902455548357302286747275640964369780341447405762915693269805825854041492967814505266897050112725561107169536619615409301957240647122056553974349986711214790187579364187640503288326299098234493817148922210769354844704553754694868852557064239005503465671433872960979065230637027404533952504189108268179232588002577414691561368793049731472910127665427668988184295049334010929678800945507745506939781099870507251091550857763307798339594884283942849694592165616037676747923851999967154694400114471432259545443430710068726755212204109911222688158583256430582290725688102089665619989381250817280081551573175528319058322614298907134730099663853481579476913899226202253301248331509392133880290077496079577919085827558432618558948069398861805433020867892291565182224900801372171160552359835724420391826114439882448499744405013781163605231007305416413265916072840949842877534935317730345080799430119710562034397999062233674947464660919812124012712178157681637248193763530065763136311643206734139127355954585908182998289616538790627444936350692141593785031159604009475943969399169116186757844343523704089927409392558526043002431327074954543467765516778598877966528724973642837397722637587665501487133362337286250052975104903861013671367682127725158574626015396749948824430933389503122766886216040695587112241714463736532084556392383774387144792592764786825356502858621591568340263799436617209393898641781385617891024151185383132969503373622067070337733099737141408498155333654334557013192985097494319524435348552106845044343931645599949737317651195420557947492287605670149301856095795262497640880274553662653057035435112756167105830873847366098321268515625076618647018048939483853124962171939673820997123308392548442222354617150215033003310471565141145256206587079390000438349550545840596820831218268538197785610857608761659177824159114919197637302498839297206728532131049879026976743876930498495789708184931798593533146719898425332838745524989763823015319889061023490564498493677216900379507804273597685627109853942648475154926932437283394092239153722588739162538659808530109242305867782520043028308101717335373463117469366946869320554988993046896067376337530380674359946790157013660220147536057655605839408899275555812413831523354347388451078131752958242576177464890575980669195489641679043464422780761656032389393545874509146797547278028317422318982121620673342059642789881395149893065700734687982383449739866494682730097361722343074305878645015919346266498998782274658058833954492276454684613179832547378777616479703019506467848840087936736202342715638147044807639314295900694433127302381520190769412921245794377404248810908586482898977810846727342142159435847494150426846724641198687969933861179080405233474504058131549787417757746260916382632415097216437810153726473863829239894898047156746822259760934799356947922372426461554197624066488257336144003520245035548033916444799617633002572011033451173729389176249505637589306959668349830749596994896180941979343750596411536935820135190795046540642066852872162697147690905095260560609536850454676645619747586481968320170962869907582971575116630113521550450085923475967572354871361490620090095169939977307078215088428427636764062895586212419404364968072813924664058317239059045532500957041231287359338636157258834371109854377442326919642342439699546576313305634880091543410261629037537766255834152828823416364419222620359645850675167170398263885058399272134200247053916348741976678236356948160199704068905063369562747904126186887621002936675012536063747762636582481052580602555279100012887157155913334291236226336262094955101446436310915914032996521566763688701652458743824512070877640534575361346672648859143461301061160345966938283648878215383114817970483328863387062471032395899922244277658815346760049827895772550150724417036336054602510488211264627614536129996603292809177015143188509160983441714766743773925316385922109537591941792124065334897716247764117367533164776637109665256009927162536795439137857546184733904986955267869058217304417429395912469178895238598118922908164706683101235594749236275927181576065060482079208415956015633377698831297245306285708966390125141921911895562899369014448165546707706522551139020346752115197102911789244060028687066878330090315927281394703552707794410526602171569873977973059608324024363362979753368108731578294550152506607497976274615174212669453878456957104434383158326364728418770768408979215321849088945773714194416976851449971772831052040031728029913076271593631940864407680310840950461176139960724060085054075645668692194486862283625091733671106278417685104880910534166725008231491664187699497302865255377864835403389865349021101295373449363390687199572846699323581322290457991783368526160686768114196825930981212521280424967493662488281241849361693591894442442120628834936904706512473604054964470481815230591953478940777474607866986132580923250101853020950421178444178661527002797534068937404002977489690806482376038538141717704069403194177611697876093875731365609408793960298015068139901983966854399472636586236712709963898553193957411873336187941466728005617648979574974153574100949372336557654351414457085272685157442711279609995089318288448825429774219846956862417770870640302475247928283125855980401215884212976747318780931153131821675391454179757106839253487584021493702120475037889055619401647443568291937923950889819022384242323287676366831963185728459929943571982387642182576000923477498744897876979912403438449903036450540594384275497234460834579807796823701486980464630401353549158331329746013894828484221196197247890145658094439640926716840918349113692649241768590511342720126927068487680404055813342880902603793328544677887"

discreteLogBase :: Integral t => t -> t -> t
discreteLogBase _ 1 = 0
discreteLogBase base n = 1 + (discreteLogBase base (n `div` base))

MillerRabin.hs

module MillerRabin where

base_primes :: Integral t => [t]
base_primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59
              , 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127
              , 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193
              , 197 , 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263
              , 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347
              , 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421
              , 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499
              , 503, 509
              ]


find2km :: Integral a => a -> (a,a)
find2km n = f 0 n
    where 
        f k m
            | r == 1 = (k,m)
            | otherwise = f (k+1) q
            where (q,r) = quotRem m 2        

-- From Wikipedia:
-- * if n < 1,373,653, it is enough to test a = 2 and 3;
-- * if n < 9,080,191, it is enough to test a = 31 and 73;
-- * if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
-- * if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
-- * if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
-- * if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.
-- * if n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, ..., 503, 509
prime :: Integer -> Bool
prime n | n < 2 = False
        | n `elem` base_primes = True
        | n `mod` 2 == 0 = False
        | n < 1373653             = all (millerRabinPrimality n) [2, 3]
        | n < 9080191             = all (millerRabinPrimality n) [31, 73]
        | n < 4759123141          = all (millerRabinPrimality n) [2, 7, 61]
        | n < 2152302898747       = all (millerRabinPrimality n) [2, 3, 5, 7, 11]
        | n < 3474749660383       = all (millerRabinPrimality n) [2, 3, 5, 7, 11, 13]
        | n < 341550071728321     = all (millerRabinPrimality n) [2, 3, 5, 7, 11, 13, 17]
        | n < 3825123056546413051 = all (millerRabinPrimality n) base_primes
        | otherwise = all (millerRabinPrimality n) [2..m]
                      where m = min (n - 1) (floor (2 * ((log (fromIntegral n)) ** 2)))

primes :: [Integer]
primes = filter (prime) $ 2:[3,5..]

-- prime_factors :: Integer -> [t]
prime_factors n = factor n primes
  where factor n (p:ps) | p > n = []
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)

millerRabinPrimality :: Integer -> Integer -> Bool
millerRabinPrimality n a
    | a <= 1 || a > n-1 = 
        error $ "millerRabinPrimality: a out of range (" 
              ++ show a ++ " for "++ show n ++ ")" 
    | n < 2 = False
    | even n = False
    | b0 == 1 || b0 == n' = True
    | otherwise = iter (tail b)
    where
        n' = n-1
        (k,m) = find2km n'
        b0 = powMod n a m
        b = take (fromIntegral k) $ iterate (squareMod n) b0
        iter [] = False
        iter (x:xs)
            | x == 1 = False
            | x == n' = True
            | otherwise = iter xs

pow' :: (Num a, Integral b) => (a -> a -> a) -> (a -> a) -> a -> b -> a
pow' _ _ _ 0 = 1
pow' mul sq x' n' = f x' n' 1
    where 
        f x n y
            | n == 1 = x `mul` y
            | r == 0 = f x2 q y
            | otherwise = f x2 q (x `mul` y)
            where
                (q,r) = quotRem n 2
                x2 = sq x

mulMod :: Integral a => a -> a -> a -> a
mulMod a b c = (b * c) `mod` a
squareMod :: Integral a => a -> a -> a
squareMod a b = (b * b) `rem` a
powMod :: Integral a => a -> a -> a -> a
powMod m = pow' (mulMod m) (squareMod m)

discreteLogBase :: Integral t => t -> t -> t
discreteLogBase _ 1 = 0
discreteLogBase base n = 1 + (discreteLogBase base (n `div` base))