# How to calculate the digits of the MKB constant

Posted 3 years ago
104992 Views
|
30 Replies
|
19 Total Likes
|
 Attachments:
30 Replies
Sort By:
Posted 3 years ago
 I got substantial improvement in calculating the digits of MKB by using V11.3 in May 2018, my new computer (processor Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz, 3601 MHz, 4 Core(s), 8 Logical Processor(s) with 16 GB 2400 MH DDR4 RAM): Digits Seconds 2000 67.5503022 3000 217.096312 4000 514.48334 5000 1005.936397 10000 8327.18526 20000 2*35630.379241 ~71000 They are found in the attached 2018 quad MKB.nb.They are twice as fast,(or more) as my old records with the same program using Mathematica 10.2 in July 2015 on my old big computer (a six core Intel(R) Core(TM) i7-3930K CPU @ 3.20 GHz 3.20 GHz with 64 GB of 1066 MHz DDR3 RAM): digits seconds 2000 256.3853590 3000 794.4361122 4000 1633.5822870 5000 2858.9390025 10000 17678.7446323 20000 121431.1895170 40000 I got error msg  Attachments:
Posted 3 years ago
 You might get tired of hearing this, but I made another improvement to my MKB computation formula and am trying to get 40,000 digits from it.Code  MaxMemoryUsed[(*Other program:For large calculations.Tested for \ 1000-35000 digits-- see post at \ http://community.wolfram.com/groups/-/m/t/366628?p_p_auth=KA7y1gD4 \ and search for "analog" to find pertinent replies.Designed to include \ 40000 digits.A157852 is saved as c,the real part as a and the \ imaginary part as b.*) Block[{$MaxExtraPrecision = 200}, prec = 40000(*Replace 40000 with number of desired digits.40000 \ digits should take two weeks on a 3.5 GH Pentium processor.*); f[x_] = x^(1/x); ClearAll[a, b, h]; Print[DateString[]]; Print[T0 = SessionTime[]]; If[prec > 35000, d = Ceiling[0.264086 + 0.0019 prec], d = Ceiling[0.264086 + 0.00143657 prec]]; h[n_] := Sum[StirlingS1[n, k]* Sum[(-j)^(k - j)*Binomial[k, j], {j, 0, k}], {k, 1, n}]; h[0] = 1; g = 2 I/Pi - Sum[-I^(n + 1) h[n]/Pi^(n + 1), {n, 1, d}]; sinplus1 := NIntegrate[ Simplify[Sin[Pi*x]*Simplify[D[f[x], {x, d + 1}]]], {x, 1, Infinity}, WorkingPrecision -> prec*(105/100), PrecisionGoal -> prec*(105/100)]; cosplus1 := NIntegrate[ Simplify[Cos[Pi*x]*Simplify[D[f[x], {x, d + 1}]]], {x, 1, Infinity}, WorkingPrecision -> prec*(105/100), PrecisionGoal -> prec*(105/100)]; middle := Print[SessionTime[] - T0, " seconds"]; end := Module[{}, Print[SessionTime[] - T0, " seconds"]; Print[c = Abs[a + b]]; Print[DateString[]]]; If[Mod[d, 4] == 0, Print[N[a = -Re[g] - (1/Pi)^(d + 1)*sinplus1, prec]]; middle; Print[N[b = -I (Im[g] - (1/Pi)^(d + 1)*cosplus1), prec]]; end]; If[Mod[d, 4] == 1, Print[N[a = -Re[g] - (1/Pi)^(d + 1)*cosplus1, prec]]; middle; Print[N[b = -I (Im[g] + (1/Pi)^(d + 1)*sinplus1), prec]]; end]; If[Mod[d, 4] == 2, Print[N[a = -Re[g] + (1/Pi)^(d + 1)*sinplus1, prec]]; middle; Print[N[b = -I (Im[g] + (1/Pi)^(d + 1)*cosplus1), prec]]; end]; If[Mod[d, 4] == 3, Print[N[a = -Re[g] + (1/Pi)^(d + 1)*cosplus1, prec]]; middle; Print[N[b = -I (Im[g] - (1/Pi)^(d + 1)*sinplus1), prec]]; end];] (*Marvin Ray Burns,Aug 06 2015*)] Output so far: Fri 18 May 2018 08:03:3565.6633081 Here are the results from the task manager: Answer Posted 3 years ago  My computer is getting so sluggish that it has become nearly impossible to get snippets of RAM use! I was able to determine that it is, however, still working on the 40,000 digits. I'll let it do its job! Answer Posted 3 years ago ## June 5, 2018 Mathematica got hung up on the 40k run again! this time it complained about the dynamics stopping working and wouldn't quit complaining. I think it needs a smarter program! Anyone else want to try to beat this world record?? Answer Posted 1 year ago  Shutterstock has found the MKB constant, I(2N), at least 2 times! Answer Posted 1 year ago  Here is a comparison between some of the last few versions of Mathematica computing the MKB constant on similar computers. digits seconds V10.3 v11.3 V12.0 2000 256 67 67 3000 794 217 211 4000 1633 514 492 5000 2858 1005 925 10000 17678 8327 7748 20000 121431 71000 66177 30000 411848 ? 229560 For documentation of the 229560 seconds 30000 digit computation see "mkb 30k v12p0 2020.nb."For documentation of the 411848 seconds 30000 digit computation see "MKB30K2 (1).nb." Attachments: Answer Posted 1 year ago  I made a quicker program for calculating the digits of the MKB constant in V12.1.0 Module[{$MaxExtraPrecision = 200, sinplus1, cosplus1, middle, end, a, b, c, d, g, h}, prec = 5000; f[x_] = x^(1/x); Print[DateString[]]; Print[T0 = SessionTime[]]; d = Ceiling[0.264086 + 0.00143657 prec]; h[n_] := Sum[StirlingS1[n, k]* Sum[(-j)^(k - j)*Binomial[k, j], {j, 0, k}], {k, 1, n}]; h[0] = 1; g = 2 I/Pi - Sum[-I^(n + 1) h[n]/Pi^(n + 1), {n, 1, d}]; sinplus1 := Module[{}, NIntegrate[ Simplify[Sin[Pi*x]*D[f[x], {x, d + 1}]], {x, 1, Infinity}, WorkingPrecision -> prec*(105/100), PrecisionGoal -> prec*(105/100)]]; cosplus1 := Module[{}, NIntegrate[ Simplify[Cos[Pi*x]*D[f[x], {x, d + 1}]], {x, 1, Infinity}, WorkingPrecision -> prec*(105/100), PrecisionGoal -> prec*(105/100)]]; middle := Module[{}, Print[SessionTime[] - T0, " seconds"]]; end := Module[{}, Print[SessionTime[] - T0, " seconds"]; Print[N[Sqrt[a^2 - b^2], prec]]; Print[DateString[]]]; If[Mod[d, 4] == 0, Print[N[a = -Re[g] - (1/Pi)^(d + 1)*sinplus1, prec]]; middle; Print[N[b = -I (Im[g] - (1/Pi)^(d + 1)*cosplus1), prec]]; end]; If[Mod[d, 4] == 1, Print[N[a = -Re[g] - (1/Pi)^(d + 1)*cosplus1, prec]]; middle; Print[N[b = -I (Im[g] + (1/Pi)^(d + 1)*sinplus1), prec]]; end]; If[Mod[d, 4] == 2, Print[N[a = -Re[g] + (1/Pi)^(d + 1)*sinplus1, prec]]; middle; Print[N[b = -I (Im[g] + (1/Pi)^(d + 1)*cosplus1), prec]]; end]; If[Mod[d, 4] == 3, Print[N[a = -Re[g] + (1/Pi)^(d + 1)*cosplus1, prec]]; middle; Print[N[b = -I (Im[g] - (1/Pi)^(d + 1)*sinplus1), prec]]; end];] Whether it will allow me to calculate more digits is a question that will be answered in a week or two.Here is a comparison of timings on similar computers.  digits seconds (Impoved code) V10.3 v11.3 V12.0 V12.1 2000 256 67 67 58 3000 794 217 211 186 4000 1633 514 492 447 5000 2858 1005 925 854 10000 17678 8327 7748 7470 20000 121431 71000 66177 30000 411848 ? 229560 Seethe following cloud notebook for the results from my improved code. https://www.wolframcloud.com/obj/bmmmburns/Published/2nd%2040k%20mkb%20prep.nb
Posted 6 months ago

# March 30, 2021

## I finally computed 40,000 digits of the MKB constant!!!!!

(March 30, 2021, approximately 8:00 am) The new 40,000 digit record took 362945 seconds, while the 35,000 digits old record took 727,844 seconds. That's more 2.29 times as fast: (40000/362945)/(35000/727844.) = 2.291867126660277. See attached first 40 K MKB.nb and 35KMKB (1).nb

Here is the short, very fast code.

g[x_] = x^(1/x); t = (Timing[
test = -(I NIntegrate[(g[(1 + t I)])/(Exp[Pi t]), {t, 0,
Infinity}, WorkingPrecision -> 40000,
Method -> "Trapezoidal", MaxRecursion -> 18] + I/Pi)])[[1]];
t


The recommended setting for MaxRecursion (M.R.) is found in the following table.

digits     M.R.
2048      10
3000      11
4096      12

10000     13
40000     18


40000/2048+9 Here are the new speed records

digits       seconds
2000        23
3000        96
4000       165
5000        442
6000        623
10000      3250
40000      362945=101 hours


Documentation is available from the Wolfram Cloud here. (40,000 digits are saved at the bottom by the name of "test.") Here is a redo of the 10K run, where "test" is 40,000 digits of which 35,000 have been computed by very different methods.

 g[x_] =  x^(1/x); t = (Timing[ t10k = -(I NIntegrate[(g[(1 + t I)])/(Exp[Pi t]), {t, 0,  Infinity}, WorkingPrecision -> 10000,  Method -> "Trapezoidal", MaxRecursion -> 13] + I/Pi)])[[1]];t

(*3250.55*)

N[test - t10k, 10000]

(* 0.*10^-10001 + 0.*10^-10001 I*)


"Thu 1 Apr 2021 11:42:14" I computed a much faster 40,000 digits of the MKB constant.

g[x_] = x^(1/x); t = (Timing[
test3 = -(I NIntegrate[(g[(1 + t I)])/(Exp[Pi t]), {t, 0,
Infinity}, WorkingPrecision -> 40000,
Method -> "Trapezoidal", MaxRecursion -> 15] + I/Pi)])[[1]];


175,551seconds That's more 473% as fast as the old 35,000 digit record!!!: (40000/175551)/(35000/727844.)=4.738347911921403

Here are the new speed records

digits       seconds
2000        23
3000        96
4000       165
5000        442
6000        623
10000      3250
40000      175551=49  hours

Attachments:
Posted 6 months ago
 On Tue 6 Apr 2021 04:13:58, I computed 64,000 digits of the MKB constant using the following code. g[x_] = x^(1/x); t = Timing[t64k = -(I NIntegrate[(g[(1 + t I)])/(Exp[Pi t]), {t, 0, Infinity}, WorkingPrecision -> 64000, Method -> "Trapezoidal", MaxRecursion -> 15] + I/Pi)][[1]]; t (*393847*) I verified it to 40,000 digits, See attached 64KMKB.nb.Later I found it was accurate only to 54,390 decimal places. Attachments:
Posted 6 months ago
 Here is proof of the faster integral I'm using is indeed exactly equal to the MKB constant integral. In the following hypothesis, the MKB constant integral=LHS and the faster integral I'm using=RHS.g(x)=x^(1/x), M1= Which is the same as because Changing the upper limit to 2N + 1 increases MI by 2i/π.by Ariel Gershon.Plugging in equations [5] and [6] into equation [2] gives us:Now take the limit as N→∞ and apply equations [3] and [4] : He went on to note that
Posted 6 months ago
 I found the 64,000 digit computation was accurate only to 54,390 decimal places; see attached 54390 confirmed MKB digits.nb. The new recommended setting for MaxRecursion (M.R.), as hypothesized, is found in the following table. It starts out at digits around 2^(M.R.+1).  digits M.R. 1309 default 2410 10 4453 11 8182 12 19734 13 31286 14 54390 15  Attachments:
Posted 5 months ago
 Today I followed a lots of links about your work on internet. And this is the first time I post in Mathematica community! Since I very interested in your efforts, I wish to become a successful man like you in mathematics so that my name remains eternal ... My dear friend Marvin Ray Burns. Your sincerely, Fereydoon Shekofte
Posted 5 months ago
 @Fereydoon Shekofte: All it takes to leave a legacy is to keep planting seeds! A million baby steps >a mile.
Posted 5 months ago
 I found out how to verify my MKB constant calculations beyond any shadow of a doubt. Use one iteration of partial integration, because for g(x)=x^(1/x),.The following computation will show that the calculation was right by leaving a small error. g[x_] = x^(1/x); t = (Timing[ test = -(I NIntegrate[(g[(1 + t I)]) ( Exp[-Pi t]), {t, 0, Infinity}, WorkingPrecision -> 2410, Method -> "Trapezoidal", MaxRecursion -> 10] + I/Pi)])[[ 1]]; Print["Timing for calculation=", t]; t = (Timing[ test2 = (1/Pi NIntegrate[ g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 2410, Method -> "Trapezoidal", MaxRecursion -> 10] - 2 I/Pi)])[[ 1]]; Print["Timing for verification=", t]; err = test - test2; Print["Error=", N[err, 20]] (*Timing for calculation=48.0927 Timing for verification=69.4713 Error=-1.*10^-2410-1.03*10^-2408 I*) The following will show that the calculation was wrong by leaving a large error. g[x_] = x^(1/x); t = (Timing[ test = -(I NIntegrate[(g[(1 + t I)]) ( Exp[-Pi t]), {t, 0, Infinity}, WorkingPrecision -> 2410, Method -> "Trapezoidal", MaxRecursion -> 9] + I/Pi)])[[ 1]]; Print["Timing for calculation=", t]; t = (Timing[ test2 = (1/Pi NIntegrate[ g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 2410, Method -> "Trapezoidal", MaxRecursion -> 9] - 2 I/Pi)])[[ 1]]; Print["Timing for verification=", t]; err = test - test2; Print["Error=", N[err, 20]] (* Timing for calculation=14.375 Timing for verification=18.7344 Error=-1.21910183828457949*10^-1311-1.6392815749781077289*10^-1309 I*) The following proves that MaxRecursion -> 12 is good for calculating and verifying at least 8192 digits.Compute 8192 with MaxRecursion -> 12 g[x_] = x^(1/x); t = (Timing[ test = -(I NIntegrate[(g[(1 + t I)]) ( Exp[-Pi t]), {t, 0, Infinity}, WorkingPrecision -> 8192, Method -> "Trapezoidal", MaxRecursion -> 12] + I/Pi)])[[ 1]]; Print["Timing for calculation=", t] (*Timing for calculation=1111.69*) Verify 8192 with MaxRecursion -> 12 g[x_] = x^(1/x); t = (Timing[ test2 = (1/Pi NIntegrate[g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 8192, Method -> "Trapezoidal", MaxRecursion -> 12] - 2 I/Pi)])[[ 1]]; Print["Timing for verification=", t]; err = test - test2; Print["Error=", N[err, 20]] (*Timing for verification=1419.66 Error=0.*10^-8193+0.*10^-8193 I*) As time allows, I will post what all this parity-check has to say to confirm or unconfirm my latest table of recommended MaxRecursions (M.R.).  digits M.R. 1309 default 2410 10 4453 11 8182 12 19734 13 31286 14 54390 15 65942 16 77494 17 89046 18 We see that 4453 11 is confirmed, although the real part converges to a slightly higher magnitude: g[x_] = x^(1/x); t = (Timing[ test = -(I NIntegrate[(g[(1 + t I)]) (Exp[-Pi t]), {t, 0, Infinity}, WorkingPrecision -> 5000, Method -> "Trapezoidal", MaxRecursion -> 11] + I/Pi)])[[1]]; Print["Timing for calculation=", t]; t = \ (Timing[test2 = (1/Pi NIntegrate[ g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 5000, Method -> "Trapezoidal", MaxRecursion -> 11] - 2 I/Pi)])[[1]]; Print["Timing for verification=", t]; err = test - test2; Print["Error=", N[err, 20]] Timing for calculation=230.391 Timing for verification=299.469 Error=2.8146045128793867*10^-4456+1.6474663184374133246*10^-4453 I As for MaxRecursion -> 12 where the R.M. table shows up to 8182 digits, r.e.  8182 12. Actual inspection from this method shows it is possible to get all the way up to 8278 accurate digits of the real part and 8275 of the imaginary. That is the same difference that exists from it and 35,000 digits computed by a totally different method.So  8182 12. should say  8275 12. Here is the work for the verification: g[x_] = x^(1/x); t = (Timing[ test = -(I NIntegrate[(g[(1 + t I)]) (Exp[-Pi t]), {t, 0, Infinity}, WorkingPrecision -> 10000, Method -> "Trapezoidal", MaxRecursion -> 12] + I/Pi)])[[1]]; Print["Timing for calculation=", t]; t = \ (Timing[test2 = (1/Pi NIntegrate[ g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 10000, Method -> "Trapezoidal", MaxRecursion -> 12] - 2 I/Pi)])[[1]]; Print["Timing for verification=", t]; err = test - test2; Print["Error=", N[err, 20]] Timing for calculation=1764.03 Timing for verification=2247.2 Error=-7.2028204961753149*10^-8278-8.0907462882284574618*10^-8275 I As for MaxRecursion -> 13 where the R.M. table shows up to 8182 digits, r.e.  19734 12. Actual inspection from this method shows it is possible to get all the way up to 15444 accurate digits of the real part and 15442 of the imaginary. That is the same difference that exists from it and 35,000 digits computed by a totally different method.So  19734 13 should say  15442 13. Here is the work for the verification: g[x_] = x^(1/x); t = (Timing[ test = -(I NIntegrate[(g[(1 + t I)]) (Exp[-Pi t]), {t, 0, Infinity}, WorkingPrecision -> 20000, Method -> "Trapezoidal", MaxRecursion -> 13] + I/Pi)])[[1]]; Print["Timing for calculation=", t]; t = \ (Timing[test2 = (1/Pi NIntegrate[ g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 20000, Method -> "Trapezoidal", MaxRecursion -> 13] - 2 I/Pi)])[[1]]; Print["Timing for verification=", t]; err = test - test2; Print["Error=", N[err, 20]] Timing for calculation=11440.4 Timing for verification=14435.1 Error=1.269166151550935283*10^-15444-1.34038091454473637998*10^-15442 I Through actual inspection the next row is  28932 14. More to come. But so far through actual inspection, we have the following.  digits M.R. 1309 default 2410 10 4453 11 8275 12 15442 13 28932 14 So far, the table gives a clear-cut pattern:  digits M.R. 1309*1.84 ~=2410 10 2410*1.85~=4453 11 4453*1.86~=8275 12 8275*1.87~=15442 13 15442*1.875~= 28932 14 Following the growth with an eye on our experience were we proved the next row is  54286 15 we get  digits M.R. 28932*1.88~=54286 15 54286*1.89~=102600 16 
Posted 5 months ago
Posted 5 months ago
 =Using this new, fast method, I computed and proved to be correct 64,000 digits of the MKB constant!The computation time for the original calculation was 784,937 seconds, 9.08492 days. The computation time for the check was 900,860 seconds,10.42662 days. See attached "64k MKB proven.nb" for the work and digits.The code for the calculation: g[x_] = x^(1/x); t = Timing[MKB64k = -(I NIntegrate[(g[(1 + t I)])/(Exp[Pi t]), {t, 0, Infinity}, WorkingPrecision -> 64000, Method -> "Trapezoidal", MaxRecursion -> 16] + I/Pi)][[1]]; t DateString[] The formula for the check: The code for the check: g[x_] = x^(1/x); t = (Timing[ test2 = (1/Pi NIntegrate[ g'[1 + I t] Exp[-Pi t], {t, 0, Infinity}, WorkingPrecision -> 64000, Method -> "Trapezoidal", MaxRecursion -> 16] - 2 I/Pi)])[[ 1]]; Print["Timing for verification=", t]; The code for the comparison:  MKB64k - test2 (* 0.*10^-64000 + 0.*10^-64000 I *) Here are the new speed records digits seconds 2000 23 3000 96 4000 165 5000 442 6000 623 10000 3250 40000 175,551=49 hours 64000 784,937=218 hours, half a day longer than the 35,000 using the long code. The 35,000 digit computation finished on Sun 14 Jun 2015 06:52:29, taking 727,844 seconds, 8.42412 days. Attachments:
Posted 4 months ago
 Attachments:
Posted 4 months ago
 ...Print[Abs[test2]] 0.68765236892769436980931240936544016493963738490362254179507101010743366253478493706862729824049846818873192933433546612328628766540945756595772115802556504162846251439250971205896979865009525901957068131704725387265069668971286335322245474865156721299946377659227025219748069576089599393209602752002764192048986309527950738579344982825034173229565338091811015320879481813358258054988127280975209369016770287413569232922644964771090329726483682930417491673753430878118054062296678424687465624513174204900483221642766554290055935028993611478222342426128582832646718603650018931537414763848967936556912271439870651953065133056888465504885799873853516260611678863354038966005282223744908289479862039722833171519816024367657656383305723596359151086525460036387486837632622334298725709552463768300591035314935398573611886888420174824190626083498173034223703984133264282699210740455065589666674834536567489060715777444147548424388220133662816274116986724576330176058912438027319979840883059505891309117191987761469414772648989343657425085034050732738529903546587114217499635584514475429656959327732862489935076490012861232249244670423220090484477969004477448946670434279197103332581857937517719898657425832767700119265854957115794801143278185461993723493131802360791389248808154759564302727311223193005229640892474022665093207969297797972308795483218256171403916521459251943207234100609086755844459050004667079633465456383179509789357941736916352744611848521664077918386624294040883487647062354653558109265769644276994369741555722263494599492834558291937955573706480722982389806312472239746286527176248883116124285469947303667188075506826507811479428582807366599407544908560990699866167233307144245764835741501174979679166078765231145175411199825822532170091858833628202128777966026600647843068442894310401343003939117236867245656732686719139206716028255819141802331701942027248337771633882445225049334329008827371320849006472846226868011129149192754883153995560921671208059671732704499253517327447529208297180672654123457301218758892278525894167935930983363218877512533994251978272092700003994136520699813263053327399132641690231179063314931546906927612775633995348209911166678724589467821767106592498663827057034363632241807121831546175498178011687284590439293322231263406301066863589072717290630291441982684113819198880100231182613587798104863611185433976009254862585527222843445901958943153561148829083242874018226480554274231391324767376148485531787767908124831873688579979114662856184612164534836370699371440464263768724668291617743681719766849740663590277737977490693183461320266666793472116774276618408124767965369796362732668987556797338128876129264558867657737417548617146808592137056879602982206609613881069490166381528825180204703315896719667069923077454352649723496033985893188309150391579573916059639453655188856334980355047281560296288150836680499821806918067869468571687709518088408966653716009356556714281694904914038988996962213833530636987279769672200413448893419914190954063100962251649102614676944333201213024711868954772741991675045198246947499574872027800654821823797116399297131866662866832215332914761325880983081211272181775518951539503852063119472301382766303820851467743266039356123495461914463960644386394228342211998370152351720235034997434035743513051754761571835043769475528640144621307760159481496713401409374957729200400650100318226988524015127382509490642900236553851499823658269458873976032051355393161653806016080446394196719312454167915154602448638624354575153334932298393406734174580316934939632892851077461038399470015366439910136971186909599331204517462262508377673477745789645309425145559198802530351403897927622891172233239135167420567162398873965477371498335087310395422796362380227536212159184529243644094285328763286873653399867593200891823468738537356817916009007206857590792983184556882143118383332812491747733056313117179696094921120670802012310012864110800437831852620698327457619035904268498030693438632685623213366864129523404256345542376567721287706234359125016588483777876970236084456277023948551334490591022594253744077631232660869593809453087749830900393202787736482133628148979992109544954840067942735030391105496026321872468122542495017023785810605820545392820104069279893067324597299043883381251767370331206913429284614563732308018369972360638019778425246546329838131639355043236388708044857300408692365733932897876809202025693305332974091411983635619038514442263783801745983300121464879550146672827072002317686396598587702487509572349422593441184802476344187280014450860069307120621758277552124841158659386176036703247124389223327008210072318671884895179305778728051888524412158486781863155034447221379906386062559915129172725833420555901857729690605950941678587057025641848365090809750870051863842805803189784976076099574956436664131457150096711473033060684065060747340764998195621425524824611657787212347497307297184843276100338110267863618974154272345482369968216663233417338501929114697679974461999040589290327155974468089706302454776026817180862666499129628174265577539296103535807674203952782073115928317544891317654708215972145012823941980744128048658597163977280396427316169647475303595080927471754288841833046841458422387717974567843044763850418125206354901611986735632986299742416514404459056979593895488162233943652678347265596022282622385942587919265881732538688040421277515535793758126602211811071215627680419344432516747402019492482943196302886074832961592788991057409669743325758307333163136246632364563780912463029611662201334616642363164539543840181301469207548893290144196646698764959753342322814145996984815900737499281211342548428906112295670587794396336773199294694685408180899135324672973165645117794165164625772251499013197507709128473895643620535221191614787415169032580462466771890125789345521268697933221974072228257137688062748923747463128426891753656977603806187577539562171586625808503292996097826167833312793361094258099626951418568585518961687635101836804717331526833821482927759113475972330852882944833032257951185249657808449783975928144212629465555401121770667943354738182016599177879322535318669382299981500007793969274837166785629080488761222197549875004161208801954470862728371878889690961127008128988556968897951226589322413393621290922169712215501662328885746858351091854067612190960814788538340562578207940194447820374758964049453475279596594755697761023231503354696608266140588427725279132408041823760459504872832001577406637490493472266614047453860870065686792877317240215300245115939170990462859843807650049824300175195709172965197327078675562310841032518575712484118847367779336861724033437212821275432183094312917793867315784551027523227005327157648039488363953701623965995604711695004856773762203158723953554272766853309916267341275797701903330320042991780321928042752204238907746197436551707656232310297198950878091594928897182512416873896222378187499552752921976712473276842502760152461333888138362604443683396629339896297650204980597418549284339871113824834286671299816817387582638999915913286638728595546135935343327723455065683745940557931894237331753292045470410939999575537512585307075567794220591384663498770172627012864400543194750780056992232117453578320389209867758387153664474345216548748209284915679039103002974533659770931659846870364413634670648588160193106843188106278338484810906518566594643137582510141675299253740013452703717539783595916347808069303890053016731820356545553334308669988238215584797234857833240715337734964890963336352895209158472114451967789258561642243848301230761365174350759810624743918027836785194432612734564175386521406785552306982060855661420857844642892457821845981654717418043312915755155342902248185663052387501034934749414043850316243443995738735101173469076174529743228171316148424511561503236188112034773319311513132912842798170621472827047672512662660852021680873128806212250221980163516049343951492036827192365458624007962426554417906076621642340008264494604009400963618761963743233336699723230804728616304144337784023198465901333727384408963746178911895846410600416997576086543137329171944692055426801269582117623218593830183301386966850121271664831399119275066306084081037583165170944565900194591454705621425288086806504167157399213665956221987887850729795078428235191733444077623156066353441806301809447237558386800763779726469019801516781767029953454355486904086668961133817439450715151128685255321775726892870440473744648135498995935054160338685663523581037884369223344060532035244549530978707961982715975634739572087881230153460402610891533080110973700091540678696985479648877093538694703949814678318178906344131546480237420675784498137760336800205498122230353675368010587675313178007613310409033915829070038954051402592682464313456575568059220870617974413434576207889586620127970628216302933626256098521411354887792001292183442992713495148114132503886863918215495594135709356606956839123128764710024555788150700996403565715489148120536193763080771965908774932176687575396177970047279872390682064853333317876735441961126812962435306711447931900024658102394948060723874376192992074534577072409014967177579881003203603844597465838672089245254647844940297347907582162840968570311034735702558885041591735458587806321821681468362558269818765491115492370357335209916816201371799888087838643560301629784058060474468807601318274763626318805269627924736976096596143438889750807217089885706589537704845033995010990501704030485978413906693471823056058978361765766540875857780152353408191351286387079162446133333449551836073470193445248355929280369763149422632438606998644721208347829355596847775887472079459339376004377441766456024133954622699343314552862743421422371195589467507811224974076666505100447335985294698743481536277956472985989379142059927665547319180436047661445150971635633321070664576769828503372420176381854082122911693446785358685649432354200798985200344829230769191651462987929262619681734042999411805817382627750320836574960607564939935193713317938773219968529378875643297709581094705710775087337340048430356133329809307844513305130536419451502785240472800606103546718110003429303529906499494710047912237804449249468874525861083507010580349374701040030853685622848919878449929399851433751531600860218882532874416607559293184652366518405285172427184628927098560354782726363212597594770953634441623223718002326825766680241421852081609630303146486257064001699198422370576720335824455462285774244510694123015266718544479682986587917276656888581776216242287865231580329129808038591901952458108582886799850458913868870897316226399785695207697594428075479862155444063290069933763160519758353807284083073393027087794549513007736792112216429208439255374096196594904127869096362714022294184973891594248800061126654310668508809992868539099319923967900644358223292981012168404390789699692226974532812736740726705001655775124973620097345182072524359145885905902176218784092650852667171197480014612236259464872765843116006356086890067690233029982695875207293003626204223274745661069509440757588454169313726480937365021254534348209980346959715427124799927823882402396681319310222085719304648072632850848476903201378748718641877578017549246728454975911731380323992109244157781903593878554206064360914649409887207646362198718570717717828555745157055499606109945049294448554426277452184000492947923939681133667684299336442600353596074034145457666334331793961275462039007627213995452036177297272181745363958253145746378713674914362798861912370616204547295605099498268925270142468175541885936455230391996304914004337777568355347422130367905347350273778348426228428661469096462827715531661223661982922965385873663654906808552645899234048209365933126670575275802344829577289518161114817548328708323260137171887381537431438495763162872013412530729081800855631613767906611199235441691313536959306225969842073218977525206805089010503086744773911802531262458736383818632981454415888931500276959485335571617401643867802454518073083747981689243228707691363505519248801525470729484403981839727724581325054279894580924153424034980721591117713459481711920188146374609735437708789726381086002375802532851460036051245029267075777395041069203162249819292562906665858423018853205286078794806182035956253492598017769414680713839600943488472976928157795083131569856681065970354607231916440790023121971921063643253016992146934353541385065323232732416348528363830204550297901450028349760279586033397868154314810686464782535307316558683744949764451407817579353350266047245126257588496377047460395161491865670240157744681698896845740056269336891214367946547516678622720499862708909236488801029242763320063716880338723047179151798172058591124245575791489778944441792552360399198799743162085797046492087284331547315234891707663583637345058339250844352208626075065211002042402852548997696224231894476584104305252983051191993222219055741828524094252377925581703037152893534072425401720375934887581730991828290325117506555789230837583134473210547294260194982981519860912595954338191835720992308863630223835283759255205519300777881534867285454592827828524635031096077880648051886971133695126113929662229558732819097600207625824039727287689715234382974010185765739372284191513142959236853288627452308543337638644049025803544103510682270633218110911954688572494588187241971009790086275999731836282822129696754560584484503250841012506831605558863012659137903462449958732525188618380900088050894054336066355791119374965827906274864842151882268850621297248101428312054900533583216944631861626122510082082948769552584815342128083661652190772424146024625009231163820015068672195579312189548651487591345437813757441652233825016579370483546749025026486091835624885580729107206394743120989443742596397946986532657361050227492526944826103918996197813637871176060238382090946566765838399045073749749808967900477565685204163145349767202254049653445701731797224580931130144436315966907705090169035658090259875036956158416441744243312411242984767762396522602585962208859553456575846443674057782808449981261908954983951241759741750720901581884722817504304011957451395096673818414859842065409004696774034910989296144854435347841078251745452006945321505252144488702316190501513830181678900460652350667910123747817179595199448298133111092763397754128341727910605738631687254741174818938185397265747241023428269259507279848899947471545624758647042443827788368058218482353059553351031334052948678233923611265188514815847760674821423091793105863195928814686758055252218891239899987291845992009434816751078729384625585946379213282556349209111784765585513963392672067482816675816148726191451616109993128144202270947196734756325239342116398042218762971400666788022254343916772222497456368099921005746495321202188903803577906352435030955031135860519210000096429393851172745952195233923392705678930770254703614031284247755908869936042351444220330809526622875759687333022773524409808010139864309440742959573871139136757554471953331334210601691836581561512232181968283688303595304806580127957658352776138794312115393827933609169842487504264473663281726407649263108598740651157004974028306421874750795807471186826306536812676670443101928784277023495868312680188902657537598464346340680898309628212690416877722215220998384103431558545741696921375810425244068049779635269388838985483810164644660154215985355314002191072183826834150364933111897635872101794281442659843078223862815197818268234905934105962017289199664484509856851152571711407743981226634242648977077907262917821596746791845983552190964269137238998329643786140886276001669253224411999982885770258107926328516172422268014598700031525640631831572340465999499823727743735860504191303731231297014779022116064905047114454872899622206489234599826586396527361043001377631008159467400941115054484174699217894418780239782235806818592944425795290352264590391125194923239175238385530548831490448132830741094726510683902362032845415826839418541349555518567786339717924798835135652664955428874746390983648718792515819928101128208157392563232262477302633131761516279395410942166073603426625646415499325446544446176961777704332594383390271844444789452394799668165431710838354330928146992254682365088452351788869385112287843823181456202881903316831712389212335081399759274071661663025057239285027272228070621787850885932813064277648455682848679143821101541212039914926883137872136310878896636524959199119199008454870119285251327665130651804384549890620784844376185359563017846179599858006374105565180381545899481534624317844751723985534330767110164897570419074886204283713397206165732444080994456501139532278429062360406066245098853647796890817370541942635476410064790358844410286416698030928433393443054580812155686712547630165646471983057545681310486007294356970946010339692962083822345529536929479845583110101772761044789272882353702282977767784472475628083637285522211238302142258716171304832579616714576380730275750067721360930755024802985873288300996710306520012511247802663572953971030972621318440452569211754191449481858237939682684775978773612872283397528785556552026763179520536873281806921512691801956916739368499585097787793159558139907584066804051267302837205345820515916808381901347404194035790805655469266915458717746760246854670953322534003601061798894466292078923638808668463036694428322306765668083083183463695527905277826971584195281646637970491206359844892839142719319905449908779532420976275606600086965953228027943911904574111556710003207866128541537659526534433644720693557924372174524949026681621804666748959849631509316177047697834230436553358221794117442883065683550707156175675900958216772854792043327249515884176885910684201895992959230102954603905617347080536152768741025234628356955007416935687697499284404674269273900903450394251007734020198396200321509486969046661167494719187483594388945660901502702635458854894487631762494507095783419963951421682396784816261669772185782256527319198823861631271305557334629034454498661142677846406912692925774443168093589891040662164382633796893056880442621829353879631634578976963235921629360829143359689543537972247913740705649199129434512215215740679036987749974182571013658531964646778847149349261417998963482352721226955643820019004829309013880764975124746345794436086485714626451648600805977150640117805901595518345893479654988936835717670724884318192070873487543894386331355482056111525441696426051948232631043671371143697862965228696298741392391196941449688983054241252609515308554575584427185978096863888750824693110432545402994807205717323133405172850752190459202667476109943422410241573373698022479735343657354319748496751385763073480580501733588812683059007773495903529327965043761106054451600132937952364382837086187036444722430119083247598455858244430762446542826629866996492834814026803773449440995522430483940980984726305696285237481914071204742568680609586863659745113750653550689592779518657849085240184574742028251559922510452901860043524041463658647037742238893434165809470292570456284996915545999444251193381030290141746210081563107140516323538818377824184714603638972113832527634992708938190408049158080822024750184714344683056026297143611368573505838395679122109456872973271435965970527537594370948339800488598801160936453029436583361154272047308679704361864035171592217830334405563754399107324217094822176589598259498008224368570514159771359032192945865791926395260564056102327277384954281031168496628995748840366862999475605310775537492410538380205195556395691185405441171726671783380888809158287984772020195607983462468072039597182004808135749286865005313456354446432738488570228974748117727243292966261660462321422971309083506870605186292992748767056948987766121194450203459009961336049593046347449948501671482126552774921617888757635937891504694776592125033239683524380751023399669802982256073198651740183433268427350019466368060803123948190531505371279763926080627174597753093877528734523928212855662080469535041635502505460927247305777379655740309932171381671180809455637032819530657126587782734561336866134042972429630063420853250083346092025567295835389383686792213298721828323324305898736220351086101097969171884600798761910714084349876267672453339734177791038756760710599326613122016645473079424620142392899457072138341287282078381624631678553561718212648954200520923044691758895240021822640923551509022529529610478774889661172127429646039557160397013489030723027673965599970182006545166692216319834148948911221110993150316618459891132532481386535767646150044592084755659960873845037937699767749257964447093943412785019048406187700597809521064646060033336704823778387198135312902363743784818590795892908091223818152822931358731684317076829480312231466239059679061983552925561573521123882109112017346689313359279340875176762340044748849628267318337526957942996149757833382531252555431309670317322685311543858261899657369846419700056910830440604363863014750358220202692828423048867253620566421984645769753729614654489431735986577510895760028157318581579485270642837299737647767883329695468785062957741897312437732055605172526075001080977750423281764412224932701205315588897913699205943463826509977121241701344489108947626882090923143622461165936467053054304515875565956471807711322045854384920524231562813392481375800843712043736637338981941845236287027383334967600303975092279045656624758799082664016662539594147341876657113272869159078132760283524980252417242999370106289782946386537464949173452231895020345097250984243182220472603445491714599155572506670626675211074238282050170763898079026238939628342685735490812491724705490340311090765668329360689027272806964505349790520466889319056171288731120852099897720580426057560337484066466315700107827033505530845720813459411427266351979577490192922928291545480377638447006274741059501405175007656406697308028372202204601204382150096304144605786956911178488102758773181739639967330494233255325788741410825522985462684649925103229098618464284430010962689530048140508490764439088989835709674121284126411735968182179608799850320992610335418306811332335326452646062954283649865894057578409157764605009877104819439169835225874969674811079731688354146167896594484892543332293141728201486340258281826592517332641643843487564161458444258240685920802473806412300683311533276739861915880812562538703669289333566962143062531354305456847886305168836394051793048982761585783420553757692243318865019774855310724877701102588748614270963965467761741669584923400189861006534169908116658099946248500888354997950655748799741000365568018336490989815165004297908921075477512832648827943586442967990684136067086954058999054841239979018223790302917631975285397592942053261422997983747116384686656909103115181431156277810254412332807215521521913210188561978585551220620946997905436181482382812509797216214534139208438729063119268815475532631127917290425824545171988550887423640063405982537561548346413628863712242681785132671375305935991688530429003042194031750271644151411389381149052294005267597471403423250867152542749149178912822512729286125408367351308934717944240465484641795577195920433614704395431215233445214762102456860712543439607752146117823152877496307615237782270474695837617786842614444502256482578789817600157917636415994030480609322477903642054612366150687314422954146713119505411836749588046889579113211539830476187121910605612646269383131868208217353909339102784200141724069027190113433066436228320221410158566131026128468165907807435758418013421625857870007622184208914367965234781568790433636034503103435020834332476616909057876728754387504102092210928047793333183472518566428884705653585926512737753482973727183786825183580572713767119346615964521796867596310010548840807546755303981587583030288557658949650958411903588823513924732485267115171111506676066918066904107719634258550982773530404220110548665697912977833960430447353845004909911303279635186313541411818532323341427386278365167776601690816802424616844372740452859673973150101216703623096083563234019786645793225501930118713004170268183349103077731107258049178697300463457985489189438393176018065479038550718474274887817575086539393810822899974631499816496110494244129486286210922826197936747790633981677436502922334909921445614737589944467848167246917428695872001088057181255744648122517999075266657602834478853565670186154923896767519659494562872470384117362888150364029965967321511631733219151646648038721317233633321508080712014541927562409331021768426387190218707456659284347808807427328083451956836427256899097276118727729790925851364721598920680287154381941836104009691057049672371739606582800181761067894097394277358064020448784606906923836673383948698745266794229963423994725524492217675161409118905627232013188685656338426552801768532063328165027051885093188228264581213805313044578658546746142243852544028170454888159624837598130368817059982907399338079131953092875599302534037534493538446263483767146866060174148713795386952822607632916357578542043442253219429428321099538927604269192415840408547434508997663277672854243638154809761320114310471289604552266693897846220052787006616578624182856501140506091084553193785629349394297414303270336850138097988709288401000509572835435809496098471644365567323643258614561643369697597132567632158175318778837999671839372662245543698057593976828959984773233415435110614484300466372399048661686410077202935179284386940136863785449704388572300309149553493702483507091956362919340041863581931097116556493047725365455421743723623570007674433424122803249367497470961195116987189325683916808680378708883441662736165417044104473249366832409588627850687122333658134431163599624702558433801653096051088813185446140313909241457065935556468688992589650037139142818929172947670247414701173860669311010164367989183440325298136820575396000750684019767501164956792925517084815922800484881296764085623512338960498369965940475587228294741535131222011942734064204644877235033588919207704169518665336768532484173073783248157233567136746885034351046815853017957423009438272560042717062540611876692207565973507375177436645114212562584030412691717763618931610915972872303802551516648509638755507146504171678990153900932138323259584691324322445651512868889718645845854388164244305149188431015701151567910391747870206148745784697894832268425395418290507249875083846910974279706146668262381271893604249107564438577643851780740049411472964527062771993809387145453729625634989160675428490483602156930327341961239646522249943283140221543286207711543096724544848002954721636060531469220607463863138212397172874931877752205494667857451044707701356863227259790759009883682127785381590223678669116303161095792175571797620387032290320827969308698824248183944550825525234471838006474449803075414157934930241062348165743261539702660017011157921274481937985448207055846387082788797329233667034437233471197917264835487601770320415362928717414496423549113211695455692909178360678857487735776875828418038006354319442489301195133382402231497874892332937811572131865154751076536650998917540437642691943319263124635961597537132136707633356404674604992885037449344401558103283725036326484360310981146909977131478778018348347425461213052091753907915953467976208479497457165458471124573544646802639042844079605669227590988506218742895372976506158292594238259046507024869794439465964078963822964111928435452669945156056559649097341129029114756096175758524132371882206398939992011706255622640709160311423308231188191305376323340076885028781525202829935553883558158160927610113578459651745964228335436910472042549949025258311538597970500375119838670104101627072163197857384697950759182475740450631450214106612170997288962680046377621239356227730467426373820281261258062395954974691931505187417228257911086265171913509432414236012383216066448666187211182574810016537068570808818413791299504100898959209291430086065124527569894865612838041952626464158034586747985578176132748033861274112722784597871257467779804995963453291442050044388405899266606138172914594468742554758849503663637741453115296819390421337598751891903336256678653101951702771774394473609978908439554436010714936019989268915387978241077246333679854536330747512058491394803909983398076964890933677943029096171911865985376850654443993007953919414489685783873652562283685243584750350819178653616011626552914610148930867241608740496701844014528066221528459522129598826758156410976552628770241509485300309323987601466339444176878758256137011100362314789120747009903465621525199388145809956318647032828003017282172015307731182401368748515508733143423907070173838085582542285180152521779607961296065907655492689862265362950466285474782755936658930780477886389090336529863324662696936927687837789470702487998616201771422558968301383233230169332257233660206569418285856593586468502507802698350498416196978557192510485874990688375457296722814842189932584178558604923841818563201086067160968344724441371049096888001797469692690223781987121167691512753166288976381253007350641933574825264025196753256873423240019165022163599267201932387856053111211165217441282764857399455579732117239577148547018539455108151335571526376822119697154345888978759913239530025410666766911104839968780921934554982211776977415152180005882017113007535466827593363650266898039402981957034163883880590083985731736839905885112842416114447751696479097560491179994839795262025543820513225880954754805245776188575745467243170584842241959308797281241961893171970804687424254056842803517397532607545565014433309970853011067474305622917857090078363035889336640595663291093230921885808968880751193923736552928665087211296983891823803890114652998140874986824459128988937101364527944335716841987723322528599815305759171120619546222310523243839039799332941873721518173420738890601813405319180482271900626705113726575960586166225971757538275701878044035387906544118985157003463459799343244838630416502111749939894882756489052966608837340221329177491172025249145319062518279966184992673838284882332604331754190432945176816246198050779666140738272598833986227743194784023165167805558842579703207467235554780220411280708039266250536276878733067671736423919422988817705809714648934196469330181263549827555496868693905679050829659093412858053851047964660747198138188130683685897238526000256677147195662487518081513539939386179126216171485111294774146481829612580396141267993063044463749967182158007675376944816190823961296093686554998317434166949436932332505009451780267639751513791520626930465212938612372074016945991400354008330629929383152523238887212263826643574411885029092348639859000332586959154445863501739552745576804423397028565806595815566370324896466397936726610272282475993933598178347483193590385142759219017921798481044834228699343472297454655920613394258796122232673830455769241558108214298538615916564285076019111661988037214110511261331618070094033661992259305087742714272982504461199974799433750797080076871254035560621749906567237988763353688432196990741369950112206527342061175350988229582759318279612297846068519529926583724821807362382969421651362530729455616418216991249312757786572467056862908887491302205741719922197869800814433200122164613967975345441383039000376525649343844996349867492790296817399948260954762569718694514893238212437641820600804189625213407606125568707549642604781839768243747308942492849000291952450096861447210663968132834994485431901028270385874972224983458975523515830066883811564655243968386691977064877553322724849876525032376245382607864126638444270495549937219515477916449800755793071523103281267362414539699660589422536020748450304323888850240348449785145011499671133733048018047973631170365942468589417970011692660034222268415799887793121893859566020840569178260076419065012619922623634207027447606627575230258455811405924352611770259222144019757356482083129962611793580776235042882262727631922535158545879157249916751782711495491317760780798075016756212762710434560989582501912032153116923951755472392577969259112562377001228053478009609165828502549935858205504717819821552437130122170914011408300759269353589633224402322839540955889629474062240861426105202215101147300247026849900157042433815006556960234467861086449441279925249083393751703494132833444156198006212464138826288584107544831763216157937718370577620928751022264313427300537288402669506250274443072015275497230570380739123607583486836859681090147818048641139487423696810951745028787266340606482959240942835017695072269154914293010911181860122516059271498655049561491341749959838036616812117921133784389076151558995905900158842435882099384135777411989210835154784087399200246585466789515611628808516578566640564065048075481956489343144895406216597398621532098413077425612934934287531489923110695960585495394949457477655517521128689923779639681199806552260255389914592870018296423204602004511602703427388816239810637779119133135072647261452014763354585730121811281520986341814614487482434930319749710099686530720253639440181877442285791284442561199070099228270908626515552763097449556778591689772002919213996688846857592667034154836638725569728670070894847621677096767084839746490441944422396549136386247384678337833949842913047461723440687162891670833311855183655163838499325545177688050198684744296389527754165160972550207800810413866098250130691506511065220090183582786149496128199561623094360561481949058361783673259016538210987926154974931842653400624464617430577503391728745795646198696506986090175803196971304450764521855370767764258531154717504331822157400039680232462195992801735821590543050485077942073581816796507207657409225721458734357786407865024657361696765937483031813563171873018247797677311309298706934256020840729131117501366368055569789130947000951018999556149820932298296124679209177265115745302154074468585287146870542868402644732527834616430088221929920015366254329516001985696948019744523001470875489757253834763176629074744518476135716582401285113708690265323713557836537330134671293054149767267597141093464203489789216863492461212972523303215332614459143702441032476918325604630160810009696296785980562124517380892904944030950545642329171513779842470251865561648784332736254691303001820077260238446295728801844941581997929111944033757888396360272015219317452442692634922283520756280088740107200044528899356190370621174585240258233646997393874610620616615690402789345811206579123050613660784294196653650807939139773799219150264192537876510367880580071690326067504289631285562105814424044327446568713194491184334470025295276646605599299072612282252024373646277131556173534621523079427332492561390958887236822899502067416564294796167093872969203067577970603151553288365078261974009866927607542412250123460735561343558001823825441874637761596052521490169744414006875018216127274205180514433740351519989496577821676284191837572299576985624368347591217688910772434483357608015298941224658052574120254549162669753829651909819592068764275771087089800894846433322284673707481681183505365260269754532767629207251090922877748503731261886454269904022851265453676478380991393774333351453791759812428931551356161010511746270085426598930632011381762697887945077741792664626361391161801871843329886719713760096717195226818664767508713695120259787804807934150964599786072841110509226105842441610999541487587296348722002065024733355926719723988048016611511004682311122172996105690527030662832479839439912333721478159747744357013440567639895448903829037958770566197518023740419619562228273798249801942711570560875952694108099561845138404963316084322496014177040881668167380674106076085144226887669059592808558366956199806487469126739743899189144628049123093317793613402171096678974293697494886157337804846028977309376310375731970611767537772238796813531687812163122593573826352522682108164454244020483837544858985205192995756043998044161247728680985851866561036794626926604808107518174166753688053330950399403220755292501310425767872577467351116216538754837156578910809003310645275264135045902733390233993795274288459389222513071159403318272402339709935769288298997187966970842849799291229541905414685214643097214924632742024283984013673329982346723597603411306567424780210887650560796275933711584313032835883643599097204437894977360222071854715000460073429623012723247138650797110936621369206249812123116122370529289953483819626644723538955655415856512503394557360605318304254710200631726084155660598591165029419923330655483415491411168604766404561102013895063630235247427468838178673314035759909627393842971534475394314618940834578409195621474471167912370600450810114581416126741620639156268961444305564522184882860151090164335254317480618547113846603942312423419310030152223901874364418673599519472501072585613936965626983236835738638683311404216318981322392647343932039537328807431370809171662593995417613862987614744957867628714540969007239849324577233925787280763776269934862236978440158349099949920431025296123594360061520956274919707479607595715136866498529606432621678665943323277991856987811132658267802134815887183619894450108372886205236648375691917494403717190607820462171787716909505208096906837131313338297250527492374993980349866587275593918629885725510071175062393906220344537555343731695324764257296913192154043439656528478826231470366877225196589912962914307473376412563294816996505448717288778710563918205210166969299758413996935451535210301426300137859297347348758940625154480628723325311677676537046469486240108160573510453497148419860507628963717389528744963583830586054666161961178732425743313451759977357619175078465839787109889429042114037723778426830684322364386870191546356981813394901482311572257758213357644128067692172279848665594968608081482762920247067616733323606944144693497716253037030471092319620278791492585672407599990171428136909047747476723759223217012571320987809274114422744697457052927319674500711910994828126832850566669014691508265576716887476806317772374003019448154409225919406026354594426965868468127263116083916111153382919590304874474963900214287670696558343730310468283042568921116014803610350091442795415747510711510789780235637214909935220321317576660380990794029922408013765589022977204485305874983232326437060106863860346915528537808210366637150361882642773645413398209195036217853305159300213206507796177717460277844590751436258455240723643363055472766817217779082338392488916598444137112704832842416454202027104466362808123485422464594139586584058043531561562306375961018325408609358288789359979349546721428416679176328930265663387471942092400201043264327299808085775803352517245705958101649811564851318400123728108892343425075202001160285781602014974041349827480335866949876339474487730836419520063329886680042219706885908352553685906799863833716548388120690998429092044656332280840601046169970401898564049881074070620311573423824990447486596962624207789805543140874073165552744195996583892542366757842935789568928230573445539496333030572313667794489048305537095505660075598877330352926026292370266589913688816173235945760486285039992943744156757492785906670141816351391560119290960471091648524239880818960275638768446279358127466419938103339323683771485752614162954930186857093561306477290711810233993333426205398600835448946340316656696188297179728767097641057496192825400076228053095043942708472746331334868054646537609113024764562837286759599828608446735684801052435542941123274463443334362740478512993887354716876753114353090781619206873794705270150689886615719623235616562140651850191684394244898961994655067396251146288317881160415656464860573990471041038706348566089213465460900312037012256073316625608226676035221348014977035512354120288274486426799880245178144829097415738837971518554121515941173535454506232587998110994825139948200547154724569474708567594675464160302771927014269612820655830412410570681142736153669023172828367021578162132309522385205197522056949634014812977565416669280859393427100896144054342404047563554689574360850298965183114645611753501892471942509133011568326462763246292993507413204225821830291914272817873353638482931941469478789993888256782912820535489108995615468262601487562596043430953501882396013525770912988528664153281933793807586784144467785072639779442618759983269043115733981204669845799927243499334036278105773244992441806724587271427857131253501708123792138548033244607693727715559895814942058408432046165263319375049964515674446191227125003113825842693170585163177736310329604502627743799815427901065727115678381987268927268177393198378987309485494814101835265922119340867955844025433227150790293508376188969300453914545608497099603289003342641040877007239457503561678861205459744561788526886924702071466943267085247569236500304243993426030576865561561089189648041788627746267131461162456398686112602498169902103261416645128602262375911361723615970118353504942081830775460809952949999135839892487614444882164018790133608499676736931176414165281348074132323256881930368188789922423139077681605990050115166556373700759319938547817614485108624779777218350776011393854917544405853273807193647592588552870131696444540628480200208846607448813035807992922645169128234723276271234219533646990235464542984141962954451570700594601800320152434953911019996906445420004059600502749252723498240967481169038599484681037319561282144656175009376224630920036646218474247298575308303833131034184361251718783544973660230410836782072205444887431550439551403909725686735823801021891723742887346879525442705693475206256522886591609332019003738064360955843731469742983328112475785894901503550690463301027416403991302871293830286089729976737918269930716753403945296422299050836885545275688122208499618637857693437079465808695813071024816146756675710603676372697741125681889047489975203089257696601008514126750040139565373321919167170849346297450283789230562326304718438103554586603199105394732449813156227515454768811510436129115393672282580405545178357818479480922160040402826407150319355308262266177264713107035617149902328448061687299846743262614719589660332682601611425810852873480152155538652307576924642075252662707117165360856654567933056684474964504758678145346457000294255020009202940536181009599684454549557858940881860579941807624125836162551754429883174866994304738560416667905073359227787738856011348649379881384689326256761803663865296282307493430231008240216824375609535689026457694453740388394014205706746930125570640091265992802956036014695064259609816979945416540486233080472482030404167466975349263063620817083809743720425797208482576001505405996643752648668805199170070855393091134887529417027921482446059266674226213039631254054149148389160431818250514611892412762678301391004412682138457344653746948440553021938382267124102468083990356829427485561045589834353671880086615260691504210697662964811367038890011925742297284791180627130223594746222330714228686387140393890601746765077395649232802806198469982271679170274743168040610705320643296721178416277553567254107395532153756275649016274075799677464987936157668400454915962324906781991389992126280578082410932001167161482723900209723743878281959580045223534809654169741023794288224944162624046358259744382086262305779036428265352548004575946763936207630602020767843471066136415743816362094916732612163018868115655387691380987134793113524837620943315975043123941495639257823227633694047730009719456246919212493662919159577237658427860526350308715615142414021568608783438430852227383316118008979658209638759719105099945428442256003573400428573104999285170521172157101328359277100633803232094535665751405003496065401746177414982791720215085682352482722016416006358996675871150237832093190006693718147379069073592811747456108699124975590509612855293394485259953471608932991188835359352615152985935044272215117127604441533732932003373660022482162573319013455159321790816976397479751029555953668494693119948225316213763200943850816416702919717168186035749996145908750098112849308818301449834171362093154084404421059389510903733275010907566385414551185866309692596659083134593048887313201245259680578416435354136697480726005248780549282666390503445674974279215026102698285398797686449705076798921034425771134553216761649273991044738130973517032890964835040566625538710612244663590673867083540050294659998645357263716068406981043078502479589457636660542118971482212456769598260019699016005540139042693936943865734202043637682687220003819727467096311046220007323992051718318761312919994580561432005793188272888708684214195221074853394091082438785227760623787655629453978592093631212612832388768826449063311183436286838918612437057194552890913710955336967283104305908672173026667434318703147417060562691274449880240237739646295298369487928357979012368525004454460925184233982582226605710341987803429318246090972098739428963770023698210601783875227043029803939219695207273809246448080738185750351303695358789209183418140435589333863179699631640559067847442558791152630107868454290251912056321041133029448978236489730474221581313954130213760175840350051982804822624718931924115554775888629781361411405527158697583310785277804657183478653777195391999094737199637959139838954163742075945108456400321637978945613052924461399429608456773224709849338939200041984479720385404086262809886595217710795108093739629529129960979550079777931093198181432686019966394703458016099283182816073308625395496762524236993104976551159539464062980378858139281353878806983335498663397616241247191047684975045166102093553946474530914716320685886675356654396846747908743642720810031046808050508049329623871074591868691129292197814452167836171181060714898172446589162886090006312108235209259196800297497016122280765452379471483529663967537924138018315951239774871724060745939671431699391702654336847838968111916334516269132402480074618209174237577917204815088547752302570776576089668025426925901578069396943095002974371853938176976903603906884936153325436917396260473940121828883520895422028432785356428054723546673334521424292577593024325352955870258822889711983947562004663920595766311604345967377955633487593351473512315889983361260454993893482080620869170778855821577683102303489477814758759378958174082139542047536886420679318778670144902160595723583478519811574784191791712978498816153711138229387851994522497368050679388193639669529633496404908825772013939364924556536595787517887676773508765970445849523830031909268898803427247604157400257694382129528909125620265322874283676863352309344519403844914005816685647230379849854294795527282764879275338963395408400627346948243975205896123050503670864190697108797527938829271270126547523886425359845984249300806279446868875555118563304291856474250303175555540977613920687667160302802349039421300794252430760014998181128449929773779862960905093048594850065609788022373261804740465391870650245283760637964649283094404661490112192108775379215593229350031423062781722333543124205024390914117772653211643273354081358152707054467060042230095519125725815197111024727165406564731135526059613787034047029353191413229493596282884580993325175711341838045636252316076747678210648862235240968781541614359946273880954924270364873597164016673638104002026931645996926061040335718684489836309107589889839704700700927718559232764595483451816971535614262008571348275444074720893267357667536500678014737201981231873764812572124482115742758312430353959306325973718770747574723468255036055250900976239679865158775896389528972418564196021246786797106138906363879890884696702555334550790834200039907392874425565176275453883017425191036486078616263730315953609365104316304987449311977628592764656929564756174064209482598827743928393254195058618539076234445744363028536451372692389196376115244552878273518905581451233829340160968698242481591407442775222442797953197307881404761743829600122680363406457031031085281334865892299688662749146860175870782270463298539958048456107434830357451099251595581801325424119898053713001710858624959972870030281516982342820770814411456819782550813752115773414347064591376246113536486885329122575322655353493742721907014263046159904981935879178815674129574250873091017841697871977668205971167335752407261251252521631117614242657127407379816502264542344014289050752957769491445676317163774720448997840897993808190708649773679781780086106565763352790931456507424136846927890074279407571653250700159187480281252726566194963100808060843334984009374500722847894249917545651314498410538117855343867900548399275668006768567587017646303648294622246343902585374795922030589796428492771174725076593475480715739825653431315253290453020267799712908535556102106367035050364657883774821871390090959877194690318899636538295836269644024123769782333533060369849643390380690266538731521977123433990384183159426263552137042188461649257409383200922842677395282049564162249604568114310168553066604619803711162251328927320988720723996097070759737633240685417984843518155752615647480187150330797776329785769771362666099442230571379224462214127551132429847199721221056938025440565434846526152727078111271826980804354323665118258497022239344500619144308301659048748730202291434987237345683007430424191127314451885580860330922809972723655826271359826671320913466353414804673467346378694534510118723163305717458857881600169545342786505294677535958705159024701161749113022737992378652430673618858177875033096477496807861860636188315735920751738370789169926018603471764051421610413417950774694720065715505843431316529062602790167551391266282282853811860205417507907895699747999481811896596630925920081531775908229807674347509378696546845863210371471277254759201285000295494312975903876226064860883051112654040629598368498324926858430416014924634811741005546823807083147999899637639220204497995157838080472013073142613749386835728295705478694229979268689973458800160683474490446012710220097076322615056820394020453403861393298006679743068739988440285544407511613791836006835455066924865839677606896863171835039411057941354606515308458761550987569591358784415770598199042289492952696748395096731985046733617095834307634217345761639591922287079853719454344288594522038039500656128684258163354239614807603383105811376778307235084818786523298604619881937575722551007095688530247051493131888747732688647890670950026036727736138695736805339196852584752926372369924930785756965691552497984527246888303027220786565868094369111629229614421129623830031967334953500065743614980868423095456145595305593819464370538230625491376094357476022459186338205356887165027510433191925277451477931546593354933469462307114400119568915881122838134411375148416463875027513326049369036479741910961896364047546751474982378715576641775281219753295088678426254374200868703420450002532512984498669159701915360229598831090327460301018013452880149779806752052462833278087262608847305653185579305764495724144043546845172824956832719846580300021371255544371944592226662054600745801556602037230681794792692415888275146796816175868451231053242781584512937586103605475161382402528173427227993950016333525599825488563950675482916887024048875076879556063817966280607095116758305327326442653024009518596601556043405400088827760977841854869089893918630005155061090903069398501511721484520062496104436432261549020474613919616719951476618951938916541469786122774038429151910743712216374123373492161955471625056785512743833513827777513635341534802458935146276808220157354254465190196212655068198144396540987496814886631832844679752103537245968039408787242889105385307939870299680833069606368630530099300664995427670905253691151175659388796161396233351848694952150589363872426485575340595649416283262218441100070906259881672771160850878222104827623967802415889356396096576426991473907447637934034616743461980180700260403779340618738444030757526895471139000484526722238149313718267066312057359820153471884261357179611316956181536538186126523573290929106376678187474599595090530860677331255737214259566063246622962842088636705087236117883140351028039911423040465400965550775706462211667463548270009723899730139892509243354030573669235110474392369162407756625915311884464286874602942186578882170822840709664108167142608566573295291765667743459681959654886596665839703972037302171619691843671007589135912948416280399276826082019311113500685393204249922519713250473948314378417741484009999571302016142592214865081719198812798882533810792088108483335678244843419863390710233330557035146304062399990084899327384797625257057847456917840769499038625363446681128922441454794011959469921177484333098320256086105389607284939158617536048792774435090237241788839804508783555162674792544084480667023507818682031814634967162324961122925616684398119870353661416088610380011312505727779327487252163699930521309879533464261600697115400934698691395777464262241840756982480157880026476667691799050753465846059434457208835758908679322465300498346213302933055098517619050004599666236014228113715701564811988717893138260048194272593016523694282105963063023984893970097399202185067326991321636027419852054262447932730242209397174678511093517496573740353948539793547443938861357808290879464955296263888038582539433437520522185380319425782050252397475394548640914640577697635609356822912014449909513033542102327500293901688626833920897782349539097073434273110175779569203744526340825235827924911811683847612333100740135418453788455982815330840984798372085699169710499592291868440078849198074629739445861680093833259643163736323874302069570570231448185928062420664304076201952587273697440351169522963449164786861861459488513925218729545758035533865803829572103921204719909400386479649236225500056990746311539358519332513486559108581892522059107731761643697825833413714993944409634763620005095979352939431020730533182391071702594356866540125916479936224474063116805402614280401379332035539603660327475705555616160314850201415177575258264442022326496305923726836440453478314789352520516001689015112193587107043207854707866397773969418322681976375520683853549128577794701033348121178113046836971320893845417806162602555110667615583820447291847761789028622652197449355893730508156873160363282827586275336942951795755069673899256986423798478635019330752212632153239761732685958217583269444874015920098186803111963870291466514456629016275020635144852652947429285018152656156487839501876087966774475029645680330226476866327763338102558895863364389914534037720155912978391818569589070569740459237695586252906822148753218708847393002592295942804695718706699912176379540099478823015316271671405790328620242698197560836631873960908382034155583503683163814220362178639660337762740583148520547469105841704800295071991915353761135515687393396235591446239644647383671676599345280133259279016404525934486173591063235561480790353843580154343839225296946343368870412399405300175348097463855854493070169265454808445782807748284417863559877814524091091865695839729945119800916351176169808431354214354015447498458990845623879665976923503028567967024699136294815363801628057804127995909962527222932311222911353844199150504375200461038346312937427146462501289458035672467781042118982264155693344421386336562867071509567852702537374765980881377976755110414538381478825284904417810174760680249722593126769113801622231146944640283318519542848889404791045899028152077172446890297547471982253931883410619591460388346206860912350637335856068813377069054606404415026117355291530383720098798072524914745843556315534474551536680626213011441088308276452981524436479875164010978582161616200585114234374412186475717427276207483230806733010600258252057532264783257490356317686306433732939053037010972438397535204580503467821375502141563713193338841585664867882235652546174046411671757090737604999218911478713622483848910989519928005796126502646115630874584021835462321192654046348938519510361822421916501159492456772776467677765175671823255909913470633033095004699678671277097234086021787236001975173770619992847976827114884580515289571850901996045196667960627851872982207719753946327103587660789979926815857280965040238917411306418674853915593641036682445372501775226237842840708290736930514107984929947362133711749453832037532076056757685680142427629671767343305842285620249208521932925620318007449858960542710646185161956612943476438132239462536348457598226564460095382758626414993866413103174643938757328364346139151036843297143395168554003419916595348870641434693227219500690977461628574954349791500068632872285461251769455663660546411658644090741694969542351031185912626903134752724989485407470427348579120742838476688345981540759820947306361939219002117117947383412706917399931908585350750370448675118009837926607920667058801165929823814615344398594576795335142781935884308953426014742524902065397912476813832576499660147349267876295453187346054046299289198858599475683992788729266383350601322497781815888050547809287763466640236001276529379679004064827683041606138047956485735615271779591994624021568318620375040143394715806883950790312593722608646314312004796392054237917708341227265675103576395100208366407502375948244753364506473602983538154015213488600683234130763407463421922806164282280669998194979994363379075841312108687865742403395517183043789185731648022583038771347884532036423808156313640180171327387565258438684537351056466555890789508692281685892093441630770887826776090776343375436749420843999240804885348327876054517154771227628194097704975024173862803592067609283246444566889688868518612082353618562036544160282108325161033215279105093768901222837435355441136318437853890373892109881714538921068945354949614828744777554473408917604200547047462071643243984819961549918401762371168793406259000386235866977373607369028803591006613336936077222293639446998887847085625608638318291531489039954164646419961432935003055616547590952168198227882388730642511351446664602759008040237476086144592984536230791993338171856249753792948044042480791865273148850300724611169902913394525018070010215633422346571147224189369642699319209319853160938691596512006577939322876253860101956375517716196885079570578200882149442744832871362553429857488554649721374121115463036599626196520373429439613302574032589032216853872283507649498175356853157086600337705142892358879206954901449352389742913327433132627972930352862691471281830217135386283901029780507818478081069890101615310239838693802153380051476602998445942303018431194457181943205301496129612446501357118628048162227066741488421785084412118872251828844136732010787265357483919271088036566061541900360825729282598999964245240707437365713687576251883731195324068498731453328503897808789445131691179272971861564893985050127940549337026874072144747832308180294298300055073714425038845532183144910609274128296764735395556859854258349674915984198660739185539262954526177275585805723910647906683819197625604518550277240114554547505894238945600054603058258147876233368362703289902622733166276043297896289250532719111504765039323219973344989457267546604266823831892615177303908091241932089188965170447648405783348571668195275573077549352051295082500733036149536681035590038183379327440626629543550884491701339224395032194130516290781480719870983421253253359193318858379011270244990530305889579320651672401902983410779609425925632874973676311059590219879007282285310558244903704070184293070001476190808474206278832888148301420437455334483608249924647008190762254699568589543970706192328102357914888958311345195022865924478832577390794254570808266908067179960645527582665857827173212266462639894708939320005272190640995152550295953881706617916462562110674314663958286452075559154675742263179813400345184342780309423311488716811273555232744920405534199429009540555553156787040909606113019468056914347075417317485486320162493825879165003929098706934099005616213036446061194733036808535438327440744627286057940419318578945467214763384947238188841035390540740093519006382454114398638005194318471554002834539223154234053814155658736052171152799016805932513670109173548718464176751161272191892213974087869991912093779515860948811747554267703434555854041938100758935449540174995964294482618938568037935655498327842612423976738939059020555051062933609934172821413710439819177137982345072642860319187831170890820374872445665489128467327592487499842897098502792361922706207095311369486297722270852291168649807895861483971830636344561463843647596201062399920116365219922391555303091463037461625440282529687376353160811666107778367757270187332977542882887139495647103516540484335003613145063121476140229721745495294279360390225511545051790996169464712545920621370483639671182954747732565329424977812052102165555981103354038548144076235705339715797917177634921243214735342968961188212347421278609701106707105867546737630403172540620243359527210958571623107954244491320270253169485048875329063667459384725013655132411375411788603685756846314508435318542792337088920846954878406156431745609187280076119993587888818433841576544086963247883290199420621434042119655396952205144947226589529268220062608649416991854070373275578820822092541651468016607903399674898678207339580417838809343343998836782548167150686936534986438891581272325914087895646341602104186602367469378937610562133159130493088860545887346618119495053451270651102474652165496491586823561967316780722407247328077730537381231547169945176663820635245090794415261042399091794510726741034407085714531410091271920399283953163851280495752130223001811280098813354583889285392357463305717440453106416951345851837635330517699010417884224019065157184195174972080725375906785370634222509853281665338238324158992363533409331277154431995095165356788678794719338737617929291049023892905842183032119133839179765852006498463203192420340652351668631015849392132321427292163459161527778465521405156876516352115540846188196825648600424820579678184282274862461097019144092993154759446088874385452329081485645612863616458527228213979608613252276676910265675171323183894025564398237820973630337629896333124137797464271475664918133857598017334815100518767573447652120878505717308169657911753787776817531730362377370729430206955965992584102834531477565447994197661518789633085691419043299997043577723911262898668110645906392865848938536439352238156048262587851212241135265410499066504007236396983010298402422742401174873889752071556153378227398766753203660491461032424912844001501715571464988442652302009265519852993644415495551422215384173479678384773128862638573154540633657382046524031353593708266271246511540397636697067848041406776278610461166356727107173697374609015188804611689073642487825951510773153224531407939111529642861109205622620314326831872605548549865697475695422686446710811800753921791537788157328628800094160176093701777072849230379323193212971554297157565415388928136285702822920906024819652479521497213477856705556749249345767207497933328279249772423190492720594767993251323883868868558480793361214715368674023940433121524924693852305184201985313483740816291251216978929312168445742033076212901042122108640484756556560700980356354111158762132631275795495831524516842179249707001048797832730719308134701304958443804888094109181668250967086378871495637807621474525366419288634599865675132600687092890874133597852130741927580793198037551042709417232043555763167334154854486855398089121382194535741110384424115043721795056549056891544203917510784148272464348303793177955552972474579981960582135216193371842678314657717960628367453815275936036531297020813446625639991470805825168812890401938703255264876195217540035174365404806159394836751101031675631799475288238787005821015361998893256148340815133944083491140402538893639383271691949211426668178860914799563433132578729122314884279985651848407210754762545823210795076860322021851512470982772023571672061851151735177049469456945699522368464712605318546712604879232265081832719407704880827397380381922488391851446819477158567694607515707931614593357168582916910962687306676767947370714911880372271266037106464665505805709151932632440533615356035207874143254561468130410569432574354227175809578655421301474007970033457096477363970295340007437013389939540836462914345088585767232388091860949365470586112130620249440361058081777970079364600529341662135200468017276573920279500739316376978324674246976265188360613833834152674846524437161143784158195261649299543705903444507824446142960726443407060649278432964683340107249256873701824913391673693760667648960550831551722747207479341034612817143930983162603309253697966799783194329742674309787908557953865334855335338139143614504912953385721322661012204412643730521313216615197403186753594140424360717206258998234858844196303172376271759393124761736622328326579714295362600273714532909675491578410049495413678653998578777181615915798815710592590527845366190884642302039885655799914143500807351176553368665249070310286155670473157019047538305861534857230528180456893889089825269992356961811986643483291415055657748546630845278452844302118655711332766581332861935405766380663067469405973832703006759795068149935647594562721635522397226415436364014618785927279905151238694133109322980386876235271731998389956226688748766603089627624868863810178926491619328564675434130507476433458459232162958539630522422472838633133292656824917699825395622031901892947070038198259914052187218090503118230482201066905150842399667708502736049438812342922647089654690202401033870103771059636431909956794961075483304405529801740409405957095206442668688890836554533334736595833852160228159175258381904462989923807270390295692655023770742819181261772106609963480608970134376820447065649585603996855235998653040934178385681464890525318231574030537947242041837931641798392426893961620244382861787907511321666908277169045757029189440828937033288774439421325531423367107981820886399836739820947109828992267366931356841188440257782664970766387726137107394537067652167568696214268123976383243889874217444233485382726299325120563369701793525763093827768084902804150007914433524344298487108895640401495409910172961303195244200330417284642492188295652545235681636882547869276921080352588983668663967430715656902014250433426027433239201941122470627122200971080615852855582734972459757296038713780032732157953694477399142866060449518934724236960909834312282712998650284059615172643331604788903350292887215240022770041975994217164977381036125742340847036555245122571984488575341496924008255240386772053890462528477239068684755677876477063717858619761690997464800996548154061913592823931847146407230205443701211239627804668749562276592891368844555239054234252926349891026588163990499222107830687315138464296093558375775538591110978562984633477083385346816236728365385769272692706219939518388576579822846299843309705407756719332119733551986703924211122155329387939355472895980471534754149770418470707456357711348486762158911547597232564146914924844389408501194715323478282518508401040798521576484625969882326732489207851387366762530669391730043706347358773317552493075476300691821096498915397473786734443973018394313446845484695088308749203297069778457898927335985177552076234010449307061014414638755292021716964007120548812256453745055249548851566157238319089639130699767015900757209796552972827008127069007671395332011178750637843159079338708351580431569491244553663849083010216773925845901395242020866513173052769589179551072906854508927823403710821303223323764903529021572305535629803347357737884621954078731031414477743978127888959953874401062485172676168734010320286594593926983548034749447798986906448374933021468402198088144053346608516608143378585150021395468552645867393574846842096259642870679850421194192296831871450118544283896194025481641260553957150497800289252446780784100922980702220502516508103559992954328440371487456244226740053388005250653581545454231480796791033570912124850995392465870472366370026757350834949623044310106791672668102948312945799985914927643290616176998765458461246241872937518387220553593390666342754537836424545963070068201496333211871440140734588983991578129410553705236598209964235266315219164411367908105539254264711409611309931262196254846132434074891875639571964640728054186478536035461265515186773187537644679633879696319054755216189729301367040128249532832342916544967927879779626991792526209146151004673620341283181474441741647439933270340781204716151609535103382678520453707484053636689007043152941696632107122681529573666249025428193107689814193813764303318589286195075446936877657537521184667753186709987206784534551983907474394950413670482560031655331868186638654000629589072863291717369748413548652403918141489038997109739377531408089682128501653171280255197915368604520151124724491360887043123539351886441251971714439484635531088025375755130926126858067656586193546216508278826463535262366443371237209867027873388040891427505470554369808008890340071447481195575715276484411834050378337241547705047029028263669672578104103044152421551521589580695690274493766387298027806794348584099862163142978557189895941296148876808146589011546968497245375989894144579379068903164112519486390829819028496054255034268753281539643659597965699727277480912295073617277476378311727621455452832931683080592222890356642107542922797386644263145525347264816456465313931632034283023740225151823899860083691981393162646068835405100534938262578320242668369515297293068813567959119862547192040655069364727638931155220641358481453715129173402434150456033110710465261281481111227955259428498868464146657733007781618557397385223947878716755083396292563665315372065370340151597048322640774222392789181738642302403596653203827512066419566829908113230637966353236333062375786434432332412197962973427616925408454123297731894241132097347601593379362003244739720696120910373903069040221759218516288458380318593626475272739023809316452655946868646556572586464148172412239622010230453551690568680681892513286795724139475737979162470861178970435785944212237752349826742956054760335448447969005895538197006029475581806116870075760463510996519571974790534980211822625691407925808166738989956252647277303639402114751405694711220934647021152435513048960156307147928029072030331499051768433939654498570605947549936356939301957901477175438896675110354988227421635821230074417098872209727334932511707528323302325515246751981444987914093806782053009335376785750257303218338412304079968693700488160906772057335009919109982594989279057870869964693759788921348622283249945267207977062642087905084658584297125011574710178132736619865068515294400317367823989638009550420544963011984297817505638468214983852751878135451922795988849598254728291758287502106821824087659416080748965531405499996724445891430082979576703850096639678636794922506285155391588806206928448526341466114843854283393669765890283228877956402962436773554333563717156629799730908813503594256399515627082873627357605539317540378662464882531088496601792801386905042848137887684946585218204978618637137155874776991534896607952340409538520048739802200729362431857492188265622726617627915184141976559109686488968552234550260037922161164161558018935677158507802267867236497654861967416110422402237209726425616569610701479132143501952648072326898106286905838339559610057054873344188667780574779078778098529500814580741173422715902939995352189886614505414916041037763989155670042474210852029984326879400138526167004517688912030017833802667865870700793271681186736710817623567794035029475870186202292772005905497968552356175072986922282280912462852882981591538174980020194449101418340041202943745735166944501387321132368659998795323789177325686415885045029185385969025099745247817914430990140139433578639497600777910081595880076038616132678631638771779985468040327424221970306070564161201396100287913237841666800546727170541888602383388148899709924890307547773557962070960546527934083696447575318996778746460388609489739748544494095956207962477180497073234050868251602976490345775173231500159353030722853630671071588452755223022159707340047562987971555768890347417395405709307354812519360952051259899886561866404280181561483672563136677980273302965087258048130554488504927931413078590710849970304341083114158564234730954763556556069105952884577030243048750726450505644405635008340472173784996951161113445516533345692454072398717012760992399279414437543712182914238076362485569744952809925756392886191297865417111039400613932271100537948767695090716345122698612291209884966145557190031559370329872993708024864725141569472234577060293862824097409000802990573180670711710870505817001550876487882907319282522859301019019227929214135688373882157069867440112691679637062424486709388151175194280135189373972511918912702556830245700498114274340742315807537902813575220988384549748257273405632190777979024551329419848686107777799381566909078106951374107257352280803014738066109428352384906851007871916628052868004832155400257116067211497298255361988725728051326073549479700480976500057979057642194587433402978191762479005849299436119697095490996524369156161089337875231247192737124446594805055595939893198405279382930372345377748112048741743673118070978657921242390544026789492581674096480292543611980953382818498818705493054457288167802505413246321496450222591098868052902339319360153212758700659068769332697587094650804291897075072939764854395683441401543708332176844766015371988192637912469715823413184117801825101611508596269010047974520145501062641641824454780184864510089957600199232918020182803087934651714722009218282895550377946429156593817395761907830993100780516344093800741425772026187065917292028942063777659337806942775076801333704112558104744138632333045831515066310857076910838136932792009519122379711498993254600260804538695955732296529773062100583785743043051954645831379143239481186675489742454992217057728263201279739053235323730812498805879946625419068399242534046283656091507910823180340383017970564178629004352172830363781208107603367421798599402319221147221797085673936474878420145894214326868435449924645593250381918236083962939444981052794600643888372245914789962592781263860511857509051148270935812092599946858972877255468133694823089962500298912986218671056577391800592562302831973182212676501423868071270002237628153959563506560402890619748723753480770227913630533883105926059852887673627887367810266813907906293553534151109738654885736801378225144177671774451369484454828165404147226121553199457802726417376674046261823159823319279201199677124869339151636660807908341341685485784691619828423484787512680490507233655004168206763063553298851149294961264528771125694737110392940629178333687868747573852668265380624826450146505717328423390062006500670218413500766648029839308347212820325049654459209755705859475753456458720078263818533855056051669758979425123188165559290719718023869329030363255366535244588604982471870172860440124459091872976856319160385628491152572760884526646110734680342750093286499060427326419854987194573201226108812894824779890228334646111852175600190117121534094253794410128400938135013139216309588492375070719522441166856840107744375215848786902709565664224111064261203061348237917201614414511559704392805743513421787490925147540800564366976276592575582572240662030777674150029389669802888113090556469318800133275925565623843115937614645094373555948945466242101228524271459523602649138413059735987581371754907576169782557673555578499440865234182440431412314563845922183148656749235794309277241944498575246857333732159683945976788674228122038934566846779789682383594243143714988047586110247152786425157095133855545590157593813285300503058705438724156299950825193748003520719736386124777575074891957794755586696783287904325547376382695966698771718196012906393126557425549219831080877250416475807244703871488578531310129630829788358225905491668581745741594865271192884575571266240325333415878273698434226296781324989021274663206820719759026079034296250598496158508472990072568352366872517377648964875348421071538751457023659216166743372661949564927491154451937665345764962045634299786167808036700582051768558994788467878683657571226029343939220369737083853316746568907567695059311490590544613791423683366247636145402608726911255122511508535021709395726096797986786844580631938018846066580000226915632054351261590337788271870104034535723628684219929416862374110572174597462003329146793368764297668934803904092796854631084186925989430558890509046185892221759112441366724508212939901775822184260812115549221208241374598703102003536132907956356853784323925547325713093885870708232118205176963068152020981943667615030848487551592752108849685089748707516586362300315893090210485639097401760478535900490742462485944708561734967902859272199834606343475547866834385036742950130774718825811215915313693540526736737471585338654718462979317266153318233444936374587596114170810924987607576119325997873503750949340875293931492627416163700178710307472679515910335641416784910109594151166527237980494122998416790062874689450144742025409343774849232035389930335802697128830032281814109975176690816043307690521886174798521743864705008630691713833820977040065055582010901652565033941231084045371256855467740520131517683167178271830062114158443279355413478513922120229508381760414335511263521239428776787220705991673791977623746283064477711537042154582550675392366876809479890412500713243682262815009223254682300178649151965572729797585412736144908747765770083060887202950877496758551164879686984086426202514224348708908971700019144195535927391513470543806082747978019581154858592089434860306888072384555837780295874536116514834486606813279694378626290842773056130757617768998137972363485689524265711583720207829307766796564107179685610938350158520208478721693490656288016015995533796678510764090058584207918674580939939598540847972979588021600314938937916820368426342647576638698455656616360703433860585365888958569333856783960160914867105887920976681846011557348611405855303024895708744364487025052046958133722265058509406049509031893938169762250288247452991322693894596677139462690762933945881205247534578591305409246944038232317189148917001423568910175188594337438740112979388057477077406729451512912472362507567574525310130572269182870255257056983825767805547122516816357478060529904167607279323473128759866214557224126248272214828820759072279037560444956219345594609034188742876513765992767541335758793933966748831630986538334134254966487111132073122470914509461872719832515710746750949865311791225461662959850487803529645697043718136009982915189175336771782164451539008221040128622906846368016246661317141895577742990487221537243986639877870770237449449442379187482712740406010257569005737055187607492550463540138847679675208058614898523478638681136775234645482077509489377683648425454874901047144573763161576583203534688581382980670762260513287437017794178084315165913487266956009126438804386670130467555595653046847191461686895193451405448474383214580896048505710583305938268448666317212211387548860465372041283984066813360254775579677610112701635076992850536332872874653036593827108897244549897156209759918924006315446340965694862989740556732566177375502462401608838395106063506524020871817735925841764702616760440084577780716090103910032655263381110717833738666552487800475408233311285499732184506029987191792654471239222514264507003463145082746956068371734117588951939445990645786692952060981480759276209059661304154400294503438024663325703049387675024044681156048781324466461452286439870733488532271255531175989046157408959624212841697765137329924582627656731935378487928787880530482295642538046075076381328394924975874467113053010842800225761476654298027283185165081234697839383861345528179898369858144733231922739752951864135108267277489581846230526745067977217282188436155347557601632776975408638056529357325623850824390558332933123158118922319418891798939021549061700797114828625147564926967550478468633148894551759626314395625209445605841046075060600482542007769734264968486259016518395289595627927724217513668226023027736015981844405801852031495279021576518395696328165639039173711909273800616596931095044391091796941360114223077669683003154091446419342326061706992312144966703982869129163016885097483279833153815988154947815964853951068664337238657840576281404552088605477529752616859859264777830647383360132030408092550755526594279464747077947866594189856187750758956873738098873269402753843218871626178942649464512895498394210220548456842648666366482586739267842185481786793105857596186334953016668577258273362382798796011314276043764688216837961186983303700132384261653358691653383012231953581760578669961098642784400802818301268910379768179535959789701948823244776603265375087410887054424342102814526538934607372156812916764520476404135876970094520716164535380020438823396323238925729554332633581740003158678895205092770546297685299537708331016709756422359402344645816800892479945908431662613736557057457479046216105005167382917266662750272956730726679673108524608797304190661721578692131933655470300127442657941527341091137394820888455684959755871245398001984742607501216598360515380412635216359818852681744878393558046132548884153493539667289778049649475788972857418798096361886550983405324211133538123781897791515946264988597912689955472580935861998814431746978336609462237788579783901902708230229694289787377971945419940969008038758236558322435310872564137055829139488614568346481557917648728141772413174469584128147385857166913691272608827844318905525746965221214959520045134785377177374502066054216644838680123108146065384229587271375412322565368932579102477213196634285558056747079524261437555578084668377143232749482042839596355026302005903385182597910057965848141802674966084927879815760192866574552111708067785910093815648993759316757828475984955745590471506132753849570282509846186582999581366940279837944153276870600770906211744983406552359400936616048987887144717000145079817459044885743413704834713619078192064358845103612827091949944874983448623387196271669907118895558089356739335325421883403856632800103587264226582913999628660375648794461927367884074012938271539172406747744347103025090734388255830814060748791416057584828975124159551489143982907771234578754999554976061909785053362370809882277070645123528711254139413241677541647978414971130286136449181953738143363085146510049841385135051234280167387035776097483553090920294390625198284158638714784815095625570597632377771987087329906960840468704750122930424057294774698930594899512781758355006638593422288433815551243235328897215378406612525416015965209120080756668269108574118048519621909511678227973309308323685039086182877233443149271239828849756901283787713161124434132073259906418118530875271976607728437200392897122599030325407661051388534657212775269654706595813802693508320584198415984183103137911542954121614160114851391931316448014548776301741846887762116898887190481473977540318899658201049088229689066162564036140060684725359886087328364428894317085484190824901288707852181457540827913688486562928654608525906529629202129133871502006201977799477957399649230016295368142185627970485110486707128943621586692200537173353848176218220498519690966009070301568547751070475966647015963261933828159024496036832445831999706865333522602568408294959844093732408817425661730704539998169737822732768965578419366562780233708869225079150089412406128991183992073399978077533726886130825658820875157509499635011660525729300603181430456848728310016006880663644521917617777608425486989841938419357442056870941752739389804116460734689898664226791511306906356496820578526644702159309345176153073196958647765805455786796653150021839661539575934247510169697451412905425675906458736543617854702487407691502727043557881427683308042925714508097999110957206740752091320078369322932695123967872546945647272984403391331848733258080982649369451483165169297837382270684949579268031821477328009932392233117102444728550925441228122428488687417357185489459250667173642022917334702229275464684275069505745878202872820505906555961914945506449712955560313209632577480950491689339881990316859451729104000365420025013942188628235613331199231917620189219654997768599453839584105818734670909308535820456862590044568628578990727005632575280652207962209037430564123074833264066511114432466406192843144388304133835784636665175302303517495640833806068353624552273858354827025656593329227442854658058342986490226857614157067002456058545671578536627378800491451044114505228124822758629811025116368069632590828997500068266294652548354714692467681409010070333934618508304902648101640087483860689215946803675982178089613764822449181059734705063037910871098644195177657516309869805975815640673508260844468165304666248108731690273802325580697815615988795161686817700567153834930958358758711414377635039651697841430644314723280432520075739081875741371849793111771221519228028198141209201586204025798541271855068400793412351553149276863541467941400587117085647137964500611160697700841194059295902815828094355798249993079350689091854206641674884912621976056116662479868379162472331757545129540174814574372475059885735454116824781568461213474076034154305364599275581737494035197489193653076470252648708520722702195926882833605302726541427464108302685320049027609135159108722676823367698233627171070748209591837778609166779491117527629961085943949330239761919012367722025110442876197965393053065477107337927326244721320165791042498964975598535612390873471101473467733382981919856711284343982202481821953156359102983135669394515792573668194937589485575684759172473780035005247869379449991387300529943476627165802265918031544691633327469202515927456720708827528145398430502171979562196963813371842615749460915321581723144799887851170430173865024892383844329963834465991302850787650483907117268320594081761426877522905224221681341945315581926138834932525094151865542623386376672215609369149858439999373993712844701603799853758026291267135766322755347591091637862306297092907871168029947325541672541746684555474555607422385458386730278175233258653396553771367413037440897463060388705815019086239604668530611550132846207621549825226132946883794245579999741489458543409201431749746301402687143063795644387479732072407610207040129267379917631917990398988268352622336465649339327138797678438645619782536735306001084937430791280435647686397055390200107519481933758752763217074602872232441341965227694331008789224543313354220314223370984651564560313846487572843935838690665957778822118630508843589064408389157033473643291241916477491535035599854672469518163077344612547127450139642092614149952658127070665720470617426634510608898751993413992167460136648156904061072775964376696934015146680867557416648379090482428609878536783367189606982698405540119041139891298859432243065835774392858892080428325911671279037273462980615895311476437739128077535348029454932736336617675145319642763248558740998132918426174848303381470944251621950649758816703738171530091110149363190755768265746400957826738483738330783315970068445284935788145550908978599571587774054139146379372824955094742849418598384064615820820231297610568717228502147763018552548565434833221298699876532887055682321195630125564867536968286687005865090240855599804598502669025189507201317154231278743598941984171077154319818229812174264144914922121444617530926574366434548479658277392319930789720906781353979893639313273024904894968150794105561285194319310539077667925141412936140305058887661276664430554715321901403613104885127791849384961548877168936515042131488655045404987184000151196784241100808540530026385200477984585952370647745407443486029693212682408939708790220024661499762437543529925992123365824230910466643061410662109181648014574364325867654616291188341550276853560604444019563392784837878843618266745609952198638179608031049910221330240824243249565467131857790242501183944013004651421091925477419727221771895786246794077841867047279639168063446446350316195692656126701861493292579615982986861870534558945043878320237368992927568338561756017977688237302921512303291421443340484990688883062684685234226156782559802437431749000878570384676099496119566334881417920656933015520071379877738388775971932806840776080326441672401721650610204453814452772798052284915473725025914422562952034428090724848304837999941009498191950276541823821417182731568459772599681044367878260890076071099537189433530339856089652763925746738808514282701941366092984560926608044411796454888437654996179639144319162493973567313504355934970936638081789314314205181949974383771418598440558512914520255817259861681056322723552558966794428552703244128305348890325513153885620432195148716325870623937215029214849759074508871308157260520879891574777067606961321668218069659447955104043392607441242903820270557643555883299834916377494293730813433245570109588106535734576556232768791110113823134600585483980780459654123328993588699145360992235949148573592395643137201870891285537559659954956709183693214729414060963861253938507436687802183054653350904119857489159511068354193275254513229547995140461761373627617247160297068461157715249036335481255627849856624532021298165668910824931386855920658997507161728292097136322942313033910920388513255578440661337447549690256381511832378361539194720095701016190565232206995680713845813264363187832191980731927622920736127452764661878606618125595394502583084781357436080492404537963922945243150028990128324830056545539170360525074865684442638681379783520527505919020718597135825092165943917333374394725387253854880356847888280377644329616056390836863277751112167365349932163475357258648306377301342374342118837528549668421191027852804952475537519496693176593124482838955431298050588152886943785245128841982065070035040235018833212526994741952042175296922738003375750072679119143546313658496176268405160419839121347465777518099277798891702418531748478578426803468797590183077837749306984450268395356907299887170174621968514823134585082830269088570322796158033683976527798405736476649003214423178658193378475741802789258605697446881532305367639263118356482122869620869074532308076559621551434069320427781873824049562149511422369709575996469384359382861370825699733652840501283064240389981295128679496518401950589579628776869173938705017090417904394766608897158885309782420841541106338938248500382732907126047047165845488889928502508958893597510149185335876119296343554053411066307970238188402893675134764532670743551290473238843737035906513407035891211753377411532897856890833583474576229168567714348411781831839424858338202571007050994478371368342773673225756636316436626326744001396102838703719526924700017893743146416732695465484144592738232687549937514753930209470220816353859693847086953428159527052786601408700149083558149739096713204532083648287387184211590439302807331748500750336187148126584994879734484382083281527507376051919723754352511492030781935919078906634017853510347037571906429093959987228110554036362917528823907538534755303702049924533322727516674080746095680240794306424742632862054134006648763158419040134736640796634162781085910210528061215521853021005012022172990619808061071255622800878728396814997512184716260885438880814811517078319127033136904111105176886098514009391020287745748675379306945782326109173344081417594226824333249913299168669030835304008552478138035664483359749810794203603630365797230567308141571907639010018210726339824655744700080920591755109143053365456906221747965729070987276157063455761267268718068428216334630080289472567411642054800444257925205108153567003204202366453864212799288802396203256745914510021858484066594949273491548826403489952349722095079744905865061593784013311981531908756636143665659212989915495178059558008403309797117766236990458597337762626478294550397960108886751218795186533227637938511948291962232246504415450857869060343332015842882499732819785911111500160447178075321472769578445221638828278987887254867105102089272148293177867213098901146804904881353106669453634046434286002902161101766965457496482527655634586012398914453234887815153807352485767347468368375133415470620262498738748333283924271335375844404710410368610051706478206989864633726325795469089920989831579360828363961986926808552451331946574258039851408663409925971957035188265169799240966952479472590933042862246428116017996492701044096065422156019895442757829289704718660390427270921707834289566324916673876211734160564659319850658400402502100124323312714416215387697543988783907370990491392725203906061867829220055639352751879074572445804696902638609097636438075182625225121981911782588771605635002295627668556305231520432259743207189421695996789799432969530048274153948028197887813378425276356065023490311245290053995499212953976483645741282767837655686673777538011093085243669514697409194643625330815725209283100601150088745330292409526679286892815555327465000979869973103074672424222803633327059263345829584079966356988983800982397335007545495060315952873605424122161704425985021515088062071615698942658644923280413783556545222280433764032182040141451011786955135575306250415527557230300005606637158545845058204342020175801048693280475147333713571805298596558917317917006294073042026558959444881556502746929778174507086097933052803286408851330280858352679084929107514044501459582763110745793482570440143699371823633831765556212599458395645352137436675998812666214881229600063597736968368101677089710781940235051932767573453046746498496985857019960131767039558568542978473059069631601766172944293009785892130568470476442621366069367042323742966993875142781543241332849744088377964673003559420798422850712974466440571910550933547882046991457692714211038544154544300185804078752325144304545637607141415225953330006278994732108342853969366873006735694342566375536792001861013794331401648078098980621894530512757640730079399023425986019126613202750526483579985806274351286185043418080644928254601073303435377620818063019430154686631329979238742782899040953669886610652082792141088130326476123588015124444890519782897835306450480900656492831563499251344007701743182612085672365495508866129829804782444719191898462754517753269777203043928235609191565272434964170157922057888655434194561264411750045998601030552386900629951283269755893940525061526269106843294554268332880758914091362231975425513465017113267088150449808078068988138891983032207639250423018184264349108739737101250516619275279310764621177919204923976746818852745855022970137563686912758793702416167317018437603681892020532586835468755845620601431345298406209404142841149834472745176483810892665273556926054338680241890035239562103423841048368128543470250021865429116967448278224695957474234382103136777910360015203925386883154786752235104787967719136097285227009852810388490217975382548033895443125640742244262845367039949885361939451751072812238519568055488858603839477183518522094524705190225162887420257097362488114807191189399044444644726432175165708079037174397359033107584907142141362536614924198327559759672689301268089730181728642857950125280856854849434885588986360818811952797906220226984338999728811887433714394186858520240232856102716030093196285355394210758803767221678801815324581231676319313650651510409777588424765521318083108195658975335089093202882368839723703951729040013380761544578315686430973110041355505431860263611763642521514602726080744349308684997451360819646405071980259825634591149464897549518262647519195640142338664285897584931310044303490334926470427939644469956073662500066716873248641543831479677835574706335877875289781768908017493153282259177636946965840922290707205178363253465569326201441768121971562617493965446801035838560898334231713377316159500713243067897549101708455015647758180206713899432186259942536800665980942236589631880251918470817923953911184671619168997338276177547920716469923287828745744414048577553306135665673337951267802325597448357432913771171405018247204023332030933933609208365154315998127888240573217930812549075584186467451712209812218443279871077805338460750209181604334099466538532234320154661322172961397573471901885789606759817891539638942062997010207666429317550050780088038150988911615945495791090347776809453090577007690308866062501168826883462932316915577549281913480611679763047933675522080723554084612450490982451353462150496784930226107941299554902008327177878805995161061840140537844103960547372052985506860253376826128362179319927808909635791187936011589737953325533016388308190640492140099412428870921850192005074070159919867195759817210515047657257090602140367863506486287623852029585132183664444199088754571602685882445340222995885290241409061248819979467029304067511744995700508239571976882206166989265205843615207708122555384270915641877733322966218531416869450479974861771181210185396820415310156295971089257660486555883612136022417156758270649418545615425539443347610603870822625458021012969890461911594201055707757131837312848909284449496511804254365368875581271734497746011243426433952484349070288722537236768972139128821752796631650972704083476246321130454403052365620867525829478989506653976360001308063793528708125114708908943318282657091410639702217197588232360267908366012967490150985196519026171834111403195047236254297485137630233211690034127278667645650417847896052506563876136230929113032949544656998829722985515950724556649922121290194706081702580459649503410602498192499323471855007929155794408673770895166076798687936206201318400882656559469484465923369646664277867640172286117103801709537770011985202701088568095970232903667687793884126359380578360848874593482131293085566856593625501855534204586107975555489603032856843451120171173201550568212984518005591784763620433922076978848898925004840139356406365356424722118185513598202965330446702047999070573753310168814350079467519484217657926025108334669728396166585168898945000981592039932471064522248020792372233305295380787020130116363982216907360868953555703826132311392989095305274327516958486473357031504602739573315778751197146587354356490691520723010926681977537268639606261968345534799120169740411058747421257513640124400358930553745948384084392499751707388633165648606617939007835281233230711795703024034345501300921439830842344595209145404793397387008997203764087129710076509051306808246260874908525673530557471682972107362005917975832145393755153735655474861877630825561478064187752086705289977810928340843359945393964987775062505398479166337804919179499783172479319346793500233989241423934687937700720134851285576929949497073784901063040322932991801741301312106362432458181385646230231540102337842579165322231025356149764130317084519851186378105192376694354200555229013440968341671956924045109150563627885872832770477064948623969225145314461037326005531491977314460604804151597928160027262760898871164741852152886454487865868959037891697173668785362233119809620580886758678990538333922781860414288924083455232230410824069275118058987389672080443874393167264806454474637017051975208972522930260085571059107202745084833584295431605203569783210931111134065513776296722532625827468615761228135816465124554286762343655495001482386191492810991198424358198606792188251864217612369942431069141802220366175177574982990092617023539185800941257783429555646585039437725192586944953722592479606795209192529138839821307162055493148071151690915896304290597371951073178260417026513398603268432159706369844056690303045820268605819171858224081370121627999265382376326051640850220434488185509504703349016859455183728726906940022330186363561152968959628723435042292283492653935519971488806166261860413590098821090344645561536501851805336627475805783663412358577240653406326368103781135861169505699492335930901426069238406487463594956357540708447611680059269529058464152789473022350676939244880902580621983514174950602530604275369942853001837903093031400960520604684909454891319230034223534558336730877962425656619775827202729499857732158552303284564004543739910550421151875259742113479363992845409165657373324581743516251747811922022160284430296255799382115275714819166400947828810821558314071196740007529496888084514088230395893678151042763987547934467977585329655680001482438520897114003200674375899776879547363600897617852210784704259372297829575397628957364413944045904087952104829502631332813089317435764504535532437184267693591389995280930497701347256057931813123619595480749870068608426686067925972399767463217209103533183880820451412429853178918901254208976260701749432110048979980111515395515934675466860107648944965467510233143377826341344521470645327004705424847193195144661869228832928236752947592029783304452428232705019976764709142188435985798734230135012286267872528108392928066891738461481591929588030342766375934370884609703804383639722590491080652629794900152208168700621723076775253862650375998610595578012776932264178781987843712116113148707697137287466307515393953357294316239296141640579732724658880302631202973121547337879984810834184282755844490603783851877618469041922279647062043083135764870450865078927282449792665907129532399933284905716589567895014358387790501688416110537788720704986044157398497473135843096931787492539837586977290228412307695818366612542870858107545778832070954592427593252834377935627921516172019938787070538920853939995660116409954815079147377588910607503899236402109203364027644141267742302051855471100001.01714067292 
Posted 4 months ago

According to Wikipedia, improper integrals like that of the MKB constant can be transformed into proper ones by .

So we have the following.

   g[x_] = x^(1/x); Timing[
MKB = NIntegrate[Exp[I Pi t] (g[t]), {t, 1, Infinity},
WorkingPrecision -> 100]
- I/Pi];

Timing[
MKB - (-I NIntegrate[(g[(1 + t I)])/( Exp[Pi t]), {t, 0, Infinity},
WorkingPrecision -> 51] - I/Pi)]


{0.078125, 0.10^-52 - 2.10^-51 I}

    u := (t/(1 - t));Timing[
MKB - (-I NIntegrate[(g[(1 + u I)])/( Exp[Pi u] (1 - t)^2), {t, 0,
1}, WorkingPrecision -> 51] - I/Pi)]


{0.140625, 0.10^-52 - 2.10^-51 I}

Here is what the region of the proper integral's function looks like.

g[x_]=x^(1/x);u:=(t/(1-t));Plot[{Re[-I(g[(1+u I)])/( Exp[Pi u](1-t)^2)-I/Pi],Im[-I(g[(1+u I)])/( Exp[Pi u](1-t)^2)-I/Pi]},{t,0,1},TicksStyle->Directive[FontSize->6],Ticks->{0,1/4,1/2,3/4,1},PlotLabels->"Expressions",PlotStyle->{Red,Blue},PlotRange->{-2,.3}]


In[24]:= N[{Re[MKB],Im[MKB]}]

Out[24]= {0.070776,-0.684}


This gives some improvement on timings, as shown below.

Timing[MKB = (-I NIntegrate[(g[(1 + t I)])/( Exp[Pi t]), {t, 0,
Infinity}, WorkingPrecision -> 1000, MaxRecursion -> 11] -
I/Pi)][[1]]


82.296875

u := (t/(1 - t)); Timing[
MKB - (-I NIntegrate[(g[(1 + u I)])/( Exp[Pi u] (1 - t)^2), {t, 0,
1}, WorkingPrecision -> 1250, Method -> "DoubleExponential"] -
I/Pi)]


{8.046875, 0.10^-1001 + 0.10^-1001 I}

I will follow up on this soon.

## EDIT

The following notebook was completed in V 12.1 to show the precise differences in the computed integrals. V12.2 doesn't show that detail.

I tried to make sure Mathematica did not use the same formula for any of the last 3 integrals, so that any 2 of them combined may be sufficient to prove the accuracy of a calculation of the MKB constant digits.

MaxRecursion guide

     max digits M.R.

1309  default
2410      10
4453      11
8275      12
15442     13
28932     14
54286          15
102600          16
193914          17


I am presently computing 200,000 digits from the following 2 different codes from the cyan (light blue)-colored methods mentioned above. They should agree to, and prove to be accurate 193,914 digits.

g[x_] = x^(1/x); t = (Timing[
test = -(I NIntegrate[(g[(1 + t I)]) (Exp[-Pi t]), {t, 0,
Infinity}, WorkingPrecision -> 200000,
Method -> "Trapezoidal", MaxRecursion -> 17] +
I/Pi)])[[1]]; Print["Timing for calculation=", t]


and

g[x_] = x^(1/x); u := (t/(1 - t)); Timing[
MKB1 = (-I Quiet[
NIntegrate[(g[(1 + u I)])/(Exp[Pi u] (1 - t)^2), {t, 0, 1},
WorkingPrecision -> 200000, Method -> "DoubleExponential",
MaxRecursion -> 17]] - I/Pi)]

Posted 4 months ago
 Although the MKB constant is slow to converge, I did discover the following fast integral formula for it.
Posted 4 months ago
Posted 4 months ago
 Since the MKB constant comes from an oscillating integral, I thought about naming the convergent M2.
Posted 3 months ago
 Wolfram Notebook updated with the new version of the miraculous algorithm on 6/16/2021.Here is the improvement we get from using i f(i t) as an integrand from 0 to infinity vs the Exp[I Pi t] g[t].test3 is M1. M1 +2i/pi = M2 (the result from method 2). This is a great proof of the accuracy of those digits!All worked out at https://www.wolframcloud.com/obj/bmmmburns/Published/MKB%20fI.nbThat includes a check of 100K digits, its time computed by the new version of the miraculous algorithm. See "I computed and confirmed 100,000 digits of the MKB constant" above for where the 100K digits were first computed and confirmed the first time.
Posted 3 months ago
Posted 3 months ago
Posted 3 months ago
 Here is a summary of my speed records.First a full quote from a message summarizing the Burns-Mathar method I derived from the work in this paper. I made a quicker program for calculating the digits of the MKB constant (also called M1, I{2N} or MKB) in V12.1.0 Module[{\$MaxExtraPrecision = 200, sinplus1, cosplus1, middle, end, a, b, c, d, g, h}, prec = 5000; f[x_] = x^(1/x); Print[DateString[]]; Print[T0 = SessionTime[]]; d = Ceiling[0.264086 + 0.00143657 prec]; h[n_] := Sum[StirlingS1[n, k]* Sum[(-j)^(k - j)*Binomial[k, j], {j, 0, k}], {k, 1, n}]; h[0] = 1; g = 2 I/Pi - Sum[-I^(n + 1) h[n]/Pi^(n + 1), {n, 1, d}]; sinplus1 := Module[{}, NIntegrate[ Simplify[Sin[Pi*x]*D[f[x], {x, d + 1}]], {x, 1, Infinity}, WorkingPrecision -> prec*(105/100), PrecisionGoal -> prec*(105/100)]]; cosplus1 := Module[{}, NIntegrate[ Simplify[Cos[Pi*x]*D[f[x], {x, d + 1}]], {x, 1, Infinity}, WorkingPrecision -> prec*(105/100), PrecisionGoal -> prec*(105/100)]]; middle := Module[{}, Print[SessionTime[] - T0, " seconds"]]; end := Module[{}, Print[SessionTime[] - T0, " seconds"]; Print[N[Sqrt[a^2 - b^2], prec]]; Print[DateString[]]]; If[Mod[d, 4] == 0, Print[N[a = -Re[g] - (1/Pi)^(d + 1)*sinplus1, prec]]; middle; Print[N[b = -I (Im[g] - (1/Pi)^(d + 1)*cosplus1), prec]]; end]; If[Mod[d, 4] == 1, Print[N[a = -Re[g] - (1/Pi)^(d + 1)*cosplus1, prec]]; middle; Print[N[b = -I (Im[g] + (1/Pi)^(d + 1)*sinplus1), prec]]; end]; If[Mod[d, 4] == 2, Print[N[a = -Re[g] + (1/Pi)^(d + 1)*sinplus1, prec]]; middle; Print[N[b = -I (Im[g] + (1/Pi)^(d + 1)*cosplus1), prec]]; end]; If[Mod[d, 4] == 3, Print[N[a = -Re[g] + (1/Pi)^(d + 1)*cosplus1, prec]]; middle; Print[N[b = -I (Im[g] - (1/Pi)^(d + 1)*sinplus1), prec]]; end];] Whether it will allow me to calculate more digits is a question that will be answered in a week or two.Here is a comparison of timings on similar computers.  digits seconds (Impoved code) V 10.1.2 V10.3 v11.3 V12.0 V12.1 2000 437 256 67 67 58 3000 889 794 217 211 186 4000 1633 514 492 447 5000 2858 1005 925 854 10000 17678 8327 7748 7470 20000 121431 71000 66177 30000 411848 ? 229560 Seethe following cloud notebook for the results from my improved code. https://www.wolframcloud.com/obj/bmmmburns/Published/2nd%2040k%20mkb%20prep.nb Then there are my recent programs from the Abel-Plana formula on V12.0 that computes M2 which is (the MKB constant also called M1, I{2N} or MKB)+C, specifically,  Method ( A, B or C) in seconds digits A B C 2000 -> 23 -> 20 -> 18 3000 -> 96 -> 80 -> 36 4000 -> 165 -> 141 -> 64 5000 -> 442 -> 418 -> 386 6000 -> 623 -> 591 -> 544 10000 -> 3250 -> 3070 -> 2800 40000 -> 175, 551 -> 164, 005 -> 148,817 (So, for example, my 10,000 digit computations went from 17,678 seconds to 2,800 seconds.)II predicted the 40000 digit run in method C would finish in (164005/1.09=150463) seconds, about 2 days. It took only 148817 seconds. Here is the work and results with a check against 100,000 computed digits from Method A: In[32]:= N[(Timing[ M2 = Quiet[(NIntegrate[(Exp[Log[t]/t - Pi t/I]), {t, 1, Infinity I}, WorkingPrecision -> 40000, Method -> "Trapezoidal", MaxRecursion -> 15] + I/Pi)]]), 20] Out[32]= {148817., 0.070776039311528803540 - 0.047380617070350786107 I} In[33]:= M2100k - M2 Out[33]= 0.*10^-40001 + 0.*10^-40001 I On 9.22.2021 I improved my timing for a 40,000 digit computation of M2 of the MKB constant using Method C by 1/2 an hour: In[20]:= N[(Timing[(NIntegrate[(Exp[Log[t]/t - Pi t/I]), {t, 1, Infinity I}, WorkingPrecision -> 40000, Method -> "Trapezoidal", MaxRecursion -> 15] + I/Pi)])] Out[20]= {147079., 0.070776 - 0.0473806 I} 200,000 digits of M2 are being computed using the MRB constant supercomputer in Methods A, B, and C.Method A  g[x_] = x^(1/x); t = (Timing[ test3 = -(I NIntegrate[(g[(1 + t I)])/(Exp[Pi t]), {t, 0, Infinity}, WorkingPrecision -> 40000, Method -> "Trapezoidal", MaxRecursion -> 15] + I/Pi)])[[1]]; Method B : f[x_] = E^(I \[Pi] x) (1 - (1 + x)^(1/(1 + x))); Timing[NIntegrate[I (f[I t]), {t, 0, Infinity}, WorkingPrecision -> 40000, Method -> "Trapezoidal", MaxRecursion -> 15]] Method C : N[(Timing[(NIntegrate[(Exp[Log[t]/t - Pi t/I]), {t, 1, Infinity I}, WorkingPrecision -> 40000, Method -> "Trapezoidal", MaxRecursion -> 15] + I/Pi)])] Where the MaxRecursion (M.R.) was no less than shown in this table. Some of the AbelPlana records are shown here.
Posted 2 months ago
 The following subtle changes transform M2 to M1.
Posted 2 months ago
 we look at formulas previously used for the MKB constant.
 I finally computed 200,000 digits of the MKB constant (0.070776 - 0.684 I...) Started ‎Saturday, ‎May ‎15, ‎2021, ‏‎10 : 54 : 17 AM, and finished 9:23:50 am EDT | Friday, August 20, 2021, for a total of 8.37539*10^6 seconds or 96 days 22 hours 29 minutes 50 seconds.The full computation, verification to 100,000 digits, and hyperlinks to various digits are found below at 200k MKB A.nb. The code was g[x_] = x^(1/x); u := (t/(1 - t)); Timing[ MKB1 = (-I Quiet[ NIntegrate[(g[(1 + u I)])/(Exp[Pi u] (1 - t)^2), {t, 0, 1}, WorkingPrecision -> 200000, Method -> "DoubleExponential", MaxRecursion -> 17]] - I/Pi)] `I have 2 other codes running to verify all 200,000 digits. Attachments: