2022.09.09 Math 3600-001 Fibonacci

382 days ago by calkin

Let's compute Fibonacci numbers the stupid way.
def My_Fib(n): # This is a stupid way to compute Fibonacci numbers. a=1 b=1 i=2 # This is the index of the next Fib number to be computed if n==0: return(1) if n==1: return(1) while i<n+1: f=a+b b=a a=f i+=1 return(f) 
       
My_Fib(2) 
        
2
2

Let's see how long it takes to compute My_Fib($10^k$) for various values of $k$.
t=cputime() print(My_Fib(10^5) %10^20) print(cputime()-t) 
        
38285979669707537501
-0.123773
38285979669707537501
-0.123773
t=cputime() print(My_Fib(10^7) %10^20) print(cputime()-t) 
        
Traceback (click to the left of this block for traceback)
...
__SAGE__
^CTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_24.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dD1jcHV0aW1lKCkKcHJpbnQoTXlfRmliKDEwXjcpICUxMF4yMCkKcHJpbnQodC1jcHV0aW1lKCkp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpgOjQPj/___code___.py", line 4, in <module>
    print(My_Fib(_sage_const_10 **_sage_const_7 ) %_sage_const_10 **_sage_const_20 )
  File "/tmp/tmpYZmjtw/___code___.py", line 13, in My_Fib
    f=a+b
  File "sage/ext/interrupt/interrupt.pyx", line 203, in sage.ext.interrupt.interrupt.sage_python_check_interrupt (/usr/local/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:1891)
  File "sage/ext/interrupt/interrupt.pyx", line 88, in sage.ext.interrupt.interrupt.sig_raise_exception (/usr/local/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:925)
KeyboardInterrupt
__SAGE__
print(i) 
        
I
I

If we only want the last 20 digits we can do all the computations mod $10^{20}$.  This will speed things up quite a bit.
def My_Fib2(n): # This is a stupid way to compute Fibonacci numbers. a=1 b=1 i=2 # This is the index of the next Fib number to be computed if n==0: return(1) if n==1: return(1) while i<n+1: f=a+b % 10^20 b=a a=f i+=1 return(f) 
       
t=cputime() print(My_Fib2(10^5)) print(cputime()-t) 
        
5003838285979669707537501
-0.09899
5003838285979669707537501
-0.09899
t=cputime() print(My_Fib2(10^6)) print(cputime()-t) 
        
50046042277359244926937501
-0.772244
50046042277359244926937501
-0.772244
t=cputime() print(My_Fib2(10^7)) print(cputime()-t) 
        
500208210416153997120937501
-6.900223
500208210416153997120937501
-6.900223
t=cputime() print(My_Fib2(10^8)) print(cputime()-t) 
        
5000061634304001519060937501
68.576074
5000061634304001519060937501
68.576074
def My_Fibr(n): # recursive Fib computation if n==0: return(1) if n==1: return(1) return(My_Fibr(n-1)+My_Fibr(n-2)) 
       
My_Fibr(40) 
        
165580141
165580141
A=matrix(2,2,[1,1,1,0]) 
       
A^1000 
        
[70330367711422815821835254877183549770181269836358732742604905087154537\
118196933579742249494562611733487750449241765991088186363265450223647106\
012053374121273867339111198139373125598767690091902245245323403501
434665576869374564356885276750406258025646605173717804024817290895365554\
179490518904038798400792551692959225930803226347752096896232398733224711\
61642996440906533187938298969649928516003704476137795166849228875]
[43466557686937456435688527675040625802564660517371780402481729089536555\
417949051890403879840079255169295922593080322634775209689623239873322471\
161642996440906533187938298969649928516003704476137795166849228875
268638100244853593861467272021429239676166093189869523401231759976179817\
002478816893383696544833565641918278561614433563129766736422103503246348\
50410377680367334151172899169723197082763985615764450078474174626]
[70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875]
[43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626]
a=mod(1,10^20) 
       
print(a) 
        
1
1
type(a) 
        
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
print(a*10^23) 
        
0
0
A=matrix(2,2,[a,a,a,0]) 
       
A^1000 
        
[91902245245323403501 76137795166849228875]
[76137795166849228875 15764450078474174626]
[91902245245323403501 76137795166849228875]
[76137795166849228875 15764450078474174626]
for i in srange(15): print(i,2^i) 
        
(0, 1)
(1, 2)
(2, 4)
(3, 8)
(4, 16)
(5, 32)
(6, 64)
(7, 128)
(8, 256)
(9, 512)
(10, 1024)
(11, 2048)
(12, 4096)
(13, 8192)
(14, 16384)
(0, 1)
(1, 2)
(2, 4)
(3, 8)
(4, 16)
(5, 32)
(6, 64)
(7, 128)
(8, 256)
(9, 512)
(10, 1024)
(11, 2048)
(12, 4096)
(13, 8192)
(14, 16384)
n=10705 is_even(n) 
        
False
False
is_odd(n) 
        
True
True
n=7^99999999 
       
m=n 
       
is_odd(m) 
        
True
True
m=(m-1)/2 
       
is_odd(m) 
        
True
True
m=(m-1)/2 
       
is_odd(m) 
        
True
True
m=(m-1)/2 
       
is_odd(m) 
        
False
False
print(m) 
        
WARNING: Output truncated!  
full_output.txt



179158598345263475386208992585005346938349146242545646829592599999394110\
423357740820946211528990019280573217795184883934983636975912166689508837\
086953661633171840052699683864667218817869022893928782295781145688980867\
287141190670554903130271192339182815548630630458948050592804876286069747\
956968451073078855821216327579242311191586043845731702980963222321992318\
850095890575229064119237999791543448917039711261770254461753426597715202\
824163240227972558055540685772476870168589425862704164144163970369385440\
237286074047827480461635395756058431201892646010375788509743295090915220\
770142432787014085480653364626698442996437044995051616118879718322319256\
414911718390754923141654921787609485605504441878754627509360850532712038\
877013520481856530335708091200145767379076448672362366993255516424272079\
166167571695799394002812308555489443621630852634221791418200621239774367\
963699583619024222989393407287615194328429651365873258817291910568260738\
181432837677248158389299575796379748817288572487866773999266015032180852\
122490442089318115713760227335117082465681320825017689399974023272275677\
027502191857832898392764055410305294946864282220120419872698212125831809\
355925754026969828939119581213092946768247969295633548409286633900620594\
244238170711937220015967770018519700873385378094651922618748163795981092\
226720794660470079944193724139180114704616362361821441289655203540456227\
393656230947861343318661957595158183601767725088303035310274134276016588\
117275857801289010511836241766592059424598996809268446346764928574331484\
399353091380355613732877034403257087193010451346616164936610337386979295\
462507745036302043748185999872400379589098827656424897534043365824167647\
078374289405000326123332990458696204438775662499872503806935175625541403\
028670595950422821191253424906867028064255572696388621224120417283603054\
406736061034838097941298533582887506057205652231922937227444373352344696\
146352352917820182454289164737365289949929405457033671054459019884561411\
622935612730562868100792670847717810237288736792679680646226237948878169\
964410157501420219912625728316527080907274928932055873221907841808477285\
784166155138274735195160377125316086812328381664357850280017743754054192\
664394376215146172962447224473754998778825556846811453167926415797083018\
188444881703722087965231662622641027652106420252102952482060946077270720\
546241460143513517992046064994194153387389540851866144560403436020269616\
384585328856278944825917355765690261656539973943613654832214463691539786\
038358852867789447804732555747333015749143534884468618766383343718571425\
407458324750360538102737903641023925961989454994328749566696501046190381\
322282157029806746232557288699817129719012594470760447622743455113885900\
616133254271446278280025570587784320020938322278114357865726444377204197\
768863369408301413215687910862958319570911311771806401869223832644546068\
397235592202040640220493704062631070272102397349755259814116859024680796\
712798357901163298313911701206011873328294009427436025829361014609397071\
543056502836183598614171835353309154142422602058106096501356855360199245\
725287583810567586614923245667023256396665536732912845993265056209892688\
458498033963423440933020631533712504798183306632610668164714079594817824\
722365146667902023602007433306326488355700072576328145622555601703050619\
601950990633404567529714089820974771983540715761494600981481779508417836\
418881978079495798281474021301875899581946903790593064489932024204015622\
960884778408387637727954674207583503275151751363984729792130357291334892\
006963344072328537504763783462774597063821995320174442053718150942531320\
611809072760121064434377086332367594058484637624622886117278325109068000\
196185170438315161415228602085572872624523321602798965027377315236028801\
822182112388152897500709249259058748334647784747341397272464614383137486\
515282053476743796986185330565278456138153817324956232744746094137619266\
846002756685280449443838876607097285349201278821564107106216040816531286\
278448311009149491447244309547607088385915262025496334258983257082510044\
041706536743404215113356939093204116870335241166683636302537030052789544\
205224375063817745313384668336506446591449678038434857200715241522716571\
121003898933117425216203331281545705101708878391303455242075745012848354\
292585873217344594344933465710119092716701301733343573757493040225761561\
378950230349435305863582472089506705142794229727647246551295878455153582\
015354684767848083970579317425480890607888909664060465707284091746497822\
462631743689039937038229091422345604847263214773580227388274480422839899\
785551361270384793472727057284033279480701671599498977552037127338157828\
212220979522487073753430602055915852827855311722943955333696455509459956\
418229529074740426171462818460026190589140263135146188434785639143854666\
282302904490029370456605443199565964342967254623563946376525441723740173\
372660726488582881872697988623728783035820393062592132046155964396655816\
627456339530007375491692852938028901317542876330528384075163038577878181\
601521673728552509504721389468238671323988791463711263929646070514115572\
829918547982330048527985211347708656432888703047488808856064611433656112\
321293837611038061961666683296038127184630325385636706920998561551462407\
353101531741714537649401470052265256702327439402919456148609166473091921\
263827179440664879721410588644694560746771821791053003907677943390706708\
000989313209803526854866119520298232759987670312372320723462910056993401\
463493248613383045599451902980093822688366478927636641485013960772291084\
472045724980612619409071644144792366128224090971812190252765528734896375\
337890418585149113743388490323912556779264458684109195070449795811587747\
831812485839339673832349533219375574184857244260971999163514163692779081\
515052599365186120235968490075850962843617672512701638245821149870334214\
975242413975812620517023734813743519313250902335021081156758163472793859\
851376246322640846877064156910925745019414142343448586823657227685895618\
196711348364871206016209212434088829868662339194609008316836289887479615\
300713632119413489739406701105968807587013200361257371946513697062123856\
572638497916897201105746045228257301746149660711973750251575873428702428\
694784698192677388619341223269082885881552554874829918989763094360767366\
593688542250457777552007534274330900288478796125901426991659821443908263\
085032655718717104314610302661816493427727990319707616590361713150827156\
645197176584138796757236063903609393324182447946269074263589664060145505\
817400051362714214216173557515272488363941567358184241949913971871789186\
341994643176249765076039354604475140998536163681225816322709528336986018\
544304152761344777101395595284984553945568181516236354388463053014390382\
059084136245773947181714243203232195546149724435164881519770264429198052\
688678120669231217429429247398758653648895723061673218816356718024482961\
248660348976779768927421341205255674895496056826969291244911599410068323\
696933246630951450028554336485535995941546660640464157155319177428453913\
171294092110762396386408684002456109435838961974270742009987284387249561\
616804633729381661308760564803829390129393662215415021746416044588113701\
663529196947557348695579392650987943011819785744183635476230112454356992\
129233644515438795497472274688039496248447463749658071527676680302390419\
200531201021935363959251920830875696863620735789123137607783343681776794\
051850143597224953104461666350514861992140697972223113961301419676231236\
765825753433052248303770214648389803486067087079929294270909025896547390\
185294720055067336868502769220156585400012822478178041890060620044666854\
574942953891578060854796421408880563584536753193941488345985724371786833\
453815650215939293576766040185527059784510789387065758095764118813296235\
562428751485792147537976304316441643870462217486354911336829528242324675\
023031193940990756180226294639749440624609560893494450215599876882680273\
168397684961683551012934366079800470631311865713493499371919254303529517\
550206945299708293094850864129994363116123617603778368524396342092589937\
836564106659758197535155954376995000819036507163133094919790699184914661\
091683866315914492433999175806872241852072917192820125011673890013050577\
116979380075871073045535959787568233109177311480291220370415467216315794\
843607554568220663106156542056591252008969941952790587263951525957873640\
624864058431708195479343274626928616352363583250971580153723927798329245\
077779059424932024444108281223979244145481938020325282657392435759520398\
797178813828011486645183537557743869902519961962676621342853342073035837\
869381507215514909232274905532536711094490632406133071337518160385430600\
163432869020247164058135162742381651960837200138925639820281343355684478\
829951690072501715099460136767081797774824253357317678360503466131765239\
842084539449695837942569948543430916007259929008692452347333888274811878\
549626071327877836785110485061251510079924450786788833534718045912974959\
895906385829508341877441505088161124253193137660231123555380236907547825\
695549407920737519602648234140362864150622130426773703476166525708551531\
487077983623575870694361478428716488965971151476275061270154775821145990\
746334264347629794308317192788601814794206882510266674265578375734322777\
449098400226092848795340487504129032640091723614607102237126739218513385\
188027174170632108527616907297074448365554509214080086063551752601063874\
524274867765089756707787875974305640133941518918767141785295844233741650\
639564812822999182483459599883310129142689432147034794848600694080583859\
263799214763909238207867859219480843953849899947470444874555841824589775\
575583363597940817143265740307285326678495675314112991088987497694216681\
129946042636911572252770848125084597908882374340715667337888458089857646\
942415167546741130171075767269262558445351905333023169289058323346330568\
827722666904071458355656012063959372557117774228830807202538025893078794\
386483227978829271714201363667269395465301110906974042967326108465130060\
621374943076584812246116102572830867199135542349572327855499236043143692\
992768703978453501297165734411519027951075690997839465151227983358063865\
618645742422445243429787959155653806782574104547284395376091379776532683\
206149771916139597777958723032360053874530028010282352147682022985100830\
288200414320588128151953169469623724978699023645258879396478549844629201\
460427292185657731299210736597360801006975106381995337282263704932227008\
255387971651485713759897316406449483460429664476325455209406216123629954\
625627718875807739750190841157852714087164901159213473609537593459530875\
809501618892238249772902283909003739129985209139635681996602657570706208\
522122617723991228921057602650846251739107764983885701933595450940933431\
944470461328113185952969042880398666713683217461719033937481588042389330\
944430236241306641562143768947941133914717812151825059110153798291747013\
586416353387078246185176701551824858105221037681535430548298016058490582\
864843681178796102553594328996232948800021629308027731140765276886947408\
532498728091014365659181367085046475752823431415138020698744835772750910\
633290469209924929549467285450210673083462346560308998609640135403902700\
923643340752786111518851360478736263123458124286044100065899984151820563\
334875647476423791758831719161786144708139549962688235944457118978114481\
236345721413149788064199456799882735849966980373113534113948772692884145\
016729795119339402327056760445898925579244297729673223232462807223807026\
969364300475157181391537804497300705804754796095677235457965099708277843\
085839506462046547483662899796226279390089944495232845111191780892672647\
018576099815909528898004008609951571500381677305915312161293746216562904\
111786164935885205293896249466233883303444805309984085853866740637962722\
002108886125156697304612027702620668716216679315029582561451895056708679\
071849664589223920412387595905079535477601500982032729508802642336293814\
145994966105304285743593084583226749022553028892955260674324394588959014\
112809471593655159219824096073974743854243812321223651440861490734066902\
859264071937230517965969124660563093782099102828836638344225783554654048\
163263062936044171716124648493649179250509534965035689993093081957477335\
758345474331563992888624732195992775222409640190386065071564197409646506\
047633342089749396990601359650239185409040427095101835110425986157056628\
539727571642313164043700275459148107981102726118764372744158456819172298\
140800583970515545905104660478539237558879634592346284039074179365807317\
504435554342151278227799571020105845741291690545281146831123099390149650\
667796310518828337123246887020071436442788138547653068741452043642827312\
051884132708835132369365836491576667790467213913557847613496822807988281\
426883871850363988898509925253217079977095087724996432423496285891262726\
716922148220406023679252933043301718900143560266383180945338834799675916\
288062093982417767981059257890719800237207872857492448043036363442554596\
112568975816349956721509802941294862359436564529292598067075203170933236\
101264220462659832533084858651881883532791511642501562588917002615123054\
294693093950279345619059307105573109344709460933769835757426880179469026\
107270046000809365475921324900694887029198910346710635083129903214096633\
303121815765332891579236223972289128832597764230743578554394985649181479\
793254935052725357117171732206931096339189333583920578335756308084772142\
420005620921083654958044815145780148802197747921754826037163227196518066\
307405024463349530142360096373649941287733103437767036502786801805202316\
138176548953468984686008941211789558518504325814323328398750518979601348\
024904585635137784021842112201399204743921095560859854545178493078394048\
083310122266177186260170205239350578204059030498115157751094089127881329\
964373495596782681394828956280494709386305528068295568007149691274938156\
985540752147319552271252040491360035142737753773991775900796487644878835\
639676120466456404616284022870345125306250204505344696050923484982227802\
810260722299166261657121641615453929845629576303983690568101009423239444\
959287885215068322997414475900481056159883210650813961533569739340458182\
184988321553512343218754891599763391158586526824448242688291476485574854\
818748959280034200530959805660907916801802296661605186663767243570350153\
910106628679466275733774373990928242252649195025109506603863475828224531\
473991013445416395785540912760858613235979502406784682954520519666772217\
823695858910954619756806784381540853893293888807396311752759245414775050\
443375676603420666944439166973336449554298856998027219394288428893510657\
171224200556756062544830626766573834616196027525732236380992152767689672\
519882366160378405748921971766125161452663787622514374492587019762247659\
752209906766015307966992302037500865937709031989272074158778770822340549\
372730270791975104832679704823639796080967349059878616328124678146756226\
922844542311007385149016898066494790724547396854466816882017979764573127\
335169222046184872365605429257772468266650612408973326609594407449099151\
035710575387259247631196235413818846611290997108937764849969087869380015\
473396318951828601653885770989413335825809271006535309020597686721828148\
297460153158861060254329509343916287755141918180366962015355736088512363\
283054678089927448694594233570602783477223709956748078619016884009498616\
663231765835477580606657665212668356924642774138798678704927429597225733\
591265717277354803371099277923062844086326898919407131556649908189945618\
213439705912499762363717291921079180424309814278389292338472058224536420\
287533718538610076975053819493744999706629419743457129148063642210853664\
130656011364145518165551716722882207059871440281855830134859496965548390\
553266523109385935412101291774755818649928572614245991904298250577288309\
056080354514292933726730235068763156518666596591403936755061617563320776\
416771649704640576843453309081117805649758187579992987856112550888581393\
113648133170509337224754190574224672039676119325401226474686218104953153\
485468312315214708582272839532320448637563668296961457442228291651960361\
446745161696053397775334725256901112454943173808429511992976910090280414\
149783537557553925891982317993085128324575173058000729986203975064174362\
524196816224738075000800048546968528611687780907862303027251855515691580\
742511627103404661550200542628103725594787525085635649470421564890679795\
775999195192427991353244492924552289624081169453136449322487833183263839\
077258459330257

...

416707082955696602445725634879656393708543848286396759968159881917893480\
664011343222965627505577486836970580432375136588306142009514575392195896\
193868419031269247752225917336709939953685541767881326245923030613136513\
559249774347438727361232276147412158106318591864268041598160470983295540\
262173872655812017892916244551216816138261271973056266106848718555222207\
848937074827527616791186188841646862802539024297011621817657819608429850\
121858790451066791931103392609631021390549228174916874211559522284733370\
587980035950370995271359852040791751726926883047166230517604589013652581\
930033414016032516392284652606752005867774298717114213552870454408475697\
129721659742272922883266315035959559056313782015588479381298490099389467\
971844567028836245071313283707778978393937474292962415686409171133897870\
289341870112103242934941931007709968816503280612731810638384979297658273\
754001907357005416423256573665456845780976760232136750011524826573755352\
383813300778789380171229739697824338596937492756082783034109767291125983\
956346402198039708079804437030745034507444125571937791841161247621356487\
540061161850339230336763178180778515863220040436327509522492823668109642\
807314085505368015419482709962191649661347580649823226381793840539670968\
954340187527594209817037086171331271100525469000062864426565342071554668\
062792271850372265469848449052219074786473678535105725999057480391080094\
150140189220600200460874492157349728414506050502715270173363730674111411\
636841099549664002951058143092856480354489447379418015126741187473530859\
131697697348853375285782005339605099347103173239334191142308498416975600\
064712712736742672129616631321105206689471364383268953802947959086306959\
433213958985401634808582330975081807208679018368029153065427564635408808\
082207560743152370072481062360075209999351570651351151810575043511446075\
742117575798574837772599862054094907209583542477124109308435612401336052\
208160389487499124688517840300528012514703347447950804241500798639723695\
493018124336342888763932233714848137849698389916670200824187447474013989\
276415170179643236497976519578232678262906302468560329206505915714101039\
959045545016810052337625315813226008427238669848144797003742816590529158\
714111850448790905936366115409390713576686781989281705150301051609557767\
347423859232979791606925425591067269321722788806689922675150800126635961\
552354686094915234212626972968894033227402725404466188869184970252402939\
839449664796544852838777685986668600023033503666576256058637127828626447\
651636424249739020884993480847188341883107549217976150006656348337809995\
094564914697239737943015375957420140358919456866653448806630339316119310\
455138673693866511845986025069624280368138846691251898632580001071397453\
073256365858852097386019463012039096655100505305645927046143465893614885\
001578856590629041355109073825528002177178043308546468019330950842617336\
097489926959757963405367054833804616832964043025445527379573163645706859\
002891268936405130745444082281933553811174043565460722963350785579345353\
032049249738950529208768778448683214323614922817114286700144165657040258\
606864944014057720353066236583004141893597461286047036906871568938923271\
826133302308465910659500966644440686016014188251528647001298731979081458\
552354753888433186142271488182704035322447350419317064298614589879185153\
774240030901634356944253700664527098342018693409249289509618118299487593\
111747425122003981494294443465688535612305421656887423724531585857082198\
049684987500084550713471647724080900511735936534008444797093484287595970\
571510419421078357265788739962831444358287640769877938906365617247917869\
510113699007495320916104422955701428205363488832820581483386971435702289\
831855050562089752543067137757692608991274990966591417700047839468835524\
811085388426602305526057299119957434131418312432598286857346805554313906\
756965737569865625360927385423009926595873246430205465843565657808983232\
309738474071180699340624982719235233154109242492187403143433265319291226\
229228170326280262469812990283696880299268022400047950744978888024227893\
187814931805937079058557238395469644453232259113322381134027799098699997\
181876729333778117258130943973963755703474485876339030215181476172635117\
757513671312224791882305169924434551788305038599517790950831780491798280\
207504834826630890371327367817497695663004416954810809817848122074109748\
026508649589741363165313499093959622132773922508177035251797401989916402\
096983289929354504426701684588028568928412486240310522062891141088325425\
046444682608521876405891753860489427314239503149130295921157497585390548\
823885531599703557941250352687673463603930272733690351228255386214196047\
989972297303423429604478147708772094698490020087919364125102386287057746\
170763621959865408700167079789852037657271184180253105235756501521695153\
301883475474075917454383468718170680933838615827216451927860837413896368\
447305761923409118352375925118257410400069932999125850271186776761848435\
056713108592576839072594103535514453273916910972292753099376507128292006\
360246918500076164185844906587950104125352967825769042846879067039732118\
037242865552953849808140039667836502740823632540711563301493333477496703\
196696705795846593136534597153671550053565492590770552891027752829355074\
157561495648917949535143181440050448576241942023974192386431717312916290\
146940908254730457503577300069536529958887173919953397333842071954628765\
563591957957379606638317721648515827298842078999860107823225891602107570\
725404693999204825057072176604167150014250405941123798943940781031148682\
065724936410095754015438845154320843773992907708986434392423791739170032\
846683793737350165353310482004626097306477171120967018596765006299461406\
052569923617224195693953584595688624439894837880369263465015657264266102\
322537052112583828758918773909839046845888140936950992673499099563413860\
316927598037519938056285155903034798083075326677974814030699581781689693\
555147524764915510194962389173600082804999605044615056703296025427559995\
289117784453789408494966939979690840776999532069754903854871468651830475\
146178769103856212994630985847036830796683472070456080633084098761734912\
885454356724042247118720381758684485167885028851403040860222684752062854\
636208123621765896704644919093192506549040959686782538325434180146827908\
292896047753329167622423704866552393682655122658162115599457932280697179\
861233397114388741257231030353453081465190712860708291297160124186255161\
878820328624686403059787035132543337237443216279738768515117420566351036\
290137968095161365182564188295074069073551590726188358501855945771463660\
053817786884259682741682110255910469879763654957947756902855632705257201\
469380096549737264536051706057502077120187890919693684891512026749329896\
355293087690539605079993184573698900761846270563293856475234270938287430\
693901014677958005645964391961669720537443552639650965295199623237557240\
688207399536898737742566402807902630185633648345289102742690263540523420\
370927509312640340119920827429841655312449696594741215453838968847195250\
450909339552646759236057954826599356902371826415613011030338475369680301\
705834580452631169282718695531806917915486422792289461868815365088217283\
955808643047055340162475348942431252572085909842664836768068528580847328\
787105321299760016553341261812115037149001761096311755493753363420390957\
608860596332009097485229114830043639183396794114974643621540514441638933\
074216010053747870508412821803936740638945986971506153751302100423592353\
003683437459640306793189857919894393012477820131674037223022291837386526\
131916933353783134977107484133873415895375175473966515490708049789580347\
632041885803168668286194459262496766755069363867730297608762001828980394\
099120859583657198620240601217720199995453109885584947732526056808732954\
687543366991576002512952799109601799982395009980584163353732381380836511\
949473220401704439393280892555916904059408712709516325626413903188562203\
459867465817550340572484819639994124916906284299565335028856048671175381\
257671409536528158537585014121242025886161131168553730419418418185141652\
741748283373718051646519354127343936983159025280472275067688809356097003\
072396361630384641776042795368250581441096731242156929321194472236471136\
187177423364528498801665549757590790092013524914598267210449927439109607\
560123351809832372728749797854335458417292819538208214460387121734893322\
776959685179032192281704502323111777588839288337692495939676596229462512\
493385400849998697194285314572974709851989230095152998170479200312322890\
594284977083139735554855103702372552803098982609403731536989184076475403\
158784719461925152015161346781750700653657010199644049982374333465646775\
884021634414619427855767450541473448323174604221564208313772770353721899\
405483960244961630327499189057109863986853870359290371869085128008553617\
388887176536259589368609222020986926852306854492617822834867912965464126\
461068772127599574395614053673748292377543428411688607173880387385135206\
069116198141447062051688792674792921518746777418536944872104398780656309\
685939687324482434711409710527609259726561590194465291677700880095712253\
491818291521281044597231467917961325129670176417283853592290073472531602\
669594490706271059984474267962131138885218115114129626524904124441485959\
245625107783099159832210996475592805896626469535156516819074144857803834\
667610653365953820340782352392896394532090240983143689470370825070099465\
246746276513181182490000777219734152401833266533429914130250878995610374\
025552004613235465385894253248494521770026436712189121585876715330936974\
713404602382340712469968447933876104025287888414785322663845007497086624\
383524271581576032777200630665148587197622673723125598567750080453926532\
322582674130929171871970969903150479273457750058415305062823808966651950\
936814472619131874024095968628194029507486282558125861925311672766615246\
452874205274922245697692516155506160387224304309195442294966531773866003\
606736332217668509590854026695259918365434642833444728024144600906041104\
546597266044596292209534870985044941682592048515654383509251501708158285\
748668686925442444482810529291858026095169567898137202617109701345348630\
238920738844806588949056632345923303093106206080301115993156545942977083\
602893051873116575277016396878971028994678987596509264910624029484609363\
091451130843829742912785259386007542089565953206338357354811687665357885\
448290072758326155430813475301564420878471824027910040379171705818245715\
713197741371010466957987832619728378946724560448765689988313518277312972\
280708186748709855936854458463700338825438535835617797523316125316842185\
050669458166844460793666752482678022241665271112202472418347226896009082\
540913478014239610253902354032243127103796481713249480558702107725957101\
884526197490166099369653352563263347012130543682460577586047221380824672\
040941768380296903950527856121976768730794921886877911609304876089086443\
417640296948724514714426186797532466030947281388690719480005802852052525\
326494206365440451470222483792850401106312320467269358460426801670880266\
246220631646144989210446240813288193022584520354547121608668180375597340\
647032042043057035737947294252985897640539337550899085259304520255909583\
090803312132927974969794961128919880987589109986190325189926933931024893\
207952255525583869676130389102389632882651108101380353116954851655124052\
822138765836384948334707068265444606650446791954231093154419619363812679\
145462367864292252577921955638878182128908536747512429046361876168113699\
977953102145490188575958345257891814130206001000963567503584332528454843\
059352714494415430342296257101895403501508056983245416346581476097654192\
345391697507973973505682821552719147842368884232961383729482408742736436\
837076822040197622034084280584251019323363181461317518851914811829441114\
915752197647466535915393362881029331953062327962287969121113934408420587\
127799363077867284019834199121266930607646221148346823261014159974696367\
476442147715183763649283358983782770708791312491115576588745160905471772\
089974420804792582047768473898947977293121899731613444803570670230091933\
740231538913363456517942973311357496056469759204022317246869043475547351\
845406028082740195087021223117511977260272545592775872168201600538084232\
917230713791173472568579364660703183450732427133577580290972673054833469\
665231699199688130020726354042131443547333261554183023958224760110892615\
934047774392663536072361652921549412395611544855505997773310903109108920\
128424602954055230550338993778510726012460223778237483337131691422010323\
560453873036386590434713460912879709740595223444343784982761796782845917\
659484649360726713276285223232433119770965632944059736682153720719131914\
423063642418327075434585410222210909684775765053072550115403317637465974\
047070699134628280427737180180484680981789969318337061277382942787536123\
906231189374345607962469980161626668882996011357439900724106067804439619\
452610804949034679125495644303342201314882496986296896136200605526892383\
291548556781481481867982362153988995867464851331711981061245548731469365\
071469897006020000457618184610217257957758310070911462091988200112338041\
562096523571004832561256939821952314432033837946599685264334590068900353\
192254756370484981835574993432800616673365458211459468009018614735002208\
058435546778482654105385277821036584655540898338096216283648855057754140\
770008816727520563231558107828543650443857771434384518046086873407216823\
177110532811339740626873084431958280658944793816500978747312252280405608\
071946486758183847187517942205615837781884592287479192877607782540025510\
679294977213059383292149301978600865436242135059248053580053713827321884\
514458624365901793880967321215110355386270808269365040842858245296696106\
119386350131664986189895989460367159924567589063627848477058421537314900\
540127037036959370866524301925095719482056830346437635995462065693875053\
119744082391377631556371846054195656878336643859497774781403170494711271\
939072991202525689311110096384595156342299867576130605107071477758059286\
940333107419262842535881386820255623429817666043909663674657300917071996\
154470656763564598006054049659670759085700864192694909871761341625967400\
232018408577429596441650032877025376033696632600846949239833820674058166\
377515906689467180042942346052069412505318562460433274819675618312599330\
126484827746833047265807659514644229991878251529504146938526666012151091\
291074670611116117425597293008630220673856320910897972429142500624087536\
765984324318102181163394824765030523844294540180666921905629269013944954\
147841570505463882072340289597634212887130681519247549386863383288814258\
469930786870859446870922136696848104833164450579829324442065897130480545\
523118382405213838478024320524629310658976894328162871458092128421407054\
534922812352367392863213543108485646222376372706971779401635521000161884\
867093951531879050141044556725573620395362918409181179857759470044573631\
724228523074846652263141792864627076522674985963005249365937999439791523\
685582473311229193571475312530008735433627855022953331498745754787050691\
442772068047227758486580937421006361481196851427228115854229284553806688\
854157556091278096486553188355581099049783456716891964290862157845964872\
870417397592733849790771514571367646763371728006818160540208379992074966\
409162431136719308092913204548936443646005469056298954804691951066465178\
358669203911647141345485128429167283450976986153085768503004651372559712\
761526559309040099789200273375559225417970413315281233111764697996958497\
090658129727952863800311899111585614547009406040781748843348263858467545\
141595788894324139989846597874851119773854336794955674365736151291394451\
402347585644697899511805397551366435832477775673524591385437477972071306\
965386453281817465879177361619789833123832255106242397331808988059786076\
325204272152017539180722159905502261254808744647806496455298285729411379\
231557519467828400002561412829993886618995073671400794924179437736330987\
567524266641990417925688135248175879324474101265392090505448090664413897\
341191549397833619197929665247735995093795534962198407684172729598077343\
718202362337943107921253235048583132157861347742713192396480334516272283\
815683242250470365622971014918198349699987523800863479903382053725454303\
455842797669252065510565480118676320189636165736099982753136585622743883\
035178373941908942170430436066383093965365651328964136777035738951810272\
088329352478078442471834367424933925364687794016698836965438348196245221\
3484429642857142
WARNING: Output truncated!  
full_output.txt



179158598345263475386208992585005346938349146242545646829592599999394110423357740820946211528990019280573217795184883934983636975912166689508837086953661633171840052699683864667218817869022893928782295781145688980867287141190670554903130271192339182815548630630458948050592804876286069747956968451073078855821216327579242311191586043845731702980963222321992318850095890575229064119237999791543448917039711261770254461753426597715202824163240227972558055540685772476870168589425862704164144163970369385440237286074047827480461635395756058431201892646010375788509743295090915220770142432787014085480653364626698442996437044995051616118879718322319256414911718390754923141654921787609485605504441878754627509360850532712038877013520481856530335708091200145767379076448672362366993255516424272079166167571695799394002812308555489443621630852634221791418200621239774367963699583619024222989393407287615194328429651365873258817291910568260738181432837677248158389299575796379748817288572487866773999266015032180852122490442089318115713760227335117082465681320825017689399974023272275677027502191857832898392764055410305294946864282220120419872698212125831809355925754026969828939119581213092946768247969295633548409286633900620594244238170711937220015967770018519700873385378094651922618748163795981092226720794660470079944193724139180114704616362361821441289655203540456227393656230947861343318661957595158183601767725088303035310274134276016588117275857801289010511836241766592059424598996809268446346764928574331484399353091380355613732877034403257087193010451346616164936610337386979295462507745036302043748185999872400379589098827656424897534043365824167647078374289405000326123332990458696204438775662499872503806935175625541403028670595950422821191253424906867028064255572696388621224120417283603054406736061034838097941298533582887506057205652231922937227444373352344696146352352917820182454289164737365289949929405457033671054459019884561411622935612730562868100792670847717810237288736792679680646226237948878169964410157501420219912625728316527080907274928932055873221907841808477285784166155138274735195160377125316086812328381664357850280017743754054192664394376215146172962447224473754998778825556846811453167926415797083018188444881703722087965231662622641027652106420252102952482060946077270720546241460143513517992046064994194153387389540851866144560403436020269616384585328856278944825917355765690261656539973943613654832214463691539786038358852867789447804732555747333015749143534884468618766383343718571425407458324750360538102737903641023925961989454994328749566696501046190381322282157029806746232557288699817129719012594470760447622743455113885900616133254271446278280025570587784320020938322278114357865726444377204197768863369408301413215687910862958319570911311771806401869223832644546068397235592202040640220493704062631070272102397349755259814116859024680796712798357901163298313911701206011873328294009427436025829361014609397071543056502836183598614171835353309154142422602058106096501356855360199245725287583810567586614923245667023256396665536732912845993265056209892688458498033963423440933020631533712504798183306632610668164714079594817824722365146667902023602007433306326488355700072576328145622555601703050619601950990633404567529714089820974771983540715761494600981481779508417836418881978079495798281474021301875899581946903790593064489932024204015622960884778408387637727954674207583503275151751363984729792130357291334892006963344072328537504763783462774597063821995320174442053718150942531320611809072760121064434377086332367594058484637624622886117278325109068000196185170438315161415228602085572872624523321602798965027377315236028801822182112388152897500709249259058748334647784747341397272464614383137486515282053476743796986185330565278456138153817324956232744746094137619266846002756685280449443838876607097285349201278821564107106216040816531286278448311009149491447244309547607088385915262025496334258983257082510044041706536743404215113356939093204116870335241166683636302537030052789544205224375063817745313384668336506446591449678038434857200715241522716571121003898933117425216203331281545705101708878391303455242075745012848354292585873217344594344933465710119092716701301733343573757493040225761561378950230349435305863582472089506705142794229727647246551295878455153582015354684767848083970579317425480890607888909664060465707284091746497822462631743689039937038229091422345604847263214773580227388274480422839899785551361270384793472727057284033279480701671599498977552037127338157828212220979522487073753430602055915852827855311722943955333696455509459956418229529074740426171462818460026190589140263135146188434785639143854666282302904490029370456605443199565964342967254623563946376525441723740173372660726488582881872697988623728783035820393062592132046155964396655816627456339530007375491692852938028901317542876330528384075163038577878181601521673728552509504721389468238671323988791463711263929646070514115572829918547982330048527985211347708656432888703047488808856064611433656112321293837611038061961666683296038127184630325385636706920998561551462407353101531741714537649401470052265256702327439402919456148609166473091921263827179440664879721410588644694560746771821791053003907677943390706708000989313209803526854866119520298232759987670312372320723462910056993401463493248613383045599451902980093822688366478927636641485013960772291084472045724980612619409071644144792366128224090971812190252765528734896375337890418585149113743388490323912556779264458684109195070449795811587747831812485839339673832349533219375574184857244260971999163514163692779081515052599365186120235968490075850962843617672512701638245821149870334214975242413975812620517023734813743519313250902335021081156758163472793859851376246322640846877064156910925745019414142343448586823657227685895618196711348364871206016209212434088829868662339194609008316836289887479615300713632119413489739406701105968807587013200361257371946513697062123856572638497916897201105746045228257301746149660711973750251575873428702428694784698192677388619341223269082885881552554874829918989763094360767366593688542250457777552007534274330900288478796125901426991659821443908263085032655718717104314610302661816493427727990319707616590361713150827156645197176584138796757236063903609393324182447946269074263589664060145505817400051362714214216173557515272488363941567358184241949913971871789186341994643176249765076039354604475140998536163681225816322709528336986018544304152761344777101395595284984553945568181516236354388463053014390382059084136245773947181714243203232195546149724435164881519770264429198052688678120669231217429429247398758653648895723061673218816356718024482961248660348976779768927421341205255674895496056826969291244911599410068323696933246630951450028554336485535995941546660640464157155319177428453913171294092110762396386408684002456109435838961974270742009987284387249561616804633729381661308760564803829390129393662215415021746416044588113701663529196947557348695579392650987943011819785744183635476230112454356992129233644515438795497472274688039496248447463749658071527676680302390419200531201021935363959251920830875696863620735789123137607783343681776794051850143597224953104461666350514861992140697972223113961301419676231236765825753433052248303770214648389803486067087079929294270909025896547390185294720055067336868502769220156585400012822478178041890060620044666854574942953891578060854796421408880563584536753193941488345985724371786833453815650215939293576766040185527059784510789387065758095764118813296235562428751485792147537976304316441643870462217486354911336829528242324675023031193940990756180226294639749440624609560893494450215599876882680273168397684961683551012934366079800470631311865713493499371919254303529517550206945299708293094850864129994363116123617603778368524396342092589937836564106659758197535155954376995000819036507163133094919790699184914661091683866315914492433999175806872241852072917192820125011673890013050577116979380075871073045535959787568233109177311480291220370415467216315794843607554568220663106156542056591252008969941952790587263951525957873640624864058431708195479343274626928616352363583250971580153723927798329245077779059424932024444108281223979244145481938020325282657392435759520398797178813828011486645183537557743869902519961962676621342853342073035837869381507215514909232274905532536711094490632406133071337518160385430600163432869020247164058135162742381651960837200138925639820281343355684478829951690072501715099460136767081797774824253357317678360503466131765239842084539449695837942569948543430916007259929008692452347333888274811878549626071327877836785110485061251510079924450786788833534718045912974959895906385829508341877441505088161124253193137660231123555380236907547825695549407920737519602648234140362864150622130426773703476166525708551531487077983623575870694361478428716488965971151476275061270154775821145990746334264347629794308317192788601814794206882510266674265578375734322777449098400226092848795340487504129032640091723614607102237126739218513385188027174170632108527616907297074448365554509214080086063551752601063874524274867765089756707787875974305640133941518918767141785295844233741650639564812822999182483459599883310129142689432147034794848600694080583859263799214763909238207867859219480843953849899947470444874555841824589775575583363597940817143265740307285326678495675314112991088987497694216681129946042636911572252770848125084597908882374340715667337888458089857646942415167546741130171075767269262558445351905333023169289058323346330568827722666904071458355656012063959372557117774228830807202538025893078794386483227978829271714201363667269395465301110906974042967326108465130060621374943076584812246116102572830867199135542349572327855499236043143692992768703978453501297165734411519027951075690997839465151227983358063865618645742422445243429787959155653806782574104547284395376091379776532683206149771916139597777958723032360053874530028010282352147682022985100830288200414320588128151953169469623724978699023645258879396478549844629201460427292185657731299210736597360801006975106381995337282263704932227008255387971651485713759897316406449483460429664476325455209406216123629954625627718875807739750190841157852714087164901159213473609537593459530875809501618892238249772902283909003739129985209139635681996602657570706208522122617723991228921057602650846251739107764983885701933595450940933431944470461328113185952969042880398666713683217461719033937481588042389330944430236241306641562143768947941133914717812151825059110153798291747013586416353387078246185176701551824858105221037681535430548298016058490582864843681178796102553594328996232948800021629308027731140765276886947408532498728091014365659181367085046475752823431415138020698744835772750910633290469209924929549467285450210673083462346560308998609640135403902700923643340752786111518851360478736263123458124286044100065899984151820563334875647476423791758831719161786144708139549962688235944457118978114481236345721413149788064199456799882735849966980373113534113948772692884145016729795119339402327056760445898925579244297729673223232462807223807026969364300475157181391537804497300705804754796095677235457965099708277843085839506462046547483662899796226279390089944495232845111191780892672647018576099815909528898004008609951571500381677305915312161293746216562904111786164935885205293896249466233883303444805309984085853866740637962722002108886125156697304612027702620668716216679315029582561451895056708679071849664589223920412387595905079535477601500982032729508802642336293814145994966105304285743593084583226749022553028892955260674324394588959014112809471593655159219824096073974743854243812321223651440861490734066902859264071937230517965969124660563093782099102828836638344225783554654048163263062936044171716124648493649179250509534965035689993093081957477335758345474331563992888624732195992775222409640190386065071564197409646506047633342089749396990601359650239185409040427095101835110425986157056628539727571642313164043700275459148107981102726118764372744158456819172298140800583970515545905104660478539237558879634592346284039074179365807317504435554342151278227799571020105845741291690545281146831123099390149650667796310518828337123246887020071436442788138547653068741452043642827312051884132708835132369365836491576667790467213913557847613496822807988281426883871850363988898509925253217079977095087724996432423496285891262726716922148220406023679252933043301718900143560266383180945338834799675916288062093982417767981059257890719800237207872857492448043036363442554596112568975816349956721509802941294862359436564529292598067075203170933236101264220462659832533084858651881883532791511642501562588917002615123054294693093950279345619059307105573109344709460933769835757426880179469026107270046000809365475921324900694887029198910346710635083129903214096633303121815765332891579236223972289128832597764230743578554394985649181479793254935052725357117171732206931096339189333583920578335756308084772142420005620921083654958044815145780148802197747921754826037163227196518066307405024463349530142360096373649941287733103437767036502786801805202316138176548953468984686008941211789558518504325814323328398750518979601348024904585635137784021842112201399204743921095560859854545178493078394048083310122266177186260170205239350578204059030498115157751094089127881329964373495596782681394828956280494709386305528068295568007149691274938156985540752147319552271252040491360035142737753773991775900796487644878835639676120466456404616284022870345125306250204505344696050923484982227802810260722299166261657121641615453929845629576303983690568101009423239444959287885215068322997414475900481056159883210650813961533569739340458182184988321553512343218754891599763391158586526824448242688291476485574854818748959280034200530959805660907916801802296661605186663767243570350153910106628679466275733774373990928242252649195025109506603863475828224531473991013445416395785540912760858613235979502406784682954520519666772217823695858910954619756806784381540853893293888807396311752759245414775050443375676603420666944439166973336449554298856998027219394288428893510657171224200556756062544830626766573834616196027525732236380992152767689672519882366160378405748921971766125161452663787622514374492587019762247659752209906766015307966992302037500865937709031989272074158778770822340549372730270791975104832679704823639796080967349059878616328124678146756226922844542311007385149016898066494790724547396854466816882017979764573127335169222046184872365605429257772468266650612408973326609594407449099151035710575387259247631196235413818846611290997108937764849969087869380015473396318951828601653885770989413335825809271006535309020597686721828148297460153158861060254329509343916287755141918180366962015355736088512363283054678089927448694594233570602783477223709956748078619016884009498616663231765835477580606657665212668356924642774138798678704927429597225733591265717277354803371099277923062844086326898919407131556649908189945618213439705912499762363717291921079180424309814278389292338472058224536420287533718538610076975053819493744999706629419743457129148063642210853664130656011364145518165551716722882207059871440281855830134859496965548390553266523109385935412101291774755818649928572614245991904298250577288309056080354514292933726730235068763156518666596591403936755061617563320776416771649704640576843453309081117805649758187579992987856112550888581393113648133170509337224754190574224672039676119325401226474686218104953153485468312315214708582272839532320448637563668296961457442228291651960361446745161696053397775334725256901112454943173808429511992976910090280414149783537557553925891982317993085128324575173058000729986203975064174362524196816224738075000800048546968528611687780907862303027251855515691580742511627103404661550200542628103725594787525085635649470421564890679795775999195192427991353244492924552289624081169453136449322487833183263839077258459330257

...

4167070829556966024457256348796563937085438482863967599681598819178934806640113432229656275055774868369705804323751365883061420095145753921958961938684190312692477522259173367099399536855417678813262459230306131365135592497743474387273612322761474121581063185918642680415981604709832955402621738726558120178929162445512168161382612719730562661068487185552222078489370748275276167911861888416468628025390242970116218176578196084298501218587904510667919311033926096310213905492281749168742115595222847333705879800359503709952713598520407917517269268830471662305176045890136525819300334140160325163922846526067520058677742987171142135528704544084756971297216597422729228832663150359595590563137820155884793812984900993894679718445670288362450713132837077789783939374742929624156864091711338978702893418701121032429349419310077099688165032806127318106383849792976582737540019073570054164232565736654568457809767602321367500115248265737553523838133007787893801712297396978243385969374927560827830341097672911259839563464021980397080798044370307450345074441255719377918411612476213564875400611618503392303367631781807785158632200404363275095224928236681096428073140855053680154194827099621916496613475806498232263817938405396709689543401875275942098170370861713312711005254690000628644265653420715546680627922718503722654698484490522190747864736785351057259990574803910800941501401892206002004608744921573497284145060505027152701733637306741114116368410995496640029510581430928564803544894473794180151267411874735308591316976973488533752857820053396050993471031732393341911423084984169756000647127127367426721296166313211052066894713643832689538029479590863069594332139589854016348085823309750818072086790183680291530654275646354088080822075607431523700724810623600752099993515706513511518105750435114460757421175757985748377725998620540949072095835424771241093084356124013360522081603894874991246885178403005280125147033474479508042415007986397236954930181243363428887639322337148481378496983899166702008241874474740139892764151701796432364979765195782326782629063024685603292065059157141010399590455450168100523376253158132260084272386698481447970037428165905291587141118504487909059363661154093907135766867819892817051503010516095577673474238592329797916069254255910672693217227888066899226751508001266359615523546860949152342126269729688940332274027254044661888691849702524029398394496647965448528387776859866686000230335036665762560586371278286264476516364242497390208849934808471883418831075492179761500066563483378099950945649146972397379430153759574201403589194568666534488066303393161193104551386736938665118459860250696242803681388466912518986325800010713974530732563658588520973860194630120390966551005053056459270461434658936148850015788565906290413551090738255280021771780433085464680193309508426173360974899269597579634053670548338046168329640430254455273795731636457068590028912689364051307454440822819335538111740435654607229633507855793453530320492497389505292087687784486832143236149228171142867001441656570402586068649440140577203530662365830041418935974612860470369068715689389232718261333023084659106595009666444406860160141882515286470012987319790814585523547538884331861422714881827040353224473504193170642986145898791851537742400309016343569442537006645270983420186934092492895096181182994875931117474251220039814942944434656885356123054216568874237245315858570821980496849875000845507134716477240809005117359365340084447970934842875959705715104194210783572657887399628314443582876407698779389063656172479178695101136990074953209161044229557014282053634888328205814833869714357022898318550505620897525430671377576926089912749909665914177000478394688355248110853884266023055260572991199574341314183124325982868573468055543139067569657375698656253609273854230099265958732464302054658435656578089832323097384740711806993406249827192352331541092424921874031434332653192912262292281703262802624698129902836968802992680224000479507449788880242278931878149318059370790585572383954696444532322591133223811340277990986999971818767293337781172581309439739637557034744858763390302151814761726351177575136713122247918823051699244345517883050385995177909508317804917982802075048348266308903713273678174976956630044169548108098178481220741097480265086495897413631653134990939596221327739225081770352517974019899164020969832899293545044267016845880285689284124862403105220628911410883254250464446826085218764058917538604894273142395031491302959211574975853905488238855315997035579412503526876734636039302727336903512282553862141960479899722973034234296044781477087720946984900200879193641251023862870577461707636219598654087001670797898520376572711841802531052357565015216951533018834754740759174543834687181706809338386158272164519278608374138963684473057619234091183523759251182574104000699329991258502711867767618484350567131085925768390725941035355144532739169109722927530993765071282920063602469185000761641858449065879501041253529678257690428468790670397321180372428655529538498081400396678365027408236325407115633014933334774967031966967057958465931365345971536715500535654925907705528910277528293550741575614956489179495351431814400504485762419420239741923864317173129162901469409082547304575035773000695365299588871739199533973338420719546287655635919579573796066383177216485158272988420789998601078232258916021075707254046939992048250570721766041671500142504059411237989439407810311486820657249364100957540154388451543208437739929077089864343924237917391700328466837937373501653533104820046260973064771711209670185967650062994614060525699236172241956939535845956886244398948378803692634650156572642661023225370521125838287589187739098390468458881409369509926734990995634138603169275980375199380562851559030347980830753266779748140306995817816896935551475247649155101949623891736000828049996050446150567032960254275599952891177844537894084949669399796908407769995320697549038548714686518304751461787691038562129946309858470368307966834720704560806330840987617349128854543567240422471187203817586844851678850288514030408602226847520628546362081236217658967046449190931925065490409596867825383254341801468279082928960477533291676224237048665523936826551226581621155994579322806971798612333971143887412572310303534530814651907128607082912971601241862551618788203286246864030597870351325433372374432162797387685151174205663510362901379680951613651825641882950740690735515907261883585018559457714636600538177868842596827416821102559104698797636549579477569028556327052572014693800965497372645360517060575020771201878909196936848915120267493298963552930876905396050799931845736989007618462705632938564752342709382874306939010146779580056459643919616697205374435526396509652951996232375572406882073995368987377425664028079026301856336483452891027426902635405234203709275093126403401199208274298416553124496965947412154538389688471952504509093395526467592360579548265993569023718264156130110303384753696803017058345804526311692827186955318069179154864227922894618688153650882172839558086430470553401624753489424312525720859098426648367680685285808473287871053212997600165533412618121150371490017610963117554937533634203909576088605963320090974852291148300436391833967941149746436215405144416389330742160100537478705084128218039367406389459869715061537513021004235923530036834374596403067931898579198943930124778201316740372230222918373865261319169333537831349771074841338734158953751754739665154907080497895803476320418858031686682861944592624967667550693638677302976087620018289803940991208595836571986202406012177201999954531098855849477325260568087329546875433669915760025129527991096017999823950099805841633537323813808365119494732204017044393932808925559169040594087127095163256264139031885622034598674658175503405724848196399941249169062842995653350288560486711753812576714095365281585375850141212420258861611311685537304194184181851416527417482833737180516465193541273439369831590252804722750676888093560970030723963616303846417760427953682505814410967312421569293211944722364711361871774233645284988016655497575907900920135249145982672104499274391096075601233518098323727287497978543354584172928195382082144603871217348933227769596851790321922817045023231117775888392883376924959396765962294625124933854008499986971942853145729747098519892300951529981704792003123228905942849770831397355548551037023725528030989826094037315369891840764754031587847194619251520151613467817507006536570101996440499823743334656467758840216344146194278557674505414734483231746042215642083137727703537218994054839602449616303274991890571098639868538703592903718690851280085536173888871765362595893686092220209869268523068544926178228348679129654641264610687721275995743956140536737482923775434284116886071738803873851352060691161981414470620516887926747929215187467774185369448721043987806563096859396873244824347114097105276092597265615901944652916777008800957122534918182915212810445972314679179613251296701764172838535922900734725316026695944907062710599844742679621311388852181151141296265249041244414859592456251077830991598322109964755928058966264695351565168190741448578038346676106533659538203407823523928963945320902409831436894703708250700994652467462765131811824900007772197341524018332665334299141302508789956103740255520046132354653858942532484945217700264367121891215858767153309369747134046023823407124699684479338761040252878884147853226638450074970866243835242715815760327772006306651485871976226737231255985677500804539265323225826741309291718719709699031504792734577500584153050628238089666519509368144726191318740240959686281940295074862825581258619253116727666152464528742052749222456976925161555061603872243043091954422949665317738660036067363322176685095908540266952599183654346428334447280241446009060411045465972660445962922095348709850449416825920485156543835092515017081582857486686869254424444828105292918580260951695678981372026171097013453486302389207388448065889490566323459233030931062060803011159931565459429770836028930518731165752770163968789710289946789875965092649106240294846093630914511308438297429127852593860075420895659532063383573548116876653578854482900727583261554308134753015644208784718240279100403791717058182457157131977413710104669579878326197283789467245604487656899883135182773129722807081867487098559368544584637003388254385358356177975233161253168421850506694581668444607936667524826780222416652711122024724183472268960090825409134780142396102539023540322431271037964817132494805587021077259571018845261974901660993696533525632633470121305436824605775860472213808246720409417683802969039505278561219767687307949218868779116093048760890864434176402969487245147144261867975324660309472813886907194800058028520525253264942063654404514702224837928504011063123204672693584604268016708802662462206316461449892104462408132881930225845203545471216086681803755973406470320420430570357379472942529858976405393375508990852593045202559095830908033121329279749697949611289198809875891099861903251899269339310248932079522555255838696761303891023896328826511081013803531169548516551240528221387658363849483347070682654446066504467919542310931544196193638126791454623678642922525779219556388781821289085367475124290463618761681136999779531021454901885759583452578918141302060010009635675035843325284548430593527144944154303422962571018954035015080569832454163465814760976541923453916975079739735056828215527191478423688842329613837294824087427364368370768220401976220340842805842510193233631814613175188519148118294411149157521976474665359153933628810293319530623279622879691211139344084205871277993630778672840198341991212669306076462211483468232610141599746963674764421477151837636492833589837827707087913124911155765887451609054717720899744208047925820477684738989479772931218997316134448035706702300919337402315389133634565179429733113574960564697592040223172468690434755473518454060280827401950870212231175119772602725455927758721682016005380842329172307137911734725685793646607031834507324271335775802909726730548334696652316991996881300207263540421314435473332615541830239582247601108926159340477743926635360723616529215494123956115448555059977733109031091089201284246029540552305503389937785107260124602237782374833371316914220103235604538730363865904347134609128797097405952234443437849827617967828459176594846493607267132762852232324331197709656329440597366821537207191319144230636424183270754345854102222109096847757650530725501154033176374659740470706991346282804277371801804846809817899693183370612773829427875361239062311893743456079624699801616266688829960113574399007241060678044396194526108049490346791254956443033422013148824969862968961362006055268923832915485567814814818679823621539889958674648513317119810612455487314693650714698970060200004576181846102172579577583100709114620919882001123380415620965235710048325612569398219523144320338379465996852643345900689003531922547563704849818355749934328006166733654582114594680090186147350022080584355467784826541053852778210365846555408983380962162836488550577541407700088167275205632315581078285436504438577714343845180460868734072168231771105328113397406268730844319582806589447938165009787473122522804056080719464867581838471875179422056158377818845922874791928776077825400255106792949772130593832921493019786008654362421350592480535800537138273218845144586243659017938809673212151103553862708082693650408428582452966961061193863501316649861898959894603671599245675890636278484770584215373149005401270370369593708665243019250957194820568303464376359954620656938750531197440823913776315563718460541956568783366438594977747814031704947112719390729912025256893111100963845951563422998675761306051070714777580592869403331074192628425358813868202556234298176660439096636746573009170719961544706567635645980060540496596707590857008641926949098717613416259674002320184085774295964416500328770253760336966326008469492398338206740581663775159066894671800429423460520694125053185624604332748196756183125993301264848277468330472658076595146442299918782515295041469385266660121510912910746706111161174255972930086302206738563209108979724291425006240875367659843243181021811633948247650305238442945401806669219056292690139449541478415705054638820723402895976342128871306815192475493868633832888142584699307868708594468709221366968481048331644505798293244420658971304805455231183824052138384780243205246293106589768943281628714580921284214070545349228123523673928632135431084856462223763727069717794016355210001618848670939515318790501410445567255736203953629184091811798577594700445736317242285230748466522631417928646270765226749859630052493659379994397915236855824733112291935714753125300087354336278550229533314987457547870506914427720680472277584865809374210063614811968514272281158542292845538066888541575560912780964865531883555810990497834567168919642908621578459648728704173975927338497907715145713676467633717280068181605402083799920749664091624311367193080929132045489364436460054690562989548046919510664651783586692039116471413454851284291672834509769861530857685030046513725597127615265593090400997892002733755592254179704133152812331117646979969584970906581297279528638003118991115856145470094060407817488433482638584675451415957888943241399898465978748511197738543367949556743657361512913944514023475856446978995118053975513664358324777756735245913854374779720713069653864532818174658791773616197898331238322551062423973318089880597860763252042721520175391807221599055022612548087446478064964552982857294113792315575194678284000025614128299938866189950736714007949241794377363309875675242666419904179256881352481758793244741012653920905054480906644138973411915493978336191979296652477359950937955349621984076841727295980773437182023623379431079212532350485831321578613477427131923964803345162722838156832422504703656229710149181983496999875238008634799033820537254543034558427976692520655105654801186763201896361657360999827531365856227438830351783739419089421704304360663830939653656513289641367770357389518102720883293524780784424718343674249339253646877940166988369654383481962452213484429642857142