Find the Hidden Number via Interactive Queries

This is an interactive problem. A hidden positive integer a is chosen by the judge. You can ask queries by providing an integer x (where 0 ≤ x ≤ 10⁹). For each query, the judge will answer whether a + x is a cute number or not.

A positive integer y is defined as cute if and only if

[ y - g(y) < f(y) - y ]

where

[ f(y) = \text{the smallest perfect square strictly greater than } y, \quad g(y) = \text{the largest perfect square less than or equal to } y. ]

For example, since f(1) = f(2) = 4 and g(4) = g(8) = 4, we have that 1, 5, 11 are cute numbers while 3, 8, 15 are not.

Your task is to determine the hidden integer a by issuing appropriate queries. Note that although this is an interactive problem, for the purpose of testing, the hidden number a will be provided as input and your program should output it directly.

inputFormat

The input contains a single integer a (1 ≤ a ≤ 10⁹), which is the hidden number for simulation purposes.

outputFormat

Output the hidden integer a.

sample

1

1