Guess the Number

The judging system has secretly chosen an integer in the range \([1,10^9]\). Your task is to guess this number by asking at most 50 questions.

For each question, you must output an integer within the range \([1,10^9]\) to standard output and flush the output buffer. Then, you will read an integer from standard input which represents the feedback from the judge:

• 0: Your guess is correct. Your program must stop asking further questions.
• -1: Your guess is less than the secret number.
• 1: Your guess is greater than the secret number.

Be sure to flush the output buffer after every output. For example:

• C/C++: fflush(stdout);
• C++ (if not using '\n'): std::cout << std::flush;
• Java: System.out.flush();
• Python: stdout.flush()
• Pascal: flush(output);

Following these guidelines, implement a binary search or any other efficient strategy to guess the secret number within at most 50 questions.

inputFormat

This is an interactive problem. For each guess you output, you will receive a response from the judging system via standard input. The response values are:

• 0: correct guess
• -1: your guess is lower than the secret number
• 1: your guess is higher than the secret number

The input is provided interactively and the exact input sequence is determined by the judge.

outputFormat

For each query, output an integer between 1 and \(10^9\) (inclusive) to standard output and flush your output buffer. The program should terminate immediately after receiving a response of 0 from the judging system.

sample

Simulated interactive transcript for secret number 1:
Judge responses: 1, 1, 1, ..., 0

A sequence of binary search guesses that eventually outputs 1.