Interactive Number Guessing

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

This is an interactive problem.

Your task is to write a program that guesses a secret number through repetitive queries and responses. The secret number is a non-negative integer less than 101810^{18}.

Let xx be the secret number. In a query, you specify a non-negative integer aa. In response to this, the digit sum of (x+a)(x + a) will be returned. Here, the digit sum of a number means the sum of all the digits in its decimal notation. For example, the digit sum of 40964096 is 4+0+9+6=194 + 0 + 9 + 6 = 19.

힌트

In this example, the secret number xx is 7575. In response to the first query, 1515 is returned because x+a=75+3=78x + a = 75 + 3 = 78 and its digit sum is 7+8=157 + 8 = 15. After the second response, you can conclude that the only possible secret number is 7575.