405907: GYM102155 I $\leq$ or $\geq$

This is an interactive problem.

There are n stacks, each containing k positive integers not exceeding 10⁹. You play a game with the jury program. Initially you know only the topmost value of each stack. Game proceeds as follows:

• At the beginning of each turn you choose some integer x.
• After that, jury program selects one of the options: " ≤ " or " ≥ ". Denote the chosen relation as R.
• For every non-empty stack, if the topmost element t satisfies the inequality "t R x", t is being removed from the stack. This procedure is performed only once with each stack.
• Finally, you are told what was the chosen relation R and current state of each stack, that is either information that the stack is empty or the stack topmost number.

In all tests except sample n = 10 000, k = 10. Your task is to clear all stacks in no more than 50 moves.

Note that the jury program is adaptive, i.e. stack contents are not fixed and may change "on the run" depending on the output of your program.

The first line of input contains two integers n, k, the number of stacks and the size of each stack. For the sample case n = 4, k = 2. In all other tests n = 10 000, k = 10.

The second line of input contains n integers that are the topmost elements of each stack.

At the beginning of each turn you should output a single integer x (1 ≤ x ≤ 10⁹).

Next line of input will contain the string, that will contain either the word "End", or one of the strings "<=" or ">=".

In case of "End", your program should immediately terminate with zero exit code. It may happen if your program successfully cleared all the stacks, if it made an incorrect query or if after 50 queries there are still non-empty stacks.

Otherwise, the string denotes the chosen relation R, and the next line of input will contain n integers, each of which will be either 0 if the corresponding stack is empty, or its topmost element otherwise.

All values in the stacks are positive integers not exceeding 10⁹.

Make sure your output does not get buffered, for instance, by calling fflush(stdout) in C/C++, System.out.flush() in Java or sys.stdout.flush() in Python after printing each number.

4 2
1 2 3 4 

<=
5 6 3 4 

>=
0 0 3 8 

<=
0 0 7 8 

<=
0 0 0 8 

End

 
 
2
 

4
 

3
 

7
 

8

In the sample test there are four fixed stacks of size 2:

1  2  3  4
5  6  7  8

Next we describe the interaction example as shown in "Example" section. Note that, although the stacks are fixed, the interactor in the system may behave not exactly in this way even if you ask the same queries.

In the first query x = 2 and R =  " ≤ ". After the query numbers 1 and 2 are removed and stacks look like this:

      3  4
5  6  7  8

In the second query x = 4 and R =  " ≥ ". Numbers 5, 6 and 4 are removed, and the stacks' state is:

      3 
      7  8