Having just landed in the desert Kira remembers that his Strike Gundam is not yet programmed for sand environments. He needs to determine the right amount of pressure \(N\) that the Strike needs to exert on the sand so that it will neither sink nor float. In other words, he needs the pressure to be an exact number. He knows that the maximum pressure that needs to be exerted is \(2×10^9\) and the minimum pressure is \(1\). He wants to find this number \(N\) in at most 31 guesses.
This is an interactive problem. Your program will keep outputting numbers between \(1\) and \(2×10^9\) inclusive and reading a line of input after each output. The line your program reads will be
FLOATS if your guess for the pressure is too high,
SINKS if your guess for the pressure is too low, and
OK if you have the right number. At this point, your program should terminate.
Each time you output a number, you need to output a new line and flush your output buffers. For example, in Python you can do this with
import sys; sys.stdout.flush(), and in Java with
>>> denotes your output; don't actually print this out.
>>> 1 SINKS >>> 6 SINKS >>> 10 SINKS >>> 40 FLOATS >>> 32 OK