Arithmetic Exercise#1135
At the end of the lesson, the arithmetic teacher assigned homework, but Vovchyk was in a hurry to get to recess and did not write it down. Now at home, he is trying to recall the assignment. He remembers that the example involved several of the first natural numbers, each preceded by either a plus or minus sign, and there were no parentheses:
He also managed to glance into the teacher's book and knows that the answer is the integer . Now, Vovchyk wants to reconstruct the example from the assignment.
The input contains a single integer (|k| \leq 10^{100000}).
Output the smallest natural number (N \geq 1) for which there exists at least one combination of signs in the example that results in .
Primer 1