// Copyright (c) 2012 - present, Victor Zverovich
// License: https://github.com/fmtlib/fmt/blob/master/LICENSE

#include <charconv>
#include <limits>
#include <math.h>
#include <stdint.h>
#include <string.h>
#include <fmt/format.h>
#include <benchmark/benchmark.h>

namespace std {
to_chars_result to_chars(char* first, char*, uint32_t value, int = 10) {
  auto end = fmt::detail::format_decimal(
    first, value, fmt::detail::count_digits(value));
  *end = 0;
  return {end};
}
}

// A fixed-point decimal number.
struct decimal {
  int num_bigits = 0;
  // Each bigit is a 9-digit decimal number.
  uint32_t bigits[100];
  static constexpr int bigit_bound = 1000000000;

  // Bigits are organized as follows:
  //   bigits[0] ... bigits[F - 1].bigits[F] ... bigits[N - 1],
  // where F is fraction_start.
  int fraction_start;

  void shift_left(int n) {
    int offset = *bigits >= (bigit_bound >> n) ? 1 : 0;
    uint32_t carry = 0;
    for (int i = num_bigits - 1; i >= 0; --i) {
      uint64_t bigit = bigits[i];
      bigit = (bigit << n) + carry;
      if (bigit >= bigit_bound) {
        carry = bigit / bigit_bound;
        bigit = bigit % bigit_bound;
      } else {
        carry = 0;
      }
      bigits[i + offset] = static_cast<uint32_t>(bigit);
    }
    if (offset != 0) {
      bigits[0] = carry;
      ++num_bigits;
    }
  }

  void shift_right(int n) {
    uint32_t mask = (1 << n) - 1;
    uint32_t borrow = 0;
    int offset = 0;
    if ((*bigits >> n) == 0 && *bigits != 0) {
      offset = 1;
	    --num_bigits;
      --fraction_start;
      borrow = uint64_t(*bigits) * bigit_bound >> n;
    }
    for (int i = 0; i != num_bigits; ++i) {
      uint64_t bigit = bigits[i + offset];
      uint32_t new_borrow = (bigit & mask) * bigit_bound >> n;
      bigits[i] = borrow + (bigit >> n);
      borrow = new_borrow;
    }
    if (borrow != 0) bigits[num_bigits++] = borrow;
  }

  explicit decimal(double d) {
    int exp;
    int num_bits = std::numeric_limits<double>::digits;
    int64_t v = static_cast<int64_t>(frexp(d, &exp) * (1ull << num_bits));
    if (v < 0) v = -v;
    exp -= num_bits;

    if (exp >= 0) {
      if (v >= bigit_bound) {
        uint32_t upper = v / bigit_bound;
        if (upper != 0) bigits[num_bigits++] = upper;
      }
      bigits[num_bigits++] = v % bigit_bound;
      int i = 0;
      int bits_per_iteration = 29; // 2**29 fits in one bigit.
      for (; i <= exp - bits_per_iteration; i += bits_per_iteration)
        shift_left(bits_per_iteration);
      if (i != exp) shift_left(exp - i);
      fraction_start = num_bigits;
    } else {
      fraction_start = 1;
      if (v >= bigit_bound) {
        uint32_t upper = v / bigit_bound;
        if (upper != 0) {
          bigits[num_bigits++] = upper;
          ++fraction_start;
        }
      }
      bigits[num_bigits++] = v % bigit_bound;
      int i = 0;
      int bits_per_iteration = 9; // 10**9 can only be shifted left 9 bits.
      for (; i - bits_per_iteration >= exp; i -= bits_per_iteration)
        shift_right(bits_per_iteration);
      if (i != exp) shift_right(i - exp);
    }
  }
};

void dtoa_puff(char* buf, double val, int precision) {
  decimal d(val);

  int bigit_index = *d.bigits > 0 ? 0 : 1;
  char* ptr = std::to_chars(buf, buf + precision, d.bigits[bigit_index++]).ptr;
  int count = ptr - buf;
  int exp = (d.fraction_start - bigit_index) * 9 + count - 1;
  for (; bigit_index < d.num_bigits && count <= precision; ++bigit_index) {
    char* block = buf + count;
    ptr = std::to_chars(block, block + 9, d.bigits[bigit_index]).ptr;
    int num_digits = ptr - block, num_zeros = 9 - num_digits;
    if (num_digits < 9) {
      memmove(block + num_zeros, block, num_digits);
      memcpy(block, "00000000", num_zeros);
    }
    count += 9;
  }
  auto has_nonzero = [=]() {
    for (int i = precision + 1; i < count; ++i) {
      if (buf[i] != '0') return true;
    }
    for (int i = bigit_index + 1; i < d.num_bigits; ++i) {
      if (d.bigits[i] != 0) return true;
    }
    return false;
  };
  if (count > precision) {
    char digit = buf[precision];
    if (digit > '5' || digit == '5' &&
        ((buf[precision - 1] % 2) == 1 || has_nonzero())) {
      int i = precision - 1;
      for (; i >= 0 && buf[i] == '9'; --i) buf[i] = '0';
      if (i >= 0) {
        ++buf[i];
      } else {
        buf[0] = '1';
        ++exp;
      }
    }
    count = precision;
  }
  bool negative = signbit(val);
  memmove(buf + 2 + (negative ? 1 : 0), buf + 1, count - 1);
  int offset = 1;
  if (negative) {
    buf[1] = buf[0];
    buf[0] = '-';
    ++offset;
  }
  buf[offset] = '.';
  for (count += offset; count <= precision; ++count) buf[count] = '0';
  buf[count++] = 'e';
  if (exp >= 0) buf[count++] = '+';
  *std::to_chars(buf + count, buf + count + 4, exp).ptr = '\0';
}

double data[] = {
	6.29144216066358026e-308,
	-4.55415372971565510e+91,
	-4.77654225732092549e-142,
	2.82472053605216201e-151,
	-4.81033353457174864e-112,
	-1.54734077720000547e-198,
	-3.74835475850786866e-287,
	2.96720275234264948e+78,
	2.24237291022756926e-140,
	-2.87612934208601528e-252,
	-5.08709612739053546e+86,
	-3.23947860441736387e+99,
	-2.21074957211681698e+39,
	-2.76786087342203990e+235,
	-1.09063657843620561e-125,
	-1.20793800668260825e-262,
	-7.77421093612891233e-293,
	-1.46065762226347122e+10,
	2.03148372675882155e+136,
	2.70238113946880942e-74,
	-5.10945835775107653e+247,
	-1.12422080271987195e+223,
	3.47926980119339958e+286,
	-6.87311141938484082e-79,
	-4.54939756683820153e-166,
	4.03171543726861157e-165,
	-1.24406477058647349e-77,
	-8.52567746217984191e+150,
	1.08987028547717175e-76,
	8.58512244132744105e-265,
	-1.39288797781114402e+108,
	-4.92131086725651910e+198,
	-2.74688585346141389e+99,
	9.01178118424645786e+149,
	2.44498976069769846e-203,
	2.00294284953161119e-43,
	-1.49467722888894894e-220,
	1.49047383936805095e-21,
	5.77048177086516349e-257,
	-1.88268201721914436e+235,
	-5.77577774053865345e+05,
	2.80619408527983287e-86,
	3.62198750628677664e-304,
	6.83914080106731462e-256,
	-8.60788595644088424e-252,
	-2.49147579398885529e+78,
	3.05309908211473325e-07,
	-8.05298769740317707e+180,
	-6.27845871112339544e-297,
	-5.78436160545472721e+210,
	5.85361268207284190e+146,
	1.01253107794083997e+280,
	8.81984841997499254e-15,
	1.04212680285636070e-69,
	-6.63086643315633065e-28,
	1.66033690250843010e-180,
	1.38197477337375301e-241,
	-2.10652632087657711e-306,
	-1.54363777274832973e+182,
	-2.40641723999677870e-01,
	-6.17805397730354686e+21,
	-1.48076823112227704e-25,
	1.22541838415280131e-36,
	-1.62234730379570739e+191,
	1.19693162513251025e+305,
	3.75686458428097067e-89,
	3.53633194510659366e+196,
	2.62869358521482505e-290,
	-9.75753044083513497e-237,
	-2.25181738675274305e-275,
	1.44299958396277283e-48,
	5.07044717794641899e+271,
	8.18042048158808629e+194,
	7.26457877578627524e+136,
	1.97084320573854671e-138,
	1.88227733813546488e-106,
	-2.15278957418935726e-118,
	2.50329231111947149e+07,
	7.43485921437584496e+09,
	-3.71032482494698149e-170,
	2.21112885490327208e-147,
	4.37126789625338593e+223,
	7.41400005501540794e-252,
	-1.10210436990825225e-142,
	1.05090213840596765e-272,
	-1.51840840802036981e+261,
	4.95769859704946709e+66,
	-1.50773799188439127e-187,
	1.83137154045455869e-188,
	-8.73904834868624135e-244,
	4.59270276541012258e-142,
	4.68829156711560073e-31,
	-1.22690515921388596e+185,
	-9.00399167139393641e+158,
	-1.38868725709152819e+294,
	-3.41382127739513848e+260,
	9.33484967463825710e-138,
	1.02382385032791085e+288,
	-1.52155038937288232e+12,
	-5.74262730272483167e+193,
	1.70464121476536049e-260,
	5.81848041162066304e-10,
	-1.33736403742742048e+258,
	1.53736987479568180e+78,
	-1.23378570590666101e+58,
	1.70958083043315088e+171,
	-2.90589207708078754e+233,
	-1.90053137950775903e-140,
	1.28353279148382976e-200,
	3.60071509138312771e-184,
	4.03872059288218174e-80,
	3.74323069619901681e-113,
	-7.62388725644711813e-137,
	-2.65194533478874949e-119,
	-2.11839973643794350e-98,
	3.46582362452529890e-101,
	-4.26709661413847235e+144,
	4.60876771000081446e-149,
	1.27291315655242960e+25,
	-1.70040368229375123e-55,
	-2.72844453882117440e-222,
	-1.40571707665531276e-67,
	1.67835612145153782e-11,
	-6.82249702781492734e+144,
	-4.82974232545723464e-72,
	3.83560624089875399e+235,
	-7.03062000413384600e+15,
	-5.58659233022576300e-89,
	4.84612791332227385e-133,
	-1.01037061111964938e+33,
	-3.61872575704992887e-259,
	-7.58614255880414414e-283,
	-1.54575926125401107e-83,
	1.55549590826640558e+184,
	4.71874194563134235e+272,
	2.45282932493385135e-147,
	-2.93936893221231355e+150,
	-2.59519929868048336e+81,
	2.58379883760722823e+151,
	1.18890738828980964e-120,
	4.78183438060704421e-213,
	5.39866011301360756e+224,
	-2.12830895142036850e+30,
	1.30642153074133301e+11,
	-1.16766140825521320e-249,
	3.26803616943610575e-59,
	-3.31325602279472773e+25,
	-1.92896049975944600e+102,
	-4.70573139892366257e-252,
	-8.39657190181954756e+114,
	-5.70947640724320349e+229,
	5.23640893023937448e-48,
	-2.70362031291429673e-250,
	-2.66701901986417563e-176,
	2.45394653020963921e+69,
	5.48302783953925431e+299,
	-2.09881148043571899e-309,
	-8.77174376086405468e-156,
	2.63533107821944602e+204,
	-1.86661700606387259e+191,
	2.95575659132876076e-128,
	-1.14440383738854857e+58,
	1.70534475140570579e+190,
	-1.76803860339219980e-16,
	8.58975172787168889e+194,
	4.91835402064109974e+22,
	1.43231590640164000e-85,
	-2.00888278368393771e+104,
	-2.11871502337297093e+102,
	2.82771884233192374e+239,
	-1.98278036874549835e-118,
	-3.76741372935762358e-118,
	1.25887687988386049e-178,
	-9.94898778745785753e-208,
	8.10042091618905882e-282,
	-5.67027742572698134e+168,
	-7.03472536799552294e-162,
	-3.26163417061057976e+236,
	1.39237112297709989e-155,
	-5.99884855025070577e-145,
	2.51486114856422798e-173,
	3.93810675051033786e+305,
	-3.91902067548388031e+137,
	1.49078617209743400e-120,
	1.61444084793318524e+129,
	8.39905714494381557e-44,
	-7.06174103295307264e-98,
	8.33393019040292417e-100,
	-1.09170827352393197e+223,
	-2.16290046263403412e+168,
	2.69013634210392923e-223,
	-4.50403881558906115e-13,
	7.37149618727104645e-262,
	-2.86906004253235503e-267,
	1.02348374300786457e+06,
	-8.96531999853722446e-81,
	1.68662520364543365e+165,
	1.06385110685454648e+148,
	-4.74450162040093259e+29,
	-3.16285839364153183e-204,
	1.96072596808832216e-148,
	4.52835937267604903e+92,
	3.08460919490459329e+00,
	1.09271167748548982e+105,
	-6.66290862415169196e+188,
	5.09314516546258920e-144,
	3.23945530895462207e-93,
	4.59131418772706427e+19,
	-6.75795710689210311e+142,
	-6.09726287309725953e+290,
	-3.93558251487437402e+12,
	-6.77730814690829435e+90,
	-4.86705520158456711e+126,
	-4.06158858039087716e-14,
	-2.15714468055103136e+130,
	-2.55390551756013466e+80,
	-2.80121048299860788e-226,
	-1.34279234614981374e-68,
	-1.32976862734765878e+218,
	1.84840015833091268e-44,
	-3.47869397778199745e+111,
	-1.57836914440764861e+229,
	1.20825172713078932e-190,
	-6.78869286294307390e-270,
	-1.38317180727845734e+253,
	4.82105149173140654e-30,
	2.87276582005929902e-06,
	-2.79944542356908413e-07,
	1.44617196343514753e-272,
	1.69887114893068765e+277,
	9.99832408583984572e-82,
	-3.26759886632344449e+53,
	4.73797376845342551e+263,
	-1.32561960481420391e+13,
	-3.43288551119714010e+155,
	-8.14572126474785823e-141,
	2.54630637207407057e+248,
	-1.04403367955195898e+210,
	-1.00745737580069937e-24,
	-7.20598054709577379e+147,
	-8.31894686966592332e-247,
	-1.03200641957181311e-63,
	-3.75733371660706733e+254,
	-8.18508608421076634e+196,
	1.75385519873894074e+84,
	1.28088869978930773e+262,
	-2.69019210299837247e+281,
	-2.97014370505379242e-19,
	4.33963898567243021e-297,
	1.56625930432448469e+276,
	-2.59160290069293929e+202,
	2.06870258318715657e-68,
	2.03091838019939679e+105,
	-5.57117806097694344e-25,
	2.80121932208234711e-164,
	-7.67168729871939055e+158,
	7.08306199228805108e+43,
	9.36555837237114006e+139,
	-2.09459422753865497e+36,
	-2.10153671045541061e-252,
	3.70126285944683669e-292,
	-1.27739918585777025e-181,
	-5.89007247588569903e-190,
	8.92725175581938153e-160,
	-1.23608870750039945e+42,
	4.39153380940024869e+64,
	2.06063132544323589e+305,
	7.35593161042137211e+00,
	-1.75624418478424365e+286,
	1.52153891699251200e-278,
	1.06868497106660654e+229,
	3.87267822942898704e+212,
	6.03325725239387016e-80,
	-3.39722009994094077e-68,
	2.80703178209470071e-11,
	-6.73466066836980434e-129,
	3.24854897549104993e+62,
	-3.17879411507267679e+78,
	-3.60904359344796384e-261,
	-1.36975286846482144e-64,
	-3.10257964343184376e+09,
	1.14381228693169318e-26,
	-5.09649607256535463e-33,
	-2.76229381001469385e+220,
	-2.30401891363472960e+27,
	9.31831352720427946e+280,
	5.43707973770615390e-302,
	-1.43878085563693054e-148,
	-1.73588853726617094e-103,
	-7.56956985149853159e-81,
	-1.42026844040404066e-296,
	-3.48235287613809073e+269,
	3.15272706985113118e+06,
	4.93771855638368914e-277,
	5.81161979970637478e+240,
	1.82692512711214188e+282,
	7.22925071654697848e+50,
	-6.24424422635946485e+02,
	2.76238191819324984e+99,
	2.51301122552303981e-160,
	-2.99135778394139666e+279,
	-7.76547532677354638e+36,
	3.01906620915397744e+46,
	-2.18138604280087455e+181,
	-2.15282917879297455e-266,
	-1.01908535213662891e+110,
	8.97604372968956799e+176,
	1.19392906215514596e-262,
	-4.40799807376178345e+115,
	2.92782822799717042e-77,
	1.53919793739443821e-189,
	-1.00203316890837125e-11,
	9.11149669253135569e-141,
	-2.86226986590413481e+168,
	-1.78147742871363197e-66,
	1.50027899622499544e+287,
	-9.21777761237333536e+08,
	-1.16548199868388848e-140,
	-9.97888622677140776e+163,
	-1.97896183392688936e+165,
	-2.23023475270052513e+291,
	4.08027443548110092e-87,
	6.06976778600273719e+111,
	4.75962087112983445e-133,
	-5.18578405940479548e+213,
	1.83519046100383200e+16,
	3.73013431573031426e+203,
	3.96723609520024826e-274,
	4.11278458794714010e+228,
	2.47340394285408259e-109,
	-1.79670073210289853e+112,
	1.65773008835794371e+232,
	8.68928039818230778e-104,
	-2.61853547319792167e+23,
	-9.19519478099591244e-268,
	-2.12614364758559417e-287,
	-5.06965082103534698e-174,
	6.05995373518359015e-07,
	2.87625265658854238e+235,
	9.26717618345261819e+109,
	4.14356164889392000e-11,
	2.58912642221187386e-24,
	3.28444723531759720e+261,
	2.06458301458665944e-124,
	-1.94551654499959579e-36,
	-1.92793822009993794e-156,
	1.00375264194684075e+214,
	2.60610266569422549e-93,
	1.23569023318188775e-127,
	-3.58191460923203691e+202,
	2.99575600599365462e-159,
	-1.48041574772179710e+295,
	9.25882590443694307e+162,
	5.30660197393106506e-201,
	1.61890535082099621e+215,
	1.39975357973476519e+244,
	2.16056731782484422e+230,
	2.33979605806764567e-203,
	1.05049165365484096e+235,
	8.05841353800163543e-87,
	-4.19817138227512284e+205,
	-3.34752976544448932e+102,
	-2.37007884505784737e-07,
	-1.78140201568551099e-128,
	-1.89125214859885087e-268,
	-2.47143486439146465e+92,
	-2.72249089576384051e-99,
	-1.14232659633312225e+09,
	-2.07498373957699820e-95,
	1.02310624440455650e+33,
	-4.27962383672371900e-109,
	2.94434825582536414e-240,
	3.79648396639090641e-262,
	-3.11320319517248012e+108,
	-9.49855591105553915e-70,
	1.49689464359417726e+259,
	8.18752360442257353e+106,
	-1.84573430072684832e+144,
	-1.66104952873358511e-06,
	-4.91550850431715519e-220,
	9.63929644885303690e-250,
	4.34046478587529081e+23,
	4.71621060910442317e+114,
	-6.69766879804749656e-254,
	1.22263466042811945e-10,
	-2.69813050907857183e+181,
	1.76256885470656981e-105,
	-4.29460620329981223e-291,
	4.29961987883651563e+264,
	-6.17225130310568517e-292,
	-1.47444597270700108e-54,
	-8.00978586970691066e-191,
	-3.37850860859293997e-80,
	2.95784278269990996e+83,
	4.85062283216902752e-300,
	5.40640404070699847e+230,
	7.34892273162160548e+70,
	4.61208548410893089e-271,
	9.13054046860257615e+239,
	1.98360328897464686e+111,
	6.33034439301978581e-15,
	-1.13742969504218383e-248,
	-8.89898155462114949e-204,
	-7.57657335524313938e+236,
	9.60780277377143399e-276,
	3.91948199405014380e-118,
	6.11732684909761783e-183,
	2.33398492330570423e+257,
	1.18312883450024787e-236,
	2.10959981145815667e+53,
	-2.32570181263896575e+03,
	2.21393186736948513e+298,
	-1.42514238610107931e+82,
	-1.80802181360448733e+196,
	2.51447361415050027e+209,
	1.72114324330952752e+183,
	3.44056039709274702e-58,
	5.25223741114470211e+120,
	2.97456903341425075e-43,
	3.11559659139392825e-35,
	-4.92494894980697102e+216,
	-1.10377574364866901e+84,
	-7.49376308815873805e-128,
	2.69034216693558714e-79,
	-4.97533552048319399e+236,
	2.13841936617670044e+206,
	-5.59787790148595394e+116,
	-3.85636206794909594e+03,
	-2.01940157186804665e+273,
	-2.22566303792877177e-38,
	-2.97683946569257634e+128,
	3.12868042720702107e-13,
	3.90179867612989380e-225,
	-3.74838728692358165e+216,
	-3.32266479316415749e+294,
	5.18056794115958466e-305,
	9.89412091931586701e+02,
	-2.81930195843877993e-214,
	2.48085665724570177e-05,
	2.77858891067026651e-85,
	1.70521057344004138e-47,
	-4.82100813308498410e+97,
	-1.49158997985600073e+45,
	9.74226083523219733e-307,
	7.06187613503782742e-236,
	1.58570766981725700e+52,
	1.28503199896922385e+276,
	-2.67929829487929416e-124,
	6.81608150467969527e-119,
	8.12878501012786446e+220,
	4.23281564947419732e+282,
	-7.34972201807935889e-62,
	-6.49137153136482465e+294,
	-2.72940998251526627e-285,
	-4.83235420245500976e+242,
	5.63260109796492018e-170,
	4.48503562916205440e-141,
	2.42052575561465706e-82,
	-2.77947060743684532e-34,
	-3.61687865595068641e+44,
	3.13408444028321385e+08,
	1.91465521005845233e+276,
	3.91195215063048224e-129,
	-2.49940627702866465e-87,
	6.57879393423313099e-94,
	-7.90430926923496216e-283,
	-1.87294948017614446e+186,
	5.63979265071558988e+300,
	1.24230137782924303e-298,
	-2.43877106121862197e-01,
	-9.96256184935562537e+228,
	-5.31719715059230536e+202,
	3.85294911348816737e+150,
	-5.37642728812242215e-122,
	4.56499701492021239e+231,
	2.71069160586245403e+208,
	-1.18538514785366787e-145,
	7.65899057472877863e-153,
	-1.23956196826669404e+157,
	-6.25187854381610042e-128,
	5.12432736733135042e-23,
	2.77203396409991690e+160,
	6.06793757089664937e-174,
	1.53904989007847944e+98,
	3.44654139379101404e-218,
	3.02284797133009737e+169,
	-8.62195212723658133e-259,
	-5.52363021411332650e+44,
	-1.93010201103170122e+269,
	-1.77956247240021799e+208,
	2.30843048315922463e+132,
	-4.14730591510155931e+282,
	1.11287029171865648e-130,
	1.11013728508710489e-151,
	-1.53204375017757044e+82,
	3.20497821036145058e-144,
	-7.78784400449431574e+86,
	-1.65738269518213066e-62,
	-2.43971016166972399e-185,
	-3.30636573171648082e+208,
	-2.69247350703152979e+109,
	-1.37682426825272907e-224,
	3.46442435434738130e-25,
	5.14224251681535979e-70,
	4.04745832982433250e+140,
	5.18731097123319447e-78,
	-9.85321687767253458e-251,
	1.72860592061724025e+75,
	-3.39832353579516208e-133,
	1.13497869207450770e+148,
	7.51163892195991821e+02,
	-9.14696006416998662e+293,
	-5.74409305701716515e+91,
	-1.35746159302608880e-74,
	-5.18481400992933850e-297,
	-1.13982816110832491e-13,
	-1.58728199222962598e+121,
	3.30689212055399580e+238,
	-1.58642039357994176e-169,
	-3.83637896302715431e+145,
	1.42917047926944737e+171,
	4.88081984418392352e-94,
	-7.42493941234103292e-45,
	8.43994414875647732e-279,
	-2.08100673073041847e+143,
	-9.63403554668319200e+15,
	-8.89619518852018821e-169,
	3.64749137634881121e+92,
	-8.61827478768013764e-286,
	2.27788063474032929e-215,
	-1.88424747681172891e-167,
	1.75051150915389961e-267,
	-8.45886765439411762e-263,
	3.73942032760980149e-88,
	1.71243933288822546e+233,
	-5.74972914020648631e+68,
	1.09240889608702280e+16,
	1.11458546805130883e-169,
	1.52307653318854792e-55,
	1.95973087712652972e+302,
	6.10716972973746452e+241,
	1.51919288392525339e-24,
	1.54742817213348196e+272,
	-1.81881094691941458e-280,
	-1.60324166046816482e-223,
	8.55483738315648252e-188,
	3.14839351920622892e+102,
	-8.59393453273848793e+73,
	6.97890821375940648e-23,
	-1.07251390104708741e+256,
	-2.01488547921813997e-187,
	5.03176790840882695e+23,
	-1.26604631600113207e-188,
	-2.16918645328104162e+02,
	1.17647731418538289e-297,
	-9.52258445151039384e+140,
	-9.27050119153339875e+188,
	-5.52197856524896379e-46,
	-5.28605424036174654e-267,
	3.40843571293014354e-28,
	2.65027316149935625e-269,
	-3.23143316906191520e-292,
	-4.15687117508382011e-34,
	-1.01209583584678137e+114,
	5.89777671590185849e-126,
	-7.22483228631066072e+279,
	3.25434024694549326e-158,
	-7.36437269473624973e+44,
	6.60169647440466770e+177,
	8.61994457242042923e+129,
	-3.01346225365864157e+04,
	4.12978927247346371e-261,
	-1.06424087403606486e-124,
	9.98192303269832833e-104,
	-3.64208148465980777e-118,
	6.67633407061781566e+122,
	4.20136608857649339e+128,
	-4.01858507963746188e-193,
	2.48442159550155948e+287,
	-2.45498108856454670e-98,
	1.88983207230217228e+177,
	2.06710265920117334e+247,
	6.82041555743800878e-85,
	5.85191194189526605e-123,
	1.78939918140625370e-253,
	-2.80683125609634487e-58,
	-2.11920679112572308e-52,
	-2.74871086186113523e-73,
	-2.05198818372599501e+292,
	-3.97242510698979047e-233,
	-1.38723234755771836e+92,
	1.47385741349397739e-228,
	9.11676112417001299e+151,
	3.15462584221733534e-152,
	-2.23797024425150953e+250,
	-3.30146691077884803e-185,
	-9.19716656593815640e+265,
	-2.50645763929623399e-176,
	3.90178159012194664e-199,
	7.87602043713374572e+211,
	1.46824732507749576e+102,
	1.94454663735585624e-196,
	-7.22422686225519103e+39,
	4.20410067907390137e+11,
	1.89224159328300598e-174,
	-9.61857406305890352e+166,
	1.89635889700874436e-91,
	-1.14569464958181011e+82,
	5.57174152662895016e+82,
	1.57378679934799149e+205,
	9.09587563926327357e-170,
	-7.35143674280487837e-60,
	-1.20654229310878191e+03,
	-2.56901451068289311e-71,
	1.20030769032899047e+58,
	-5.79226938432930490e+214,
	2.60646687311654086e+223,
	1.33389625454152116e+99,
	-5.46629114100999161e-276,
	-2.17886708173588755e+243,
	1.06395964508363033e-186,
	1.73549767338624977e-135,
	-1.35535769333479615e+287,
	3.05294821668695366e+75,
	-2.69176157175393389e+67,
	9.21053207430081438e+37,
	-3.89273123746083004e-206,
	-7.18617376327146144e+76,
	-3.92938627257855026e-268,
	-7.59713268276203304e+266,
	8.33533656663579149e+183,
	7.23404258148684087e-03,
	-1.12158948563808129e+190,
	-7.17821215107389363e-04,
	1.06520063574773953e-145,
	-2.07514460447847271e-32,
	-6.40385660584407720e+223,
	6.88110201922022827e+117,
	-2.06140753566055508e-114,
	-3.16825854854499378e-281,
	-4.34885111244716012e+117,
	2.54111302038498951e-241,
	-9.72711409328646870e-154,
	-9.28419154353155434e-268,
	-1.14057985064905378e+280,
	-1.27378624027418139e-56,
	1.48107685914640555e-149,
	1.89479232170831224e+00,
	-1.57527380115865788e-54,
	4.50426171830924993e-81,
	1.47491970260914127e+223,
	6.52294071597592890e+92,
	2.84600960884278416e+272,
	-2.79108192680438488e-267,
	-6.34156693618964218e+06,
	-1.54557186061750130e-75,
	-1.14131628429364579e+110,
	-1.98972915863721970e-199,
	1.89695204725012420e-133,
	1.69542596646381740e-21,
	-1.42734146561874512e-130,
	1.51776763201253356e-63,
	1.59622754933998216e+138,
	3.61162072065644727e-245,
	4.84891930832175999e-83,
	3.36844996193085637e-308,
	-2.99701288612427409e+178,
	1.18263682533640662e+01,
	1.15064342201734459e+275,
	-1.04239093512069387e+06,
	-2.72835116098812353e+272,
	3.66389683744125652e+81,
	-3.48871408793614735e-214,
	1.89193117874033728e-02,
	-1.07617056650770025e-92,
	1.36112111026856958e-253,
	-5.49229959557959562e+291,
	-2.64519418406687140e+08,
	7.50878102886133664e-170,
	2.06305599463074094e-259,
	8.59292364968205781e-222,
	1.41264760039519830e-224,
	-1.62883816849972162e-140,
	-2.20286504293339077e+21,
	-1.70702432286977625e-205,
	6.84011230870181760e-218,
	1.08287692068862297e-136,
	1.87198692180896949e-95,
	1.48482276215816701e-13,
	-1.39900140137341839e+204,
	1.29383414928424758e+195,
	-1.74944054010806913e+145,
	2.06448603411108254e+116,
	-2.98013347154950856e-61,
	-7.61291555240843537e-263,
	-1.23307699807212894e+146,
	3.34425909542686011e+302,
	-1.01158813245917384e+34,
	2.81581207185509401e+197,
	-8.73095933969843730e+192,
	2.05016278864650097e+111,
	-6.65129376363133659e-221,
	1.56663101541377272e-15,
	7.26954162184409383e+56,
	1.10424116004147672e+184,
	-1.11555432697193709e+292,
	7.37475268979313924e-106,
	3.34875385559738964e+143,
	-2.98979684591496473e+246,
	5.06015197670287483e+147,
	-6.54278695350300214e+224,
	1.03951475513486493e+253,
	-5.16151019155669285e+276,
	2.34647900015169597e-268,
	-5.43428022584920171e-174,
	1.44658809160852389e+266,
	5.20621195556852802e-100,
	5.78770031401256726e+115,
	2.94357998380524830e+163,
	-3.09741437694471014e+291,
	2.85618684513219848e-286,
	2.30330740888442233e+154,
	3.09086762095302319e+196,
	-3.89999295002489497e+272,
	-9.94129862644163927e+216,
	5.11578146685230273e-164,
	-1.45338899859984371e-19,
	-1.59484148591525091e+289,
	2.12587056107779797e+204,
	1.85939738889819104e+06,
	8.66540038217960100e+23,
	1.90143160146781066e-298,
	1.17008991193068061e+172,
	-4.34678102482243617e-305,
	-6.71347377674289292e+99,
	-1.73261560369475089e+75,
	6.94029489777232760e+246,
	-5.41114243275464789e-298,
	3.65091463345555939e-04,
	-2.95871018644286013e+157,
	1.93701504803866207e+44,
	8.04572530829898844e+78,
	-1.95202016537142199e-281,
	-6.34332746531026983e+192,
	7.23750641320166591e-164,
	2.75171878200806158e+160,
	2.17921093104589756e-228,
	-4.84856439675300981e+139,
	3.55595291815493071e-51,
	6.47650889406934438e-91,
	-1.07121622526424769e+285,
	-2.06978595985849263e-182,
	2.08381254380155878e+232,
	1.19747014228467483e+101,
	3.69674107311745111e+214,
	6.27565719499446272e-250,
	-2.51226792073224812e+226,
	3.02772658213894131e+116,
	3.00233716162629306e-292,
	-2.86077598596033069e+229,
	-1.03072280035842609e+24,
	-2.89121392751218356e+135,
	1.38886162925884081e+78,
	1.59073555251688132e-155,
	-1.09900875239777674e-28,
	-5.75056767149115477e-299,
	2.16227158520956072e+150,
	2.14914592196537324e+258,
	3.36315507671545703e-164,
	3.71993788664298472e+66,
	7.57213661164916951e+93,
	1.44230769450936240e-51,
	-3.34277682100279186e-107,
	-2.39204319888231921e-173,
	7.31240347092352102e-226,
	2.25469672626250223e-241,
	3.31370326355566985e+247,
	-1.45643498196901147e-109,
	-2.49445035387121580e+271,
	-1.50527954172772273e-121,
	-1.22027358815246770e+227,
	-6.72754797142339365e-117,
	-6.56910362832184827e-84,
	-3.14222705683789522e-06,
	7.90430328605459231e-294,
	1.48816830695023983e+185,
	-1.92306223769441652e+284,
	-1.56545693060780833e+127,
	2.88540553920749959e-110,
	-1.81924992905077148e-275,
	-1.10113465500503652e-82,
	-1.42410308341116471e-297,
	-1.98294760101486666e-146,
	1.20526777424536228e+23,
	-3.46172884109483104e-145,
	9.41479503674050629e-221,
	-6.10910021067367863e-50,
	-4.25976862996850089e+54,
	-9.51373613786442445e-22,
	9.77775037059648789e-198,
	2.34508540075727386e-261,
	1.22421914605480682e-171,
	2.47498196535058855e-241,
	9.78649528840284952e-14,
	1.61375940535918698e-306,
	-4.07381111739411752e-274,
	2.51150817735376187e-306,
	-1.27165634240999465e+76,
	9.54817366880509778e-95,
	-1.17607049897252430e-87,
	-2.95066388777242390e-260,
	-1.09801016622847079e+30,
	-8.43329579108150797e+93,
	8.96653729686052066e-169,
	1.71161189395402297e+288,
	1.02536954848814591e+171,
	-1.26680130389739438e-305,
	1.94695934302138952e+239,
	-1.96802025456675678e+132,
	5.57221739908361100e+174,
	-7.25571571116425779e-121,
	1.49861570791412508e-233,
	6.26813509505551248e+66,
	-7.67046653496879113e-13,
	1.62570524859595137e+96,
	1.85948578673596723e+195,
	-2.54524431490494325e-224,
	-1.70377260816119773e+206,
	-3.19716303002087080e+239,
	-9.11829499237147577e+85,
	1.92615239562851649e-264,
	-6.40425549064915839e+63,
	7.70298379422216754e-184,
	-1.08641732432289929e+210,
	7.34809543938400547e+106,
	3.69444965165271378e-186,
	1.52605296697237130e+271,
	-8.10055952044090569e-199,
	2.85796493843660141e-295,
	5.40872330731224632e+108,
	-7.03589514400941197e-17,
	1.06182967220061526e+290,
	9.49001627336532769e-14,
	1.04396874348756235e+213,
	-3.25452705664857228e-165,
	3.11170757758411340e-144,
	-2.46371434418732836e-146,
	-1.35544432829378247e+07,
	-4.13240235505003862e+212,
	-6.14028421644195748e-213,
	3.10698921116507241e-207,
	-5.19552584613889326e+207,
	-3.55607953404507942e-60,
	-1.37756601859037164e-195,
	-8.97682214563564426e-81,
	-2.58882809078968025e+203,
	7.87174207534782309e+225,
	2.90265054247204062e+253,
	-4.89978171540135486e-48,
	-1.97477419127478332e+282,
	5.01579983196388757e+44,
	1.71731674114589377e+52,
	-1.09931078181585927e-119,
	-5.11432372184274537e+237,
	7.21443373636800458e+238,
	-2.55689824029818684e+271,
	2.43496371249594558e+92,
	2.20404945371950391e-100,
	3.10155086922417043e+291,
	-2.06720119647121427e-230,
	2.16730363167300926e-273,
	4.60060192357065420e-253,
	-2.90328384045075679e+111,
	1.09368533765462227e+161,
	-9.27643743764265982e+43,
	3.28229723461310636e-260,
	2.50273020788327643e+45,
	-3.63622627990634655e-249,
	-4.99569307992493740e-156,
	6.51963207488567094e+86,
	-6.23623667681038423e-267,
	2.21710609103790568e-104,
	-4.24268717739501602e+227,
	-1.55919976433885082e+232,
	-4.73633003444709877e+126,
	2.07732506402981686e-290,
	-3.02960443928975899e+167,
	-6.07478473469517580e-223,
	-6.94098820279154130e+27,
	-2.58001492391757284e+107,
	-1.33560426739257964e+188,
	-1.61249127910271505e+91,
	-1.28395199637047273e+114,
	4.72770733305260439e-99,
	1.69461934788372927e-53,
	5.53233222206640428e-171,
	2.00310309243781789e+250,
	-8.81632391010946481e-01,
	1.68306824256981278e+213,
	8.86736129878722891e-213,
	-2.72081926148661222e-37,
	4.23863379912496833e+273,
	4.32077891694852813e-13,
	-1.19416535352467518e-192,
	2.67713949088878425e+227,
	-3.07929908522330614e+206,
	2.17071017154477685e-131,
	6.73109391631950737e+82,
	9.58193383666179062e-225,
	9.82191743572616883e+235,
	2.01339699268712354e-53,
	-1.97855714432266999e+69,
	-6.63946524265193013e+123,
	-1.95446726131866444e+89,
	-3.58002880229447510e+236,
	7.43860318915476261e-55,
	-1.55981218685901403e+184,
	4.31315487080859105e+278,
	1.09060382617877620e-42,
	6.55704590812437121e+296,
	1.83044016592052902e+211,
	9.95955366763880224e-26,
	1.65420692378952725e-22,
	2.29539511859101100e+24,
	-6.10877578296394576e+270,
	-5.54293188098477726e-110,
	-1.28612841435522443e-223,
	2.01786426600927100e-114,
	-9.90793691498120741e+20,
	-1.57824420607968522e+307,
	7.99785428119780211e+41,
	-5.53831503796149055e-55,
	3.78775083773659787e-197,
	-7.19749208058442612e-205,
	1.56247694642825773e-211,
	-2.44468715249245965e+180,
	-1.10709473801589909e-38,
	-8.51363516106253032e+181,
	-1.57067173576806943e-271,
	7.02219739147148192e-65,
	2.53767717726049665e+237,
	8.11369529679946686e-130,
	3.95594012356925497e+158,
	1.21238763485135919e-78,
	-1.19715562732113804e-143,
	1.79103654521659387e+199,
	-2.75675913704618657e+163,
	-2.10174005579367358e-29,
	-1.98997277323719999e+167,
	1.67828856743733135e+148,
	3.84102940739075253e-19,
	-3.89321841439989101e-45,
	-1.37004649796552469e-56,
	-9.34624225459681426e-235,
	1.43342981584121965e-257,
	6.72176970728785927e+164,
	2.55696763586816903e+29,
	5.17964440056027426e-33,
	-5.09042507668504257e+137,
	3.23985202835130070e-88,
	9.69512884736032557e+28,
	-7.50006363959608337e-54,
	-5.64858032202458337e+75,
	2.54167226232166931e-83,
	-1.69764744370044600e+20,
	6.49065894760965348e+211,
	1.16041999970173877e-24,
	1.87990163648632636e-170,
	2.92183795077053673e-130,
	1.35783208832015794e+151,
	7.44485126344544301e+197,
	-2.06058878905981040e+153,
	3.05410214935053462e-135,
	4.50614114430527700e-09,
	4.97935234026735380e+166,
	-8.36684968099638927e-80,
	-1.78717308319387915e+182,
	4.46730312087691537e-250,
	-1.76854079280704273e+43,
	-1.91994590593143739e+06,
	8.04995229608573570e-179,
	9.82569134934391253e+114,
	-2.12637352098577230e+03,
	-2.16206612316205926e-277,
	4.60794896254128540e-65,
	1.67504200794062932e-302,
	-2.93925670087365734e+211,
	2.52777959275273144e+287,
	-3.20363897116873970e-171,
	-3.19492321081394557e-228,
	5.92946873908334339e+254,
	-5.20516548037060158e-279,
	3.34629203437931851e-173,
	3.07931545205420409e-170,
	1.93620069829513093e-113,
	-1.98860152255882081e+171,
	9.21241279895555847e-104,
	-3.06751469759580446e+05,
	-1.15117940866146892e-149,
	-1.52750066741774462e-119,
};

void dtoa_puff(benchmark::State &s) {
  size_t i = 0;
  while (s.KeepRunning()) {
    char buf[100];
    dtoa_puff(buf, data[i++ % 1000], 17);
	benchmark::DoNotOptimize(buf[16]);
  }
}
BENCHMARK(dtoa_puff);

BENCHMARK_MAIN();