Do you know the game "Guess the number"?
The game is played by two players, Thinker and Guesser. Thinker secretly chooses an integer from an interval known to both players and Guesser tries to guess it asking questions. Guesser's questions are of the form: "I think your number is xx." Thinker has three posible answers – "You're right", "No, my number is smaller than xx" or "No, my number is greater than xx". Guesser's goal is to guess the Thinker's number with minimum number of questions.
A few days ago, we finished building the Thinking Meatmincer (TM). The TM has a simple user interface: you insert the data (instead of bits, basic units of TM data are Meats) to the input hole (IH), turn the handle a few times and the result will drop out from the output hole (OH). However, there is a catch - the handle can be turned only if there is a new input in IH.
As the name suggests, TM should be computationally equivalent to Turing Machine, but we haven't performed extensive testing yet. We would like to ask you to assist us in an experiment. You will play game of "Guess the number" in the role of Guesser against the TM in the role of Thinker.
One submission is equivalent to inserting one Meat (remember, Meat is not the same as "piece of meat") into TM and turning the handle once. After doing this enough times, TM will produce its first output (which will be sent to you). Since then, each following submission will cause one output to be produced. NOTE THAT THIS TASK IS SPECIAL: THE MAXIMAL NUMBER OF SUBMITS MIGHT BE GREATER THAN 10 (read the input specification for further information).
From your point of view, the exchange might look as follows:
You -> Mincer: 3
Mincer -> You: There is one Meat inside
You -> Mincer: 5
Mincer -> You: There are two Meats inside
You -> Mincer: 4
Mincer -> You: Mincer full, output: "My number is GREATER than 3"
You -> Mincer: 32
Mincer -> You: Mincer full, output: "My number is SMALLER than 5"
You -> Mincer: 51
Mincer -> You: Mincer full, output: "You're RIGHT, it's 4"
The input file contains three numbers: N, D, S. Thinker can choose a number between 1 and N inclusive. The number D denotes the number of turns of the handle before the first output appears. In other words, you'll get the first useful output from Thinker after your (D+1)-th submission. In the example above we used D=2. The number S denotes the maximal number of submits you may make to solve this input.
Each submit should contain exactly one integer – your guess. This integer must be in the range from 1 to N (inclusive). After each submit you will receive a message similar to one of the messages in the example above.