Some square roots like $$\sqrt{25}$$ or $$\sqrt{81}$$ are known by heart, but how can we compute for example $$\sqrt{17}$$? Nowadays, most people use a calculator or a computer to come up with the square root of a number $$s$$, but how was $$\sqrt{s}$$ computed at times when calculators or computers weren't even invented?

Heron's method is perhaps the first algorithm used for approximating $$\sqrt{s}$$. It was named after the first-century Greek mathematician Hero of Alexandria¹ who gave the first explicit description more than 2000 years ago of a method for computing the square root of any given number. This method is also known as the Babylonian method, named after the Babylonians who left us the oldest known mathematical texts².

The Babylonian method works as follows. Suppose we want to compute the square root of a strictly positive number $$s \in \mathbb{R}$$. We start with an initial estimate for $$\sqrt{s}$$, which we refer to as $$x_0$$. Then, in each successive step we compute a more accurate approximation of the square root using the following formula: \[ x_{n+1} = \frac{1}{2} \left( x_n + \frac{s}{x_n} \right) \] Let's apply this algorithm for example to compute $$\sqrt{17}$$. We choose $$x_0 = 6$$ as an initial estimate of $$\sqrt{17}$$. In a next step we get the following more accurate approximation of the square root: \[ x_1 = \frac{1}{2} \left( 6 + \frac{17}{6} \right) = 4.416666666666667 \] Then, we repeat the same procedure to get an even more accurate approximation: \[ x_2 = \frac{1}{2} \left( x_1 + \frac{17}{x_1} \right) = 4.1328616352201255 \] Along the same lines, we keep enhancing the accuracy of the approximation: \[\begin{align} x_3 & = 4.12311714060797 \\ x_4 & = 4.12310562563374 \\ x_5 & = 4.123105625617661 \\ x_6 & = 4.123105625617661 \end{align}\] The Babylonian method thus produces a series of numbers that converges to $$\sqrt{17}$$. We verify this result using math.sqrt from the math module:

>>> import math
>>> math.sqrt(17)
4.123105625617661

An approximation $$x_k$$ resulting from step $$k$$ is considered accurate enough when \[\frac{|x_k - x_{k-1}|}{x_k} \le 10^{-15}\] In that case it is no longer relevant to come up with even more accurate approximations and the procedure stops.

Input

The first line of the input contains a number $$s \in \mathbb{R}$$. The second line of the input contains an initial estimate $$x_0 \in \mathbb{R}$$ of $$\sqrt{s}$$.

Output

The Babylonian method only works if both $$s$$ and $$x_0$$ are strict positive numbers. If this is not the case, the message invalid input must be written to output. In case the input contains valid numbers, the Babylonian method must be applied to compute successive approximations of $$\sqrt{s}$$. For each step of the method, the index of $$x_i\ (i = 0, 1, 2, \ldots)$$ must be written to output, followed by a colon, a space and the approximation $$x_i$$. The method stops at the first step $$k$$ where it holds that \[\frac{|x_k - x_{k-1}|}{x_k} \le 10^{-15}\] with $$x_k$$ the approximation that results from step $$k$$ and $$x_{k-1}$$ the approximation that results from step $$k-1$$.

Example

Input:

17
6

Output:

0: 6.0
1: 4.416666666666667
2: 4.1328616352201255
3: 4.12311714060797
4: 4.12310562563374
5: 4.123105625617661
6: 4.123105625617661

Example

Input:

2
0

Output:

invalid input