Message Boards Message Boards

GROUPS:

How to calculate the digits of the MKB constant

Posted 3 years ago
104992 Views
|
30 Replies
|
19 Total Likes
|
Attachments:
30 Replies

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:

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:35

65.6633081

Here are the results from the task manager:

enter image description here

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!

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??

Shutterstock has found the MKB constant, I(2N), at least 2 times! enter image description here enter image description here

enter image description here

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."

I made a quicker program for calculating the digits of the MKB constant in V12.1.0 enter image description here

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

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

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:

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=hypothesis Which is the same as

enter image description here because Changing the upper limit to 2N + 1 increases MI by 2i/π.

by Ariel Gershon.

Iimofg->1

Cauchy's Integral Theorem

Lim surface h gamma r=0

Lim surface h beta r=0

limit to 2n-1

limit to 2n-

Plugging in equations [5] and [6] into equation [2] gives us:

leftright

Now take the limit as N→∞ and apply equations [3] and [4] : QED He went on to note that

enter image description here

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:

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

@Fereydoon Shekofte: All it takes to leave a legacy is to keep planting seeds! A million baby steps >a mile.

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),

enter image description here.

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

left=right

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: right

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:
...Print[Abs[test2]]

0.68765236892769436980931240936544016493963738490362254179507101010743366253478493706862729824049846818873192933433546612328628766540945756595772115802556504162846251439250971205896979865009525901957068131704725387265069668971286335322245474865156721299946377659227025219748069576089599393209602752002764192048986309527950738579344982825034173229565338091811015320879481813358258054988127280975209369016770287413569232922644964771090329726483682930417491673753430878118054062296678424687465624513174204900483221642766554290055935028993611478222342426128582832646718603650018931537414763848967936556912271439870651953065133056888465504885799873853516260611678863354038966005282223744908289479862039722833171519816024367657656383305723596359151086525460036387486837632622334298725709552463768300591035314935398573611886888420174824190626083498173034223703984133264282699210740455065589666674834536567489060715777444147548424388220133662816274116986724576330176058912438027319979840883059505891309117191987761469414772648989343657425085034050732738529903546587114217499635584514475429656959327732862489935076490012861232249244670423220090484477969004477448946670434279197103332581857937517719898657425832767700119265854957115794801143278185461993723493131802360791389248808154759564302727311223193005229640892474022665093207969297797972308795483218256171403916521459251943207234100609086755844459050004667079633465456383179509789357941736916352744611848521664077918386624294040883487647062354653558109265769644276994369741555722263494599492834558291937955573706480722982389806312472239746286527176248883116124285469947303667188075506826507811479428582807366599407544908560990699866167233307144245764835741501174979679166078765231145175411199825822532170091858833628202128777966026600647843068442894310401343003939117236867245656732686719139206716028255819141802331701942027248337771633882445225049334329008827371320849006472846226868011129149192754883153995560921671208059671732704499253517327447529208297180672654123457301218758892278525894167935930983363218877512533994251978272092700003994136520699813263053327399132641690231179063314931546906927612775633995348209911166678724589467821767106592498663827057034363632241807121831546175498178011687284590439293322231263406301066863589072717290630291441982684113819198880100231182613587798104863611185433976009254862585527222843445901958943153561148829083242874018226480554274231391324767376148485531787767908124831873688579979114662856184612164534836370699371440464263768724668291617743681719766849740663590277737977490693183461320266666793472116774276618408124767965369796362732668987556797338128876129264558867657737417548617146808592137056879602982206609613881069490166381528825180204703315896719667069923077454352649723496033985893188309150391579573916059639453655188856334980355047281560296288150836680499821806918067869468571687709518088408966653716009356556714281694904914038988996962213833530636987279769672200413448893419914190954063100962251649102614676944333201213024711868954772741991675045198246947499574872027800654821823797116399297131866662866832215332914761325880983081211272181775518951539503852063119472301382766303820851467743266039356123495461914463960644386394228342211998370152351720235034997434035743513051754761571835043769475528640144621307760159481496713401409374957729200400650100318226988524015127382509490642900236553851499823658269458873976032051355393161653806016080446394196719312454167915154602448638624354575153334932298393406734174580316934939632892851077461038399470015366439910136971186909599331204517462262508377673477745789645309425145559198802530351403897927622891172233239135167420567162398873965477371498335087310395422796362380227536212159184529243644094285328763286873653399867593200891823468738537356817916009007206857590792983184556882143118383332812491747733056313117179696094921120670802012310012864110800437831852620698327457619035904268498030693438632685623213366864129523404256345542376567721287706234359125016588483777876970236084456277023948551334490591022594253744077631232660869593809453087749830900393202787736482133628148979992109544954840067942735030391105496026321872468122542495017023785810605820545392820104069279893067324597299043883381251767370331206913429284614563732308018369972360638019778425246546329838131639355043236388708044857300408692365733932897876809202025693305332974091411983635619038514442263783801745983300121464879550146672827072002317686396598587702487509572349422593441184802476344187280014450860069307120621758277552124841158659386176036703247124389223327008210072318671884895179305778728051888524412158486781863155034447221379906386062559915129172725833420555901857729690605950941678587057025641848365090809750870051863842805803189784976076099574956436664131457150096711473033060684065060747340764998195621425524824611657787212347497307297184843276100338110267863618974154272345482369968216663233417338501929114697679974461999040589290327155974468089706302454776026817180862666499129628174265577539296103535807674203952782073115928317544891317654708215972145012823941980744128048658597163977280396427316169647475303595080927471754288841833046841458422387717974567843044763850418125206354901611986735632986299742416514404459056979593895488162233943652678347265596022282622385942587919265881732538688040421277515535793758126602211811071215627680419344432516747402019492482943196302886074832961592788991057409669743325758307333163136246632364563780912463029611662201334616642363164539543840181301469207548893290144196646698764959753342322814145996984815900737499281211342548428906112295670587794396336773199294694685408180899135324672973165645117794165164625772251499013197507709128473895643620535221191614787415169032580462466771890125789345521268697933221974072228257137688062748923747463128426891753656977603806187577539562171586625808503292996097826167833312793361094258099626951418568585518961687635101836804717331526833821482927759113475972330852882944833032257951185249657808449783975928144212629465555401121770667943354738182016599177879322535318669382299981500007793969274837166785629080488761222197549875004161208801954470862728371878889690961127008128988556968897951226589322413393621290922169712215501662328885746858351091854067612190960814788538340562578207940194447820374758964049453475279596594755697761023231503354696608266140588427725279132408041823760459504872832001577406637490493472266614047453860870065686792877317240215300245115939170990462859843807650049824300175195709172965197327078675562310841032518575712484118847367779336861724033437212821275432183094312917793867315784551027523227005327157648039488363953701623965995604711695004856773762203158723953554272766853309916267341275797701903330320042991780321928042752204238907746197436551707656232310297198950878091594928897182512416873896222378187499552752921976712473276842502760152461333888138362604443683396629339896297650204980597418549284339871113824834286671299816817387582638999915913286638728595546135935343327723455065683745940557931894237331753292045470410939999575537512585307075567794220591384663498770172627012864400543194750780056992232117453578320389209867758387153664474345216548748209284915679039103002974533659770931659846870364413634670648588160193106843188106278338484810906518566594643137582510141675299253740013452703717539783595916347808069303890053016731820356545553334308669988238215584797234857833240715337734964890963336352895209158472114451967789258561642243848301230761365174350759810624743918027836785194432612734564175386521406785552306982060855661420857844642892457821845981654717418043312915755155342902248185663052387501034934749414043850316243443995738735101173469076174529743228171316148424511561503236188112034773319311513132912842798170621472827047672512662660852021680873128806212250221980163516049343951492036827192365458624007962426554417906076621642340008264494604009400963618761963743233336699723230804728616304144337784023198465901333727384408963746178911895846410600416997576086543137329171944692055426801269582117623218593830183301386966850121271664831399119275066306084081037583165170944565900194591454705621425288086806504167157399213665956221987887850729795078428235191733444077623156066353441806301809447237558386800763779726469019801516781767029953454355486904086668961133817439450715151128685255321775726892870440473744648135498995935054160338685663523581037884369223344060532035244549530978707961982715975634739572087881230153460402610891533080110973700091540678696985479648877093538694703949814678318178906344131546480237420675784498137760336800205498122230353675368010587675313178007613310409033915829070038954051402592682464313456575568059220870617974413434576207889586620127970628216302933626256098521411354887792001292183442992713495148114132503886863918215495594135709356606956839123128764710024555788150700996403565715489148120536193763080771965908774932176687575396177970047279872390682064853333317876735441961126812962435306711447931900024658102394948060723874376192992074534577072409014967177579881003203603844597465838672089245254647844940297347907582162840968570311034735702558885041591735458587806321821681468362558269818765491115492370357335209916816201371799888087838643560301629784058060474468807601318274763626318805269627924736976096596143438889750807217089885706589537704845033995010990501704030485978413906693471823056058978361765766540875857780152353408191351286387079162446133333449551836073470193445248355929280369763149422632438606998644721208347829355596847775887472079459339376004377441766456024133954622699343314552862743421422371195589467507811224974076666505100447335985294698743481536277956472985989379142059927665547319180436047661445150971635633321070664576769828503372420176381854082122911693446785358685649432354200798985200344829230769191651462987929262619681734042999411805817382627750320836574960607564939935193713317938773219968529378875643297709581094705710775087337340048430356133329809307844513305130536419451502785240472800606103546718110003429303529906499494710047912237804449249468874525861083507010580349374701040030853685622848919878449929399851433751531600860218882532874416607559293184652366518405285172427184628927098560354782726363212597594770953634441623223718002326825766680241421852081609630303146486257064001699198422370576720335824455462285774244510694123015266718544479682986587917276656888581776216242287865231580329129808038591901952458108582886799850458913868870897316226399785695207697594428075479862155444063290069933763160519758353807284083073393027087794549513007736792112216429208439255374096196594904127869096362714022294184973891594248800061126654310668508809992868539099319923967900644358223292981012168404390789699692226974532812736740726705001655775124973620097345182072524359145885905902176218784092650852667171197480014612236259464872765843116006356086890067690233029982695875207293003626204223274745661069509440757588454169313726480937365021254534348209980346959715427124799927823882402396681319310222085719304648072632850848476903201378748718641877578017549246728454975911731380323992109244157781903593878554206064360914649409887207646362198718570717717828555745157055499606109945049294448554426277452184000492947923939681133667684299336442600353596074034145457666334331793961275462039007627213995452036177297272181745363958253145746378713674914362798861912370616204547295605099498268925270142468175541885936455230391996304914004337777568355347422130367905347350273778348426228428661469096462827715531661223661982922965385873663654906808552645899234048209365933126670575275802344829577289518161114817548328708323260137171887381537431438495763162872013412530729081800855631613767906611199235441691313536959306225969842073218977525206805089010503086744773911802531262458736383818632981454415888931500276959485335571617401643867802454518073083747981689243228707691363505519248801525470729484403981839727724581325054279894580924153424034980721591117713459481711920188146374609735437708789726381086002375802532851460036051245029267075777395041069203162249819292562906665858423018853205286078794806182035956253492598017769414680713839600943488472976928157795083131569856681065970354607231916440790023121971921063643253016992146934353541385065323232732416348528363830204550297901450028349760279586033397868154314810686464782535307316558683744949764451407817579353350266047245126257588496377047460395161491865670240157744681698896845740056269336891214367946547516678622720499862708909236488801029242763320063716880338723047179151798172058591124245575791489778944441792552360399198799743162085797046492087284331547315234891707663583637345058339250844352208626075065211002042402852548997696224231894476584104305252983051191993222219055741828524094252377925581703037152893534072425401720375934887581730991828290325117506555789230837583134473210547294260194982981519860912595954338191835720992308863630223835283759255205519300777881534867285454592827828524635031096077880648051886971133695126113929662229558732819097600207625824039727287689715234382974010185765739372284191513142959236853288627452308543337638644049025803544103510682270633218110911954688572494588187241971009790086275999731836282822129696754560584484503250841012506831605558863012659137903462449958732525188618380900088050894054336066355791119374965827906274864842151882268850621297248101428312054900533583216944631861626122510082082948769552584815342128083661652190772424146024625009231163820015068672195579312189548651487591345437813757441652233825016579370483546749025026486091835624885580729107206394743120989443742596397946986532657361050227492526944826103918996197813637871176060238382090946566765838399045073749749808967900477565685204163145349767202254049653445701731797224580931130144436315966907705090169035658090259875036956158416441744243312411242984767762396522602585962208859553456575846443674057782808449981261908954983951241759741750720901581884722817504304011957451395096673818414859842065409004696774034910989296144854435347841078251745452006945321505252144488702316190501513830181678900460652350667910123747817179595199448298133111092763397754128341727910605738631687254741174818938185397265747241023428269259507279848899947471545624758647042443827788368058218482353059553351031334052948678233923611265188514815847760674821423091793105863195928814686758055252218891239899987291845992009434816751078729384625585946379213282556349209111784765585513963392672067482816675816148726191451616109993128144202270947196734756325239342116398042218762971400666788022254343916772222497456368099921005746495321202188903803577906352435030955031135860519210000096429393851172745952195233923392705678930770254703614031284247755908869936042351444220330809526622875759687333022773524409808010139864309440742959573871139136757554471953331334210601691836581561512232181968283688303595304806580127957658352776138794312115393827933609169842487504264473663281726407649263108598740651157004974028306421874750795807471186826306536812676670443101928784277023495868312680188902657537598464346340680898309628212690416877722215220998384103431558545741696921375810425244068049779635269388838985483810164644660154215985355314002191072183826834150364933111897635872101794281442659843078223862815197818268234905934105962017289199664484509856851152571711407743981226634242648977077907262917821596746791845983552190964269137238998329643786140886276001669253224411999982885770258107926328516172422268014598700031525640631831572340465999499823727743735860504191303731231297014779022116064905047114454872899622206489234599826586396527361043001377631008159467400941115054484174699217894418780239782235806818592944425795290352264590391125194923239175238385530548831490448132830741094726510683902362032845415826839418541349555518567786339717924798835135652664955428874746390983648718792515819928101128208157392563232262477302633131761516279395410942166073603426625646415499325446544446176961777704332594383390271844444789452394799668165431710838354330928146992254682365088452351788869385112287843823181456202881903316831712389212335081399759274071661663025057239285027272228070621787850885932813064277648455682848679143821101541212039914926883137872136310878896636524959199119199008454870119285251327665130651804384549890620784844376185359563017846179599858006374105565180381545899481534624317844751723985534330767110164897570419074886204283713397206165732444080994456501139532278429062360406066245098853647796890817370541942635476410064790358844410286416698030928433393443054580812155686712547630165646471983057545681310486007294356970946010339692962083822345529536929479845583110101772761044789272882353702282977767784472475628083637285522211238302142258716171304832579616714576380730275750067721360930755024802985873288300996710306520012511247802663572953971030972621318440452569211754191449481858237939682684775978773612872283397528785556552026763179520536873281806921512691801956916739368499585097787793159558139907584066804051267302837205345820515916808381901347404194035790805655469266915458717746760246854670953322534003601061798894466292078923638808668463036694428322306765668083083183463695527905277826971584195281646637970491206359844892839142719319905449908779532420976275606600086965953228027943911904574111556710003207866128541537659526534433644720693557924372174524949026681621804666748959849631509316177047697834230436553358221794117442883065683550707156175675900958216772854792043327249515884176885910684201895992959230102954603905617347080536152768741025234628356955007416935687697499284404674269273900903450394251007734020198396200321509486969046661167494719187483594388945660901502702635458854894487631762494507095783419963951421682396784816261669772185782256527319198823861631271305557334629034454498661142677846406912692925774443168093589891040662164382633796893056880442621829353879631634578976963235921629360829143359689543537972247913740705649199129434512215215740679036987749974182571013658531964646778847149349261417998963482352721226955643820019004829309013880764975124746345794436086485714626451648600805977150640117805901595518345893479654988936835717670724884318192070873487543894386331355482056111525441696426051948232631043671371143697862965228696298741392391196941449688983054241252609515308554575584427185978096863888750824693110432545402994807205717323133405172850752190459202667476109943422410241573373698022479735343657354319748496751385763073480580501733588812683059007773495903529327965043761106054451600132937952364382837086187036444722430119083247598455858244430762446542826629866996492834814026803773449440995522430483940980984726305696285237481914071204742568680609586863659745113750653550689592779518657849085240184574742028251559922510452901860043524041463658647037742238893434165809470292570456284996915545999444251193381030290141746210081563107140516323538818377824184714603638972113832527634992708938190408049158080822024750184714344683056026297143611368573505838395679122109456872973271435965970527537594370948339800488598801160936453029436583361154272047308679704361864035171592217830334405563754399107324217094822176589598259498008224368570514159771359032192945865791926395260564056102327277384954281031168496628995748840366862999475605310775537492410538380205195556395691185405441171726671783380888809158287984772020195607983462468072039597182004808135749286865005313456354446432738488570228974748117727243292966261660462321422971309083506870605186292992748767056948987766121194450203459009961336049593046347449948501671482126552774921617888757635937891504694776592125033239683524380751023399669802982256073198651740183433268427350019466368060803123948190531505371279763926080627174597753093877528734523928212855662080469535041635502505460927247305777379655740309932171381671180809455637032819530657126587782734561336866134042972429630063420853250083346092025567295835389383686792213298721828323324305898736220351086101097969171884600798761910714084349876267672453339734177791038756760710599326613122016645473079424620142392899457072138341287282078381624631678553561718212648954200520923044691758895240021822640923551509022529529610478774889661172127429646039557160397013489030723027673965599970182006545166692216319834148948911221110993150316618459891132532481386535767646150044592084755659960873845037937699767749257964447093943412785019048406187700597809521064646060033336704823778387198135312902363743784818590795892908091223818152822931358731684317076829480312231466239059679061983552925561573521123882109112017346689313359279340875176762340044748849628267318337526957942996149757833382531252555431309670317322685311543858261899657369846419700056910830440604363863014750358220202692828423048867253620566421984645769753729614654489431735986577510895760028157318581579485270642837299737647767883329695468785062957741897312437732055605172526075001080977750423281764412224932701205315588897913699205943463826509977121241701344489108947626882090923143622461165936467053054304515875565956471807711322045854384920524231562813392481375800843712043736637338981941845236287027383334967600303975092279045656624758799082664016662539594147341876657113272869159078132760283524980252417242999370106289782946386537464949173452231895020345097250984243182220472603445491714599155572506670626675211074238282050170763898079026238939628342685735490812491724705490340311090765668329360689027272806964505349790520466889319056171288731120852099897720580426057560337484066466315700107827033505530845720813459411427266351979577490192922928291545480377638447006274741059501405175007656406697308028372202204601204382150096304144605786956911178488102758773181739639967330494233255325788741410825522985462684649925103229098618464284430010962689530048140508490764439088989835709674121284126411735968182179608799850320992610335418306811332335326452646062954283649865894057578409157764605009877104819439169835225874969674811079731688354146167896594484892543332293141728201486340258281826592517332641643843487564161458444258240685920802473806412300683311533276739861915880812562538703669289333566962143062531354305456847886305168836394051793048982761585783420553757692243318865019774855310724877701102588748614270963965467761741669584923400189861006534169908116658099946248500888354997950655748799741000365568018336490989815165004297908921075477512832648827943586442967990684136067086954058999054841239979018223790302917631975285397592942053261422997983747116384686656909103115181431156277810254412332807215521521913210188561978585551220620946997905436181482382812509797216214534139208438729063119268815475532631127917290425824545171988550887423640063405982537561548346413628863712242681785132671375305935991688530429003042194031750271644151411389381149052294005267597471403423250867152542749149178912822512729286125408367351308934717944240465484641795577195920433614704395431215233445214762102456860712543439607752146117823152877496307615237782270474695837617786842614444502256482578789817600157917636415994030480609322477903642054612366150687314422954146713119505411836749588046889579113211539830476187121910605612646269383131868208217353909339102784200141724069027190113433066436228320221410158566131026128468165907807435758418013421625857870007622184208914367965234781568790433636034503103435020834332476616909057876728754387504102092210928047793333183472518566428884705653585926512737753482973727183786825183580572713767119346615964521796867596310010548840807546755303981587583030288557658949650958411903588823513924732485267115171111506676066918066904107719634258550982773530404220110548665697912977833960430447353845004909911303279635186313541411818532323341427386278365167776601690816802424616844372740452859673973150101216703623096083563234019786645793225501930118713004170268183349103077731107258049178697300463457985489189438393176018065479038550718474274887817575086539393810822899974631499816496110494244129486286210922826197936747790633981677436502922334909921445614737589944467848167246917428695872001088057181255744648122517999075266657602834478853565670186154923896767519659494562872470384117362888150364029965967321511631733219151646648038721317233633321508080712014541927562409331021768426387190218707456659284347808807427328083451956836427256899097276118727729790925851364721598920680287154381941836104009691057049672371739606582800181761067894097394277358064020448784606906923836673383948698745266794229963423994725524492217675161409118905627232013188685656338426552801768532063328165027051885093188228264581213805313044578658546746142243852544028170454888159624837598130368817059982907399338079131953092875599302534037534493538446263483767146866060174148713795386952822607632916357578542043442253219429428321099538927604269192415840408547434508997663277672854243638154809761320114310471289604552266693897846220052787006616578624182856501140506091084553193785629349394297414303270336850138097988709288401000509572835435809496098471644365567323643258614561643369697597132567632158175318778837999671839372662245543698057593976828959984773233415435110614484300466372399048661686410077202935179284386940136863785449704388572300309149553493702483507091956362919340041863581931097116556493047725365455421743723623570007674433424122803249367497470961195116987189325683916808680378708883441662736165417044104473249366832409588627850687122333658134431163599624702558433801653096051088813185446140313909241457065935556468688992589650037139142818929172947670247414701173860669311010164367989183440325298136820575396000750684019767501164956792925517084815922800484881296764085623512338960498369965940475587228294741535131222011942734064204644877235033588919207704169518665336768532484173073783248157233567136746885034351046815853017957423009438272560042717062540611876692207565973507375177436645114212562584030412691717763618931610915972872303802551516648509638755507146504171678990153900932138323259584691324322445651512868889718645845854388164244305149188431015701151567910391747870206148745784697894832268425395418290507249875083846910974279706146668262381271893604249107564438577643851780740049411472964527062771993809387145453729625634989160675428490483602156930327341961239646522249943283140221543286207711543096724544848002954721636060531469220607463863138212397172874931877752205494667857451044707701356863227259790759009883682127785381590223678669116303161095792175571797620387032290320827969308698824248183944550825525234471838006474449803075414157934930241062348165743261539702660017011157921274481937985448207055846387082788797329233667034437233471197917264835487601770320415362928717414496423549113211695455692909178360678857487735776875828418038006354319442489301195133382402231497874892332937811572131865154751076536650998917540437642691943319263124635961597537132136707633356404674604992885037449344401558103283725036326484360310981146909977131478778018348347425461213052091753907915953467976208479497457165458471124573544646802639042844079605669227590988506218742895372976506158292594238259046507024869794439465964078963822964111928435452669945156056559649097341129029114756096175758524132371882206398939992011706255622640709160311423308231188191305376323340076885028781525202829935553883558158160927610113578459651745964228335436910472042549949025258311538597970500375119838670104101627072163197857384697950759182475740450631450214106612170997288962680046377621239356227730467426373820281261258062395954974691931505187417228257911086265171913509432414236012383216066448666187211182574810016537068570808818413791299504100898959209291430086065124527569894865612838041952626464158034586747985578176132748033861274112722784597871257467779804995963453291442050044388405899266606138172914594468742554758849503663637741453115296819390421337598751891903336256678653101951702771774394473609978908439554436010714936019989268915387978241077246333679854536330747512058491394803909983398076964890933677943029096171911865985376850654443993007953919414489685783873652562283685243584750350819178653616011626552914610148930867241608740496701844014528066221528459522129598826758156410976552628770241509485300309323987601466339444176878758256137011100362314789120747009903465621525199388145809956318647032828003017282172015307731182401368748515508733143423907070173838085582542285180152521779607961296065907655492689862265362950466285474782755936658930780477886389090336529863324662696936927687837789470702487998616201771422558968301383233230169332257233660206569418285856593586468502507802698350498416196978557192510485874990688375457296722814842189932584178558604923841818563201086067160968344724441371049096888001797469692690223781987121167691512753166288976381253007350641933574825264025196753256873423240019165022163599267201932387856053111211165217441282764857399455579732117239577148547018539455108151335571526376822119697154345888978759913239530025410666766911104839968780921934554982211776977415152180005882017113007535466827593363650266898039402981957034163883880590083985731736839905885112842416114447751696479097560491179994839795262025543820513225880954754805245776188575745467243170584842241959308797281241961893171970804687424254056842803517397532607545565014433309970853011067474305622917857090078363035889336640595663291093230921885808968880751193923736552928665087211296983891823803890114652998140874986824459128988937101364527944335716841987723322528599815305759171120619546222310523243839039799332941873721518173420738890601813405319180482271900626705113726575960586166225971757538275701878044035387906544118985157003463459799343244838630416502111749939894882756489052966608837340221329177491172025249145319062518279966184992673838284882332604331754190432945176816246198050779666140738272598833986227743194784023165167805558842579703207467235554780220411280708039266250536276878733067671736423919422988817705809714648934196469330181263549827555496868693905679050829659093412858053851047964660747198138188130683685897238526000256677147195662487518081513539939386179126216171485111294774146481829612580396141267993063044463749967182158007675376944816190823961296093686554998317434166949436932332505009451780267639751513791520626930465212938612372074016945991400354008330629929383152523238887212263826643574411885029092348639859000332586959154445863501739552745576804423397028565806595815566370324896466397936726610272282475993933598178347483193590385142759219017921798481044834228699343472297454655920613394258796122232673830455769241558108214298538615916564285076019111661988037214110511261331618070094033661992259305087742714272982504461199974799433750797080076871254035560621749906567237988763353688432196990741369950112206527342061175350988229582759318279612297846068519529926583724821807362382969421651362530729455616418216991249312757786572467056862908887491302205741719922197869800814433200122164613967975345441383039000376525649343844996349867492790296817399948260954762569718694514893238212437641820600804189625213407606125568707549642604781839768243747308942492849000291952450096861447210663968132834994485431901028270385874972224983458975523515830066883811564655243968386691977064877553322724849876525032376245382607864126638444270495549937219515477916449800755793071523103281267362414539699660589422536020748450304323888850240348449785145011499671133733048018047973631170365942468589417970011692660034222268415799887793121893859566020840569178260076419065012619922623634207027447606627575230258455811405924352611770259222144019757356482083129962611793580776235042882262727631922535158545879157249916751782711495491317760780798075016756212762710434560989582501912032153116923951755472392577969259112562377001228053478009609165828502549935858205504717819821552437130122170914011408300759269353589633224402322839540955889629474062240861426105202215101147300247026849900157042433815006556960234467861086449441279925249083393751703494132833444156198006212464138826288584107544831763216157937718370577620928751022264313427300537288402669506250274443072015275497230570380739123607583486836859681090147818048641139487423696810951745028787266340606482959240942835017695072269154914293010911181860122516059271498655049561491341749959838036616812117921133784389076151558995905900158842435882099384135777411989210835154784087399200246585466789515611628808516578566640564065048075481956489343144895406216597398621532098413077425612934934287531489923110695960585495394949457477655517521128689923779639681199806552260255389914592870018296423204602004511602703427388816239810637779119133135072647261452014763354585730121811281520986341814614487482434930319749710099686530720253639440181877442285791284442561199070099228270908626515552763097449556778591689772002919213996688846857592667034154836638725569728670070894847621677096767084839746490441944422396549136386247384678337833949842913047461723440687162891670833311855183655163838499325545177688050198684744296389527754165160972550207800810413866098250130691506511065220090183582786149496128199561623094360561481949058361783673259016538210987926154974931842653400624464617430577503391728745795646198696506986090175803196971304450764521855370767764258531154717504331822157400039680232462195992801735821590543050485077942073581816796507207657409225721458734357786407865024657361696765937483031813563171873018247797677311309298706934256020840729131117501366368055569789130947000951018999556149820932298296124679209177265115745302154074468585287146870542868402644732527834616430088221929920015366254329516001985696948019744523001470875489757253834763176629074744518476135716582401285113708690265323713557836537330134671293054149767267597141093464203489789216863492461212972523303215332614459143702441032476918325604630160810009696296785980562124517380892904944030950545642329171513779842470251865561648784332736254691303001820077260238446295728801844941581997929111944033757888396360272015219317452442692634922283520756280088740107200044528899356190370621174585240258233646997393874610620616615690402789345811206579123050613660784294196653650807939139773799219150264192537876510367880580071690326067504289631285562105814424044327446568713194491184334470025295276646605599299072612282252024373646277131556173534621523079427332492561390958887236822899502067416564294796167093872969203067577970603151553288365078261974009866927607542412250123460735561343558001823825441874637761596052521490169744414006875018216127274205180514433740351519989496577821676284191837572299576985624368347591217688910772434483357608015298941224658052574120254549162669753829651909819592068764275771087089800894846433322284673707481681183505365260269754532767629207251090922877748503731261886454269904022851265453676478380991393774333351453791759812428931551356161010511746270085426598930632011381762697887945077741792664626361391161801871843329886719713760096717195226818664767508713695120259787804807934150964599786072841110509226105842441610999541487587296348722002065024733355926719723988048016611511004682311122172996105690527030662832479839439912333721478159747744357013440567639895448903829037958770566197518023740419619562228273798249801942711570560875952694108099561845138404963316084322496014177040881668167380674106076085144226887669059592808558366956199806487469126739743899189144628049123093317793613402171096678974293697494886157337804846028977309376310375731970611767537772238796813531687812163122593573826352522682108164454244020483837544858985205192995756043998044161247728680985851866561036794626926604808107518174166753688053330950399403220755292501310425767872577467351116216538754837156578910809003310645275264135045902733390233993795274288459389222513071159403318272402339709935769288298997187966970842849799291229541905414685214643097214924632742024283984013673329982346723597603411306567424780210887650560796275933711584313032835883643599097204437894977360222071854715000460073429623012723247138650797110936621369206249812123116122370529289953483819626644723538955655415856512503394557360605318304254710200631726084155660598591165029419923330655483415491411168604766404561102013895063630235247427468838178673314035759909627393842971534475394314618940834578409195621474471167912370600450810114581416126741620639156268961444305564522184882860151090164335254317480618547113846603942312423419310030152223901874364418673599519472501072585613936965626983236835738638683311404216318981322392647343932039537328807431370809171662593995417613862987614744957867628714540969007239849324577233925787280763776269934862236978440158349099949920431025296123594360061520956274919707479607595715136866498529606432621678665943323277991856987811132658267802134815887183619894450108372886205236648375691917494403717190607820462171787716909505208096906837131313338297250527492374993980349866587275593918629885725510071175062393906220344537555343731695324764257296913192154043439656528478826231470366877225196589912962914307473376412563294816996505448717288778710563918205210166969299758413996935451535210301426300137859297347348758940625154480628723325311677676537046469486240108160573510453497148419860507628963717389528744963583830586054666161961178732425743313451759977357619175078465839787109889429042114037723778426830684322364386870191546356981813394901482311572257758213357644128067692172279848665594968608081482762920247067616733323606944144693497716253037030471092319620278791492585672407599990171428136909047747476723759223217012571320987809274114422744697457052927319674500711910994828126832850566669014691508265576716887476806317772374003019448154409225919406026354594426965868468127263116083916111153382919590304874474963900214287670696558343730310468283042568921116014803610350091442795415747510711510789780235637214909935220321317576660380990794029922408013765589022977204485305874983232326437060106863860346915528537808210366637150361882642773645413398209195036217853305159300213206507796177717460277844590751436258455240723643363055472766817217779082338392488916598444137112704832842416454202027104466362808123485422464594139586584058043531561562306375961018325408609358288789359979349546721428416679176328930265663387471942092400201043264327299808085775803352517245705958101649811564851318400123728108892343425075202001160285781602014974041349827480335866949876339474487730836419520063329886680042219706885908352553685906799863833716548388120690998429092044656332280840601046169970401898564049881074070620311573423824990447486596962624207789805543140874073165552744195996583892542366757842935789568928230573445539496333030572313667794489048305537095505660075598877330352926026292370266589913688816173235945760486285039992943744156757492785906670141816351391560119290960471091648524239880818960275638768446279358127466419938103339323683771485752614162954930186857093561306477290711810233993333426205398600835448946340316656696188297179728767097641057496192825400076228053095043942708472746331334868054646537609113024764562837286759599828608446735684801052435542941123274463443334362740478512993887354716876753114353090781619206873794705270150689886615719623235616562140651850191684394244898961994655067396251146288317881160415656464860573990471041038706348566089213465460900312037012256073316625608226676035221348014977035512354120288274486426799880245178144829097415738837971518554121515941173535454506232587998110994825139948200547154724569474708567594675464160302771927014269612820655830412410570681142736153669023172828367021578162132309522385205197522056949634014812977565416669280859393427100896144054342404047563554689574360850298965183114645611753501892471942509133011568326462763246292993507413204225821830291914272817873353638482931941469478789993888256782912820535489108995615468262601487562596043430953501882396013525770912988528664153281933793807586784144467785072639779442618759983269043115733981204669845799927243499334036278105773244992441806724587271427857131253501708123792138548033244607693727715559895814942058408432046165263319375049964515674446191227125003113825842693170585163177736310329604502627743799815427901065727115678381987268927268177393198378987309485494814101835265922119340867955844025433227150790293508376188969300453914545608497099603289003342641040877007239457503561678861205459744561788526886924702071466943267085247569236500304243993426030576865561561089189648041788627746267131461162456398686112602498169902103261416645128602262375911361723615970118353504942081830775460809952949999135839892487614444882164018790133608499676736931176414165281348074132323256881930368188789922423139077681605990050115166556373700759319938547817614485108624779777218350776011393854917544405853273807193647592588552870131696444540628480200208846607448813035807992922645169128234723276271234219533646990235464542984141962954451570700594601800320152434953911019996906445420004059600502749252723498240967481169038599484681037319561282144656175009376224630920036646218474247298575308303833131034184361251718783544973660230410836782072205444887431550439551403909725686735823801021891723742887346879525442705693475206256522886591609332019003738064360955843731469742983328112475785894901503550690463301027416403991302871293830286089729976737918269930716753403945296422299050836885545275688122208499618637857693437079465808695813071024816146756675710603676372697741125681889047489975203089257696601008514126750040139565373321919167170849346297450283789230562326304718438103554586603199105394732449813156227515454768811510436129115393672282580405545178357818479480922160040402826407150319355308262266177264713107035617149902328448061687299846743262614719589660332682601611425810852873480152155538652307576924642075252662707117165360856654567933056684474964504758678145346457000294255020009202940536181009599684454549557858940881860579941807624125836162551754429883174866994304738560416667905073359227787738856011348649379881384689326256761803663865296282307493430231008240216824375609535689026457694453740388394014205706746930125570640091265992802956036014695064259609816979945416540486233080472482030404167466975349263063620817083809743720425797208482576001505405996643752648668805199170070855393091134887529417027921482446059266674226213039631254054149148389160431818250514611892412762678301391004412682138457344653746948440553021938382267124102468083990356829427485561045589834353671880086615260691504210697662964811367038890011925742297284791180627130223594746222330714228686387140393890601746765077395649232802806198469982271679170274743168040610705320643296721178416277553567254107395532153756275649016274075799677464987936157668400454915962324906781991389992126280578082410932001167161482723900209723743878281959580045223534809654169741023794288224944162624046358259744382086262305779036428265352548004575946763936207630602020767843471066136415743816362094916732612163018868115655387691380987134793113524837620943315975043123941495639257823227633694047730009719456246919212493662919159577237658427860526350308715615142414021568608783438430852227383316118008979658209638759719105099945428442256003573400428573104999285170521172157101328359277100633803232094535665751405003496065401746177414982791720215085682352482722016416006358996675871150237832093190006693718147379069073592811747456108699124975590509612855293394485259953471608932991188835359352615152985935044272215117127604441533732932003373660022482162573319013455159321790816976397479751029555953668494693119948225316213763200943850816416702919717168186035749996145908750098112849308818301449834171362093154084404421059389510903733275010907566385414551185866309692596659083134593048887313201245259680578416435354136697480726005248780549282666390503445674974279215026102698285398797686449705076798921034425771134553216761649273991044738130973517032890964835040566625538710612244663590673867083540050294659998645357263716068406981043078502479589457636660542118971482212456769598260019699016005540139042693936943865734202043637682687220003819727467096311046220007323992051718318761312919994580561432005793188272888708684214195221074853394091082438785227760623787655629453978592093631212612832388768826449063311183436286838918612437057194552890913710955336967283104305908672173026667434318703147417060562691274449880240237739646295298369487928357979012368525004454460925184233982582226605710341987803429318246090972098739428963770023698210601783875227043029803939219695207273809246448080738185750351303695358789209183418140435589333863179699631640559067847442558791152630107868454290251912056321041133029448978236489730474221581313954130213760175840350051982804822624718931924115554775888629781361411405527158697583310785277804657183478653777195391999094737199637959139838954163742075945108456400321637978945613052924461399429608456773224709849338939200041984479720385404086262809886595217710795108093739629529129960979550079777931093198181432686019966394703458016099283182816073308625395496762524236993104976551159539464062980378858139281353878806983335498663397616241247191047684975045166102093553946474530914716320685886675356654396846747908743642720810031046808050508049329623871074591868691129292197814452167836171181060714898172446589162886090006312108235209259196800297497016122280765452379471483529663967537924138018315951239774871724060745939671431699391702654336847838968111916334516269132402480074618209174237577917204815088547752302570776576089668025426925901578069396943095002974371853938176976903603906884936153325436917396260473940121828883520895422028432785356428054723546673334521424292577593024325352955870258822889711983947562004663920595766311604345967377955633487593351473512315889983361260454993893482080620869170778855821577683102303489477814758759378958174082139542047536886420679318778670144902160595723583478519811574784191791712978498816153711138229387851994522497368050679388193639669529633496404908825772013939364924556536595787517887676773508765970445849523830031909268898803427247604157400257694382129528909125620265322874283676863352309344519403844914005816685647230379849854294795527282764879275338963395408400627346948243975205896123050503670864190697108797527938829271270126547523886425359845984249300806279446868875555118563304291856474250303175555540977613920687667160302802349039421300794252430760014998181128449929773779862960905093048594850065609788022373261804740465391870650245283760637964649283094404661490112192108775379215593229350031423062781722333543124205024390914117772653211643273354081358152707054467060042230095519125725815197111024727165406564731135526059613787034047029353191413229493596282884580993325175711341838045636252316076747678210648862235240968781541614359946273880954924270364873597164016673638104002026931645996926061040335718684489836309107589889839704700700927718559232764595483451816971535614262008571348275444074720893267357667536500678014737201981231873764812572124482115742758312430353959306325973718770747574723468255036055250900976239679865158775896389528972418564196021246786797106138906363879890884696702555334550790834200039907392874425565176275453883017425191036486078616263730315953609365104316304987449311977628592764656929564756174064209482598827743928393254195058618539076234445744363028536451372692389196376115244552878273518905581451233829340160968698242481591407442775222442797953197307881404761743829600122680363406457031031085281334865892299688662749146860175870782270463298539958048456107434830357451099251595581801325424119898053713001710858624959972870030281516982342820770814411456819782550813752115773414347064591376246113536486885329122575322655353493742721907014263046159904981935879178815674129574250873091017841697871977668205971167335752407261251252521631117614242657127407379816502264542344014289050752957769491445676317163774720448997840897993808190708649773679781780086106565763352790931456507424136846927890074279407571653250700159187480281252726566194963100808060843334984009374500722847894249917545651314498410538117855343867900548399275668006768567587017646303648294622246343902585374795922030589796428492771174725076593475480715739825653431315253290453020267799712908535556102106367035050364657883774821871390090959877194690318899636538295836269644024123769782333533060369849643390380690266538731521977123433990384183159426263552137042188461649257409383200922842677395282049564162249604568114310168553066604619803711162251328927320988720723996097070759737633240685417984843518155752615647480187150330797776329785769771362666099442230571379224462214127551132429847199721221056938025440565434846526152727078111271826980804354323665118258497022239344500619144308301659048748730202291434987237345683007430424191127314451885580860330922809972723655826271359826671320913466353414804673467346378694534510118723163305717458857881600169545342786505294677535958705159024701161749113022737992378652430673618858177875033096477496807861860636188315735920751738370789169926018603471764051421610413417950774694720065715505843431316529062602790167551391266282282853811860205417507907895699747999481811896596630925920081531775908229807674347509378696546845863210371471277254759201285000295494312975903876226064860883051112654040629598368498324926858430416014924634811741005546823807083147999899637639220204497995157838080472013073142613749386835728295705478694229979268689973458800160683474490446012710220097076322615056820394020453403861393298006679743068739988440285544407511613791836006835455066924865839677606896863171835039411057941354606515308458761550987569591358784415770598199042289492952696748395096731985046733617095834307634217345761639591922287079853719454344288594522038039500656128684258163354239614807603383105811376778307235084818786523298604619881937575722551007095688530247051493131888747732688647890670950026036727736138695736805339196852584752926372369924930785756965691552497984527246888303027220786565868094369111629229614421129623830031967334953500065743614980868423095456145595305593819464370538230625491376094357476022459186338205356887165027510433191925277451477931546593354933469462307114400119568915881122838134411375148416463875027513326049369036479741910961896364047546751474982378715576641775281219753295088678426254374200868703420450002532512984498669159701915360229598831090327460301018013452880149779806752052462833278087262608847305653185579305764495724144043546845172824956832719846580300021371255544371944592226662054600745801556602037230681794792692415888275146796816175868451231053242781584512937586103605475161382402528173427227993950016333525599825488563950675482916887024048875076879556063817966280607095116758305327326442653024009518596601556043405400088827760977841854869089893918630005155061090903069398501511721484520062496104436432261549020474613919616719951476618951938916541469786122774038429151910743712216374123373492161955471625056785512743833513827777513635341534802458935146276808220157354254465190196212655068198144396540987496814886631832844679752103537245968039408787242889105385307939870299680833069606368630530099300664995427670905253691151175659388796161396233351848694952150589363872426485575340595649416283262218441100070906259881672771160850878222104827623967802415889356396096576426991473907447637934034616743461980180700260403779340618738444030757526895471139000484526722238149313718267066312057359820153471884261357179611316956181536538186126523573290929106376678187474599595090530860677331255737214259566063246622962842088636705087236117883140351028039911423040465400965550775706462211667463548270009723899730139892509243354030573669235110474392369162407756625915311884464286874602942186578882170822840709664108167142608566573295291765667743459681959654886596665839703972037302171619691843671007589135912948416280399276826082019311113500685393204249922519713250473948314378417741484009999571302016142592214865081719198812798882533810792088108483335678244843419863390710233330557035146304062399990084899327384797625257057847456917840769499038625363446681128922441454794011959469921177484333098320256086105389607284939158617536048792774435090237241788839804508783555162674792544084480667023507818682031814634967162324961122925616684398119870353661416088610380011312505727779327487252163699930521309879533464261600697115400934698691395777464262241840756982480157880026476667691799050753465846059434457208835758908679322465300498346213302933055098517619050004599666236014228113715701564811988717893138260048194272593016523694282105963063023984893970097399202185067326991321636027419852054262447932730242209397174678511093517496573740353948539793547443938861357808290879464955296263888038582539433437520522185380319425782050252397475394548640914640577697635609356822912014449909513033542102327500293901688626833920897782349539097073434273110175779569203744526340825235827924911811683847612333100740135418453788455982815330840984798372085699169710499592291868440078849198074629739445861680093833259643163736323874302069570570231448185928062420664304076201952587273697440351169522963449164786861861459488513925218729545758035533865803829572103921204719909400386479649236225500056990746311539358519332513486559108581892522059107731761643697825833413714993944409634763620005095979352939431020730533182391071702594356866540125916479936224474063116805402614280401379332035539603660327475705555616160314850201415177575258264442022326496305923726836440453478314789352520516001689015112193587107043207854707866397773969418322681976375520683853549128577794701033348121178113046836971320893845417806162602555110667615583820447291847761789028622652197449355893730508156873160363282827586275336942951795755069673899256986423798478635019330752212632153239761732685958217583269444874015920098186803111963870291466514456629016275020635144852652947429285018152656156487839501876087966774475029645680330226476866327763338102558895863364389914534037720155912978391818569589070569740459237695586252906822148753218708847393002592295942804695718706699912176379540099478823015316271671405790328620242698197560836631873960908382034155583503683163814220362178639660337762740583148520547469105841704800295071991915353761135515687393396235591446239644647383671676599345280133259279016404525934486173591063235561480790353843580154343839225296946343368870412399405300175348097463855854493070169265454808445782807748284417863559877814524091091865695839729945119800916351176169808431354214354015447498458990845623879665976923503028567967024699136294815363801628057804127995909962527222932311222911353844199150504375200461038346312937427146462501289458035672467781042118982264155693344421386336562867071509567852702537374765980881377976755110414538381478825284904417810174760680249722593126769113801622231146944640283318519542848889404791045899028152077172446890297547471982253931883410619591460388346206860912350637335856068813377069054606404415026117355291530383720098798072524914745843556315534474551536680626213011441088308276452981524436479875164010978582161616200585114234374412186475717427276207483230806733010600258252057532264783257490356317686306433732939053037010972438397535204580503467821375502141563713193338841585664867882235652546174046411671757090737604999218911478713622483848910989519928005796126502646115630874584021835462321192654046348938519510361822421916501159492456772776467677765175671823255909913470633033095004699678671277097234086021787236001975173770619992847976827114884580515289571850901996045196667960627851872982207719753946327103587660789979926815857280965040238917411306418674853915593641036682445372501775226237842840708290736930514107984929947362133711749453832037532076056757685680142427629671767343305842285620249208521932925620318007449858960542710646185161956612943476438132239462536348457598226564460095382758626414993866413103174643938757328364346139151036843297143395168554003419916595348870641434693227219500690977461628574954349791500068632872285461251769455663660546411658644090741694969542351031185912626903134752724989485407470427348579120742838476688345981540759820947306361939219002117117947383412706917399931908585350750370448675118009837926607920667058801165929823814615344398594576795335142781935884308953426014742524902065397912476813832576499660147349267876295453187346054046299289198858599475683992788729266383350601322497781815888050547809287763466640236001276529379679004064827683041606138047956485735615271779591994624021568318620375040143394715806883950790312593722608646314312004796392054237917708341227265675103576395100208366407502375948244753364506473602983538154015213488600683234130763407463421922806164282280669998194979994363379075841312108687865742403395517183043789185731648022583038771347884532036423808156313640180171327387565258438684537351056466555890789508692281685892093441630770887826776090776343375436749420843999240804885348327876054517154771227628194097704975024173862803592067609283246444566889688868518612082353618562036544160282108325161033215279105093768901222837435355441136318437853890373892109881714538921068945354949614828744777554473408917604200547047462071643243984819961549918401762371168793406259000386235866977373607369028803591006613336936077222293639446998887847085625608638318291531489039954164646419961432935003055616547590952168198227882388730642511351446664602759008040237476086144592984536230791993338171856249753792948044042480791865273148850300724611169902913394525018070010215633422346571147224189369642699319209319853160938691596512006577939322876253860101956375517716196885079570578200882149442744832871362553429857488554649721374121115463036599626196520373429439613302574032589032216853872283507649498175356853157086600337705142892358879206954901449352389742913327433132627972930352862691471281830217135386283901029780507818478081069890101615310239838693802153380051476602998445942303018431194457181943205301496129612446501357118628048162227066741488421785084412118872251828844136732010787265357483919271088036566061541900360825729282598999964245240707437365713687576251883731195324068498731453328503897808789445131691179272971861564893985050127940549337026874072144747832308180294298300055073714425038845532183144910609274128296764735395556859854258349674915984198660739185539262954526177275585805723910647906683819197625604518550277240114554547505894238945600054603058258147876233368362703289902622733166276043297896289250532719111504765039323219973344989457267546604266823831892615177303908091241932089188965170447648405783348571668195275573077549352051295082500733036149536681035590038183379327440626629543550884491701339224395032194130516290781480719870983421253253359193318858379011270244990530305889579320651672401902983410779609425925632874973676311059590219879007282285310558244903704070184293070001476190808474206278832888148301420437455334483608249924647008190762254699568589543970706192328102357914888958311345195022865924478832577390794254570808266908067179960645527582665857827173212266462639894708939320005272190640995152550295953881706617916462562110674314663958286452075559154675742263179813400345184342780309423311488716811273555232744920405534199429009540555553156787040909606113019468056914347075417317485486320162493825879165003929098706934099005616213036446061194733036808535438327440744627286057940419318578945467214763384947238188841035390540740093519006382454114398638005194318471554002834539223154234053814155658736052171152799016805932513670109173548718464176751161272191892213974087869991912093779515860948811747554267703434555854041938100758935449540174995964294482618938568037935655498327842612423976738939059020555051062933609934172821413710439819177137982345072642860319187831170890820374872445665489128467327592487499842897098502792361922706207095311369486297722270852291168649807895861483971830636344561463843647596201062399920116365219922391555303091463037461625440282529687376353160811666107778367757270187332977542882887139495647103516540484335003613145063121476140229721745495294279360390225511545051790996169464712545920621370483639671182954747732565329424977812052102165555981103354038548144076235705339715797917177634921243214735342968961188212347421278609701106707105867546737630403172540620243359527210958571623107954244491320270253169485048875329063667459384725013655132411375411788603685756846314508435318542792337088920846954878406156431745609187280076119993587888818433841576544086963247883290199420621434042119655396952205144947226589529268220062608649416991854070373275578820822092541651468016607903399674898678207339580417838809343343998836782548167150686936534986438891581272325914087895646341602104186602367469378937610562133159130493088860545887346618119495053451270651102474652165496491586823561967316780722407247328077730537381231547169945176663820635245090794415261042399091794510726741034407085714531410091271920399283953163851280495752130223001811280098813354583889285392357463305717440453106416951345851837635330517699010417884224019065157184195174972080725375906785370634222509853281665338238324158992363533409331277154431995095165356788678794719338737617929291049023892905842183032119133839179765852006498463203192420340652351668631015849392132321427292163459161527778465521405156876516352115540846188196825648600424820579678184282274862461097019144092993154759446088874385452329081485645612863616458527228213979608613252276676910265675171323183894025564398237820973630337629896333124137797464271475664918133857598017334815100518767573447652120878505717308169657911753787776817531730362377370729430206955965992584102834531477565447994197661518789633085691419043299997043577723911262898668110645906392865848938536439352238156048262587851212241135265410499066504007236396983010298402422742401174873889752071556153378227398766753203660491461032424912844001501715571464988442652302009265519852993644415495551422215384173479678384773128862638573154540633657382046524031353593708266271246511540397636697067848041406776278610461166356727107173697374609015188804611689073642487825951510773153224531407939111529642861109205622620314326831872605548549865697475695422686446710811800753921791537788157328628800094160176093701777072849230379323193212971554297157565415388928136285702822920906024819652479521497213477856705556749249345767207497933328279249772423190492720594767993251323883868868558480793361214715368674023940433121524924693852305184201985313483740816291251216978929312168445742033076212901042122108640484756556560700980356354111158762132631275795495831524516842179249707001048797832730719308134701304958443804888094109181668250967086378871495637807621474525366419288634599865675132600687092890874133597852130741927580793198037551042709417232043555763167334154854486855398089121382194535741110384424115043721795056549056891544203917510784148272464348303793177955552972474579981960582135216193371842678314657717960628367453815275936036531297020813446625639991470805825168812890401938703255264876195217540035174365404806159394836751101031675631799475288238787005821015361998893256148340815133944083491140402538893639383271691949211426668178860914799563433132578729122314884279985651848407210754762545823210795076860322021851512470982772023571672061851151735177049469456945699522368464712605318546712604879232265081832719407704880827397380381922488391851446819477158567694607515707931614593357168582916910962687306676767947370714911880372271266037106464665505805709151932632440533615356035207874143254561468130410569432574354227175809578655421301474007970033457096477363970295340007437013389939540836462914345088585767232388091860949365470586112130620249440361058081777970079364600529341662135200468017276573920279500739316376978324674246976265188360613833834152674846524437161143784158195261649299543705903444507824446142960726443407060649278432964683340107249256873701824913391673693760667648960550831551722747207479341034612817143930983162603309253697966799783194329742674309787908557953865334855335338139143614504912953385721322661012204412643730521313216615197403186753594140424360717206258998234858844196303172376271759393124761736622328326579714295362600273714532909675491578410049495413678653998578777181615915798815710592590527845366190884642302039885655799914143500807351176553368665249070310286155670473157019047538305861534857230528180456893889089825269992356961811986643483291415055657748546630845278452844302118655711332766581332861935405766380663067469405973832703006759795068149935647594562721635522397226415436364014618785927279905151238694133109322980386876235271731998389956226688748766603089627624868863810178926491619328564675434130507476433458459232162958539630522422472838633133292656824917699825395622031901892947070038198259914052187218090503118230482201066905150842399667708502736049438812342922647089654690202401033870103771059636431909956794961075483304405529801740409405957095206442668688890836554533334736595833852160228159175258381904462989923807270390295692655023770742819181261772106609963480608970134376820447065649585603996855235998653040934178385681464890525318231574030537947242041837931641798392426893961620244382861787907511321666908277169045757029189440828937033288774439421325531423367107981820886399836739820947109828992267366931356841188440257782664970766387726137107394537067652167568696214268123976383243889874217444233485382726299325120563369701793525763093827768084902804150007914433524344298487108895640401495409910172961303195244200330417284642492188295652545235681636882547869276921080352588983668663967430715656902014250433426027433239201941122470627122200971080615852855582734972459757296038713780032732157953694477399142866060449518934724236960909834312282712998650284059615172643331604788903350292887215240022770041975994217164977381036125742340847036555245122571984488575341496924008255240386772053890462528477239068684755677876477063717858619761690997464800996548154061913592823931847146407230205443701211239627804668749562276592891368844555239054234252926349891026588163990499222107830687315138464296093558375775538591110978562984633477083385346816236728365385769272692706219939518388576579822846299843309705407756719332119733551986703924211122155329387939355472895980471534754149770418470707456357711348486762158911547597232564146914924844389408501194715323478282518508401040798521576484625969882326732489207851387366762530669391730043706347358773317552493075476300691821096498915397473786734443973018394313446845484695088308749203297069778457898927335985177552076234010449307061014414638755292021716964007120548812256453745055249548851566157238319089639130699767015900757209796552972827008127069007671395332011178750637843159079338708351580431569491244553663849083010216773925845901395242020866513173052769589179551072906854508927823403710821303223323764903529021572305535629803347357737884621954078731031414477743978127888959953874401062485172676168734010320286594593926983548034749447798986906448374933021468402198088144053346608516608143378585150021395468552645867393574846842096259642870679850421194192296831871450118544283896194025481641260553957150497800289252446780784100922980702220502516508103559992954328440371487456244226740053388005250653581545454231480796791033570912124850995392465870472366370026757350834949623044310106791672668102948312945799985914927643290616176998765458461246241872937518387220553593390666342754537836424545963070068201496333211871440140734588983991578129410553705236598209964235266315219164411367908105539254264711409611309931262196254846132434074891875639571964640728054186478536035461265515186773187537644679633879696319054755216189729301367040128249532832342916544967927879779626991792526209146151004673620341283181474441741647439933270340781204716151609535103382678520453707484053636689007043152941696632107122681529573666249025428193107689814193813764303318589286195075446936877657537521184667753186709987206784534551983907474394950413670482560031655331868186638654000629589072863291717369748413548652403918141489038997109739377531408089682128501653171280255197915368604520151124724491360887043123539351886441251971714439484635531088025375755130926126858067656586193546216508278826463535262366443371237209867027873388040891427505470554369808008890340071447481195575715276484411834050378337241547705047029028263669672578104103044152421551521589580695690274493766387298027806794348584099862163142978557189895941296148876808146589011546968497245375989894144579379068903164112519486390829819028496054255034268753281539643659597965699727277480912295073617277476378311727621455452832931683080592222890356642107542922797386644263145525347264816456465313931632034283023740225151823899860083691981393162646068835405100534938262578320242668369515297293068813567959119862547192040655069364727638931155220641358481453715129173402434150456033110710465261281481111227955259428498868464146657733007781618557397385223947878716755083396292563665315372065370340151597048322640774222392789181738642302403596653203827512066419566829908113230637966353236333062375786434432332412197962973427616925408454123297731894241132097347601593379362003244739720696120910373903069040221759218516288458380318593626475272739023809316452655946868646556572586464148172412239622010230453551690568680681892513286795724139475737979162470861178970435785944212237752349826742956054760335448447969005895538197006029475581806116870075760463510996519571974790534980211822625691407925808166738989956252647277303639402114751405694711220934647021152435513048960156307147928029072030331499051768433939654498570605947549936356939301957901477175438896675110354988227421635821230074417098872209727334932511707528323302325515246751981444987914093806782053009335376785750257303218338412304079968693700488160906772057335009919109982594989279057870869964693759788921348622283249945267207977062642087905084658584297125011574710178132736619865068515294400317367823989638009550420544963011984297817505638468214983852751878135451922795988849598254728291758287502106821824087659416080748965531405499996724445891430082979576703850096639678636794922506285155391588806206928448526341466114843854283393669765890283228877956402962436773554333563717156629799730908813503594256399515627082873627357605539317540378662464882531088496601792801386905042848137887684946585218204978618637137155874776991534896607952340409538520048739802200729362431857492188265622726617627915184141976559109686488968552234550260037922161164161558018935677158507802267867236497654861967416110422402237209726425616569610701479132143501952648072326898106286905838339559610057054873344188667780574779078778098529500814580741173422715902939995352189886614505414916041037763989155670042474210852029984326879400138526167004517688912030017833802667865870700793271681186736710817623567794035029475870186202292772005905497968552356175072986922282280912462852882981591538174980020194449101418340041202943745735166944501387321132368659998795323789177325686415885045029185385969025099745247817914430990140139433578639497600777910081595880076038616132678631638771779985468040327424221970306070564161201396100287913237841666800546727170541888602383388148899709924890307547773557962070960546527934083696447575318996778746460388609489739748544494095956207962477180497073234050868251602976490345775173231500159353030722853630671071588452755223022159707340047562987971555768890347417395405709307354812519360952051259899886561866404280181561483672563136677980273302965087258048130554488504927931413078590710849970304341083114158564234730954763556556069105952884577030243048750726450505644405635008340472173784996951161113445516533345692454072398717012760992399279414437543712182914238076362485569744952809925756392886191297865417111039400613932271100537948767695090716345122698612291209884966145557190031559370329872993708024864725141569472234577060293862824097409000802990573180670711710870505817001550876487882907319282522859301019019227929214135688373882157069867440112691679637062424486709388151175194280135189373972511918912702556830245700498114274340742315807537902813575220988384549748257273405632190777979024551329419848686107777799381566909078106951374107257352280803014738066109428352384906851007871916628052868004832155400257116067211497298255361988725728051326073549479700480976500057979057642194587433402978191762479005849299436119697095490996524369156161089337875231247192737124446594805055595939893198405279382930372345377748112048741743673118070978657921242390544026789492581674096480292543611980953382818498818705493054457288167802505413246321496450222591098868052902339319360153212758700659068769332697587094650804291897075072939764854395683441401543708332176844766015371988192637912469715823413184117801825101611508596269010047974520145501062641641824454780184864510089957600199232918020182803087934651714722009218282895550377946429156593817395761907830993100780516344093800741425772026187065917292028942063777659337806942775076801333704112558104744138632333045831515066310857076910838136932792009519122379711498993254600260804538695955732296529773062100583785743043051954645831379143239481186675489742454992217057728263201279739053235323730812498805879946625419068399242534046283656091507910823180340383017970564178629004352172830363781208107603367421798599402319221147221797085673936474878420145894214326868435449924645593250381918236083962939444981052794600643888372245914789962592781263860511857509051148270935812092599946858972877255468133694823089962500298912986218671056577391800592562302831973182212676501423868071270002237628153959563506560402890619748723753480770227913630533883105926059852887673627887367810266813907906293553534151109738654885736801378225144177671774451369484454828165404147226121553199457802726417376674046261823159823319279201199677124869339151636660807908341341685485784691619828423484787512680490507233655004168206763063553298851149294961264528771125694737110392940629178333687868747573852668265380624826450146505717328423390062006500670218413500766648029839308347212820325049654459209755705859475753456458720078263818533855056051669758979425123188165559290719718023869329030363255366535244588604982471870172860440124459091872976856319160385628491152572760884526646110734680342750093286499060427326419854987194573201226108812894824779890228334646111852175600190117121534094253794410128400938135013139216309588492375070719522441166856840107744375215848786902709565664224111064261203061348237917201614414511559704392805743513421787490925147540800564366976276592575582572240662030777674150029389669802888113090556469318800133275925565623843115937614645094373555948945466242101228524271459523602649138413059735987581371754907576169782557673555578499440865234182440431412314563845922183148656749235794309277241944498575246857333732159683945976788674228122038934566846779789682383594243143714988047586110247152786425157095133855545590157593813285300503058705438724156299950825193748003520719736386124777575074891957794755586696783287904325547376382695966698771718196012906393126557425549219831080877250416475807244703871488578531310129630829788358225905491668581745741594865271192884575571266240325333415878273698434226296781324989021274663206820719759026079034296250598496158508472990072568352366872517377648964875348421071538751457023659216166743372661949564927491154451937665345764962045634299786167808036700582051768558994788467878683657571226029343939220369737083853316746568907567695059311490590544613791423683366247636145402608726911255122511508535021709395726096797986786844580631938018846066580000226915632054351261590337788271870104034535723628684219929416862374110572174597462003329146793368764297668934803904092796854631084186925989430558890509046185892221759112441366724508212939901775822184260812115549221208241374598703102003536132907956356853784323925547325713093885870708232118205176963068152020981943667615030848487551592752108849685089748707516586362300315893090210485639097401760478535900490742462485944708561734967902859272199834606343475547866834385036742950130774718825811215915313693540526736737471585338654718462979317266153318233444936374587596114170810924987607576119325997873503750949340875293931492627416163700178710307472679515910335641416784910109594151166527237980494122998416790062874689450144742025409343774849232035389930335802697128830032281814109975176690816043307690521886174798521743864705008630691713833820977040065055582010901652565033941231084045371256855467740520131517683167178271830062114158443279355413478513922120229508381760414335511263521239428776787220705991673791977623746283064477711537042154582550675392366876809479890412500713243682262815009223254682300178649151965572729797585412736144908747765770083060887202950877496758551164879686984086426202514224348708908971700019144195535927391513470543806082747978019581154858592089434860306888072384555837780295874536116514834486606813279694378626290842773056130757617768998137972363485689524265711583720207829307766796564107179685610938350158520208478721693490656288016015995533796678510764090058584207918674580939939598540847972979588021600314938937916820368426342647576638698455656616360703433860585365888958569333856783960160914867105887920976681846011557348611405855303024895708744364487025052046958133722265058509406049509031893938169762250288247452991322693894596677139462690762933945881205247534578591305409246944038232317189148917001423568910175188594337438740112979388057477077406729451512912472362507567574525310130572269182870255257056983825767805547122516816357478060529904167607279323473128759866214557224126248272214828820759072279037560444956219345594609034188742876513765992767541335758793933966748831630986538334134254966487111132073122470914509461872719832515710746750949865311791225461662959850487803529645697043718136009982915189175336771782164451539008221040128622906846368016246661317141895577742990487221537243986639877870770237449449442379187482712740406010257569005737055187607492550463540138847679675208058614898523478638681136775234645482077509489377683648425454874901047144573763161576583203534688581382980670762260513287437017794178084315165913487266956009126438804386670130467555595653046847191461686895193451405448474383214580896048505710583305938268448666317212211387548860465372041283984066813360254775579677610112701635076992850536332872874653036593827108897244549897156209759918924006315446340965694862989740556732566177375502462401608838395106063506524020871817735925841764702616760440084577780716090103910032655263381110717833738666552487800475408233311285499732184506029987191792654471239222514264507003463145082746956068371734117588951939445990645786692952060981480759276209059661304154400294503438024663325703049387675024044681156048781324466461452286439870733488532271255531175989046157408959624212841697765137329924582627656731935378487928787880530482295642538046075076381328394924975874467113053010842800225761476654298027283185165081234697839383861345528179898369858144733231922739752951864135108267277489581846230526745067977217282188436155347557601632776975408638056529357325623850824390558332933123158118922319418891798939021549061700797114828625147564926967550478468633148894551759626314395625209445605841046075060600482542007769734264968486259016518395289595627927724217513668226023027736015981844405801852031495279021576518395696328165639039173711909273800616596931095044391091796941360114223077669683003154091446419342326061706992312144966703982869129163016885097483279833153815988154947815964853951068664337238657840576281404552088605477529752616859859264777830647383360132030408092550755526594279464747077947866594189856187750758956873738098873269402753843218871626178942649464512895498394210220548456842648666366482586739267842185481786793105857596186334953016668577258273362382798796011314276043764688216837961186983303700132384261653358691653383012231953581760578669961098642784400802818301268910379768179535959789701948823244776603265375087410887054424342102814526538934607372156812916764520476404135876970094520716164535380020438823396323238925729554332633581740003158678895205092770546297685299537708331016709756422359402344645816800892479945908431662613736557057457479046216105005167382917266662750272956730726679673108524608797304190661721578692131933655470300127442657941527341091137394820888455684959755871245398001984742607501216598360515380412635216359818852681744878393558046132548884153493539667289778049649475788972857418798096361886550983405324211133538123781897791515946264988597912689955472580935861998814431746978336609462237788579783901902708230229694289787377971945419940969008038758236558322435310872564137055829139488614568346481557917648728141772413174469584128147385857166913691272608827844318905525746965221214959520045134785377177374502066054216644838680123108146065384229587271375412322565368932579102477213196634285558056747079524261437555578084668377143232749482042839596355026302005903385182597910057965848141802674966084927879815760192866574552111708067785910093815648993759316757828475984955745590471506132753849570282509846186582999581366940279837944153276870600770906211744983406552359400936616048987887144717000145079817459044885743413704834713619078192064358845103612827091949944874983448623387196271669907118895558089356739335325421883403856632800103587264226582913999628660375648794461927367884074012938271539172406747744347103025090734388255830814060748791416057584828975124159551489143982907771234578754999554976061909785053362370809882277070645123528711254139413241677541647978414971130286136449181953738143363085146510049841385135051234280167387035776097483553090920294390625198284158638714784815095625570597632377771987087329906960840468704750122930424057294774698930594899512781758355006638593422288433815551243235328897215378406612525416015965209120080756668269108574118048519621909511678227973309308323685039086182877233443149271239828849756901283787713161124434132073259906418118530875271976607728437200392897122599030325407661051388534657212775269654706595813802693508320584198415984183103137911542954121614160114851391931316448014548776301741846887762116898887190481473977540318899658201049088229689066162564036140060684725359886087328364428894317085484190824901288707852181457540827913688486562928654608525906529629202129133871502006201977799477957399649230016295368142185627970485110486707128943621586692200537173353848176218220498519690966009070301568547751070475966647015963261933828159024496036832445831999706865333522602568408294959844093732408817425661730704539998169737822732768965578419366562780233708869225079150089412406128991183992073399978077533726886130825658820875157509499635011660525729300603181430456848728310016006880663644521917617777608425486989841938419357442056870941752739389804116460734689898664226791511306906356496820578526644702159309345176153073196958647765805455786796653150021839661539575934247510169697451412905425675906458736543617854702487407691502727043557881427683308042925714508097999110957206740752091320078369322932695123967872546945647272984403391331848733258080982649369451483165169297837382270684949579268031821477328009932392233117102444728550925441228122428488687417357185489459250667173642022917334702229275464684275069505745878202872820505906555961914945506449712955560313209632577480950491689339881990316859451729104000365420025013942188628235613331199231917620189219654997768599453839584105818734670909308535820456862590044568628578990727005632575280652207962209037430564123074833264066511114432466406192843144388304133835784636665175302303517495640833806068353624552273858354827025656593329227442854658058342986490226857614157067002456058545671578536627378800491451044114505228124822758629811025116368069632590828997500068266294652548354714692467681409010070333934618508304902648101640087483860689215946803675982178089613764822449181059734705063037910871098644195177657516309869805975815640673508260844468165304666248108731690273802325580697815615988795161686817700567153834930958358758711414377635039651697841430644314723280432520075739081875741371849793111771221519228028198141209201586204025798541271855068400793412351553149276863541467941400587117085647137964500611160697700841194059295902815828094355798249993079350689091854206641674884912621976056116662479868379162472331757545129540174814574372475059885735454116824781568461213474076034154305364599275581737494035197489193653076470252648708520722702195926882833605302726541427464108302685320049027609135159108722676823367698233627171070748209591837778609166779491117527629961085943949330239761919012367722025110442876197965393053065477107337927326244721320165791042498964975598535612390873471101473467733382981919856711284343982202481821953156359102983135669394515792573668194937589485575684759172473780035005247869379449991387300529943476627165802265918031544691633327469202515927456720708827528145398430502171979562196963813371842615749460915321581723144799887851170430173865024892383844329963834465991302850787650483907117268320594081761426877522905224221681341945315581926138834932525094151865542623386376672215609369149858439999373993712844701603799853758026291267135766322755347591091637862306297092907871168029947325541672541746684555474555607422385458386730278175233258653396553771367413037440897463060388705815019086239604668530611550132846207621549825226132946883794245579999741489458543409201431749746301402687143063795644387479732072407610207040129267379917631917990398988268352622336465649339327138797678438645619782536735306001084937430791280435647686397055390200107519481933758752763217074602872232441341965227694331008789224543313354220314223370984651564560313846487572843935838690665957778822118630508843589064408389157033473643291241916477491535035599854672469518163077344612547127450139642092614149952658127070665720470617426634510608898751993413992167460136648156904061072775964376696934015146680867557416648379090482428609878536783367189606982698405540119041139891298859432243065835774392858892080428325911671279037273462980615895311476437739128077535348029454932736336617675145319642763248558740998132918426174848303381470944251621950649758816703738171530091110149363190755768265746400957826738483738330783315970068445284935788145550908978599571587774054139146379372824955094742849418598384064615820820231297610568717228502147763018552548565434833221298699876532887055682321195630125564867536968286687005865090240855599804598502669025189507201317154231278743598941984171077154319818229812174264144914922121444617530926574366434548479658277392319930789720906781353979893639313273024904894968150794105561285194319310539077667925141412936140305058887661276664430554715321901403613104885127791849384961548877168936515042131488655045404987184000151196784241100808540530026385200477984585952370647745407443486029693212682408939708790220024661499762437543529925992123365824230910466643061410662109181648014574364325867654616291188341550276853560604444019563392784837878843618266745609952198638179608031049910221330240824243249565467131857790242501183944013004651421091925477419727221771895786246794077841867047279639168063446446350316195692656126701861493292579615982986861870534558945043878320237368992927568338561756017977688237302921512303291421443340484990688883062684685234226156782559802437431749000878570384676099496119566334881417920656933015520071379877738388775971932806840776080326441672401721650610204453814452772798052284915473725025914422562952034428090724848304837999941009498191950276541823821417182731568459772599681044367878260890076071099537189433530339856089652763925746738808514282701941366092984560926608044411796454888437654996179639144319162493973567313504355934970936638081789314314205181949974383771418598440558512914520255817259861681056322723552558966794428552703244128305348890325513153885620432195148716325870623937215029214849759074508871308157260520879891574777067606961321668218069659447955104043392607441242903820270557643555883299834916377494293730813433245570109588106535734576556232768791110113823134600585483980780459654123328993588699145360992235949148573592395643137201870891285537559659954956709183693214729414060963861253938507436687802183054653350904119857489159511068354193275254513229547995140461761373627617247160297068461157715249036335481255627849856624532021298165668910824931386855920658997507161728292097136322942313033910920388513255578440661337447549690256381511832378361539194720095701016190565232206995680713845813264363187832191980731927622920736127452764661878606618125595394502583084781357436080492404537963922945243150028990128324830056545539170360525074865684442638681379783520527505919020718597135825092165943917333374394725387253854880356847888280377644329616056390836863277751112167365349932163475357258648306377301342374342118837528549668421191027852804952475537519496693176593124482838955431298050588152886943785245128841982065070035040235018833212526994741952042175296922738003375750072679119143546313658496176268405160419839121347465777518099277798891702418531748478578426803468797590183077837749306984450268395356907299887170174621968514823134585082830269088570322796158033683976527798405736476649003214423178658193378475741802789258605697446881532305367639263118356482122869620869074532308076559621551434069320427781873824049562149511422369709575996469384359382861370825699733652840501283064240389981295128679496518401950589579628776869173938705017090417904394766608897158885309782420841541106338938248500382732907126047047165845488889928502508958893597510149185335876119296343554053411066307970238188402893675134764532670743551290473238843737035906513407035891211753377411532897856890833583474576229168567714348411781831839424858338202571007050994478371368342773673225756636316436626326744001396102838703719526924700017893743146416732695465484144592738232687549937514753930209470220816353859693847086953428159527052786601408700149083558149739096713204532083648287387184211590439302807331748500750336187148126584994879734484382083281527507376051919723754352511492030781935919078906634017853510347037571906429093959987228110554036362917528823907538534755303702049924533322727516674080746095680240794306424742632862054134006648763158419040134736640796634162781085910210528061215521853021005012022172990619808061071255622800878728396814997512184716260885438880814811517078319127033136904111105176886098514009391020287745748675379306945782326109173344081417594226824333249913299168669030835304008552478138035664483359749810794203603630365797230567308141571907639010018210726339824655744700080920591755109143053365456906221747965729070987276157063455761267268718068428216334630080289472567411642054800444257925205108153567003204202366453864212799288802396203256745914510021858484066594949273491548826403489952349722095079744905865061593784013311981531908756636143665659212989915495178059558008403309797117766236990458597337762626478294550397960108886751218795186533227637938511948291962232246504415450857869060343332015842882499732819785911111500160447178075321472769578445221638828278987887254867105102089272148293177867213098901146804904881353106669453634046434286002902161101766965457496482527655634586012398914453234887815153807352485767347468368375133415470620262498738748333283924271335375844404710410368610051706478206989864633726325795469089920989831579360828363961986926808552451331946574258039851408663409925971957035188265169799240966952479472590933042862246428116017996492701044096065422156019895442757829289704718660390427270921707834289566324916673876211734160564659319850658400402502100124323312714416215387697543988783907370990491392725203906061867829220055639352751879074572445804696902638609097636438075182625225121981911782588771605635002295627668556305231520432259743207189421695996789799432969530048274153948028197887813378425276356065023490311245290053995499212953976483645741282767837655686673777538011093085243669514697409194643625330815725209283100601150088745330292409526679286892815555327465000979869973103074672424222803633327059263345829584079966356988983800982397335007545495060315952873605424122161704425985021515088062071615698942658644923280413783556545222280433764032182040141451011786955135575306250415527557230300005606637158545845058204342020175801048693280475147333713571805298596558917317917006294073042026558959444881556502746929778174507086097933052803286408851330280858352679084929107514044501459582763110745793482570440143699371823633831765556212599458395645352137436675998812666214881229600063597736968368101677089710781940235051932767573453046746498496985857019960131767039558568542978473059069631601766172944293009785892130568470476442621366069367042323742966993875142781543241332849744088377964673003559420798422850712974466440571910550933547882046991457692714211038544154544300185804078752325144304545637607141415225953330006278994732108342853969366873006735694342566375536792001861013794331401648078098980621894530512757640730079399023425986019126613202750526483579985806274351286185043418080644928254601073303435377620818063019430154686631329979238742782899040953669886610652082792141088130326476123588015124444890519782897835306450480900656492831563499251344007701743182612085672365495508866129829804782444719191898462754517753269777203043928235609191565272434964170157922057888655434194561264411750045998601030552386900629951283269755893940525061526269106843294554268332880758914091362231975425513465017113267088150449808078068988138891983032207639250423018184264349108739737101250516619275279310764621177919204923976746818852745855022970137563686912758793702416167317018437603681892020532586835468755845620601431345298406209404142841149834472745176483810892665273556926054338680241890035239562103423841048368128543470250021865429116967448278224695957474234382103136777910360015203925386883154786752235104787967719136097285227009852810388490217975382548033895443125640742244262845367039949885361939451751072812238519568055488858603839477183518522094524705190225162887420257097362488114807191189399044444644726432175165708079037174397359033107584907142141362536614924198327559759672689301268089730181728642857950125280856854849434885588986360818811952797906220226984338999728811887433714394186858520240232856102716030093196285355394210758803767221678801815324581231676319313650651510409777588424765521318083108195658975335089093202882368839723703951729040013380761544578315686430973110041355505431860263611763642521514602726080744349308684997451360819646405071980259825634591149464897549518262647519195640142338664285897584931310044303490334926470427939644469956073662500066716873248641543831479677835574706335877875289781768908017493153282259177636946965840922290707205178363253465569326201441768121971562617493965446801035838560898334231713377316159500713243067897549101708455015647758180206713899432186259942536800665980942236589631880251918470817923953911184671619168997338276177547920716469923287828745744414048577553306135665673337951267802325597448357432913771171405018247204023332030933933609208365154315998127888240573217930812549075584186467451712209812218443279871077805338460750209181604334099466538532234320154661322172961397573471901885789606759817891539638942062997010207666429317550050780088038150988911615945495791090347776809453090577007690308866062501168826883462932316915577549281913480611679763047933675522080723554084612450490982451353462150496784930226107941299554902008327177878805995161061840140537844103960547372052985506860253376826128362179319927808909635791187936011589737953325533016388308190640492140099412428870921850192005074070159919867195759817210515047657257090602140367863506486287623852029585132183664444199088754571602685882445340222995885290241409061248819979467029304067511744995700508239571976882206166989265205843615207708122555384270915641877733322966218531416869450479974861771181210185396820415310156295971089257660486555883612136022417156758270649418545615425539443347610603870822625458021012969890461911594201055707757131837312848909284449496511804254365368875581271734497746011243426433952484349070288722537236768972139128821752796631650972704083476246321130454403052365620867525829478989506653976360001308063793528708125114708908943318282657091410639702217197588232360267908366012967490150985196519026171834111403195047236254297485137630233211690034127278667645650417847896052506563876136230929113032949544656998829722985515950724556649922121290194706081702580459649503410602498192499323471855007929155794408673770895166076798687936206201318400882656559469484465923369646664277867640172286117103801709537770011985202701088568095970232903667687793884126359380578360848874593482131293085566856593625501855534204586107975555489603032856843451120171173201550568212984518005591784763620433922076978848898925004840139356406365356424722118185513598202965330446702047999070573753310168814350079467519484217657926025108334669728396166585168898945000981592039932471064522248020792372233305295380787020130116363982216907360868953555703826132311392989095305274327516958486473357031504602739573315778751197146587354356490691520723010926681977537268639606261968345534799120169740411058747421257513640124400358930553745948384084392499751707388633165648606617939007835281233230711795703024034345501300921439830842344595209145404793397387008997203764087129710076509051306808246260874908525673530557471682972107362005917975832145393755153735655474861877630825561478064187752086705289977810928340843359945393964987775062505398479166337804919179499783172479319346793500233989241423934687937700720134851285576929949497073784901063040322932991801741301312106362432458181385646230231540102337842579165322231025356149764130317084519851186378105192376694354200555229013440968341671956924045109150563627885872832770477064948623969225145314461037326005531491977314460604804151597928160027262760898871164741852152886454487865868959037891697173668785362233119809620580886758678990538333922781860414288924083455232230410824069275118058987389672080443874393167264806454474637017051975208972522930260085571059107202745084833584295431605203569783210931111134065513776296722532625827468615761228135816465124554286762343655495001482386191492810991198424358198606792188251864217612369942431069141802220366175177574982990092617023539185800941257783429555646585039437725192586944953722592479606795209192529138839821307162055493148071151690915896304290597371951073178260417026513398603268432159706369844056690303045820268605819171858224081370121627999265382376326051640850220434488185509504703349016859455183728726906940022330186363561152968959628723435042292283492653935519971488806166261860413590098821090344645561536501851805336627475805783663412358577240653406326368103781135861169505699492335930901426069238406487463594956357540708447611680059269529058464152789473022350676939244880902580621983514174950602530604275369942853001837903093031400960520604684909454891319230034223534558336730877962425656619775827202729499857732158552303284564004543739910550421151875259742113479363992845409165657373324581743516251747811922022160284430296255799382115275714819166400947828810821558314071196740007529496888084514088230395893678151042763987547934467977585329655680001482438520897114003200674375899776879547363600897617852210784704259372297829575397628957364413944045904087952104829502631332813089317435764504535532437184267693591389995280930497701347256057931813123619595480749870068608426686067925972399767463217209103533183880820451412429853178918901254208976260701749432110048979980111515395515934675466860107648944965467510233143377826341344521470645327004705424847193195144661869228832928236752947592029783304452428232705019976764709142188435985798734230135012286267872528108392928066891738461481591929588030342766375934370884609703804383639722590491080652629794900152208168700621723076775253862650375998610595578012776932264178781987843712116113148707697137287466307515393953357294316239296141640579732724658880302631202973121547337879984810834184282755844490603783851877618469041922279647062043083135764870450865078927282449792665907129532399933284905716589567895014358387790501688416110537788720704986044157398497473135843096931787492539837586977290228412307695818366612542870858107545778832070954592427593252834377935627921516172019938787070538920853939995660116409954815079147377588910607503899236402109203364027644141267742302051855471`100001.01714067292

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

So we have the following.

enter image description here

   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}]

enter image description here

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)]

Although the MKB constant is slow to converge, I did discover the following fast integral formula for it.

Since the MKB constant comes from an oscillating integral, I thought about naming the convergent M2.

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].

New speed records up to 40k digits.

enter image description here

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.nb

That 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.

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 enter image description here

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,

enter image description here

                  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. enter image description here

Some of the AbelPlana records are shown here.

The following subtle changes transform M2 to M1.

we look at formulas previously used for the MKB constant.

I presented M1 and M2 in the above messages. Some of the formulae mentioned below are new ones for M2 (part 1) as mentioned in the immediately previous message and M1 (part2-i/Pi). enter image description here

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:
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract