Interactive Minimum Marking

This is an interactive problem.

You are given an initially empty array \(a\). There will be \(n\) operations. In the \(i\)th operation, you append \(x_i\) integers to the end of \(a\). The integers appended are all distinct and the entire array always satisfies that for every \(1 \le i < j \le l\), exactly one of \(a_i < a_j\) or \(a_j < a_i\) holds, where \(l\) is the current length of the array.

After each operation, you need to perform several queries in order to determine the index \(x\) of the smallest unmarked integer in the array \(a\), and then mark \(a_x\) (i.e. it will not be considered in future operations).

You are allowed to ask queries in the following format:

• ? i j: compare two unmarked integers \(a_i\) and \(a_j\).
• The answer to a query is either 0 (meaning \(a_i < a_j\)) or 1 (meaning \(a_i > a_j\)).
• You must ensure that both indices \(i\) and \(j\) are between \(1\) and \(l\) (inclusive), \(i \neq j\), and both \(a_i\) and \(a_j\) are unmarked.

Once you have determined the smallest unmarked integer, output it using the following format:

• ! x, where \(x\) is the 1-indexed position in the array \(a\).

After outputting the answer, immediately read the next operation. If the current operation is the last one, terminate the program.

Important: After each query or answer, print a newline and flush the output buffer. For example, in C++ you can use std::cout << std::endl or std::cout.flush().

---

Simplified Offline Simulation:

Since interactive problems are hard to simulate offline, we provide an offline version. In this version, after each operation the newly appended integers are given as input. Your task is to output the 1-indexed position of the smallest unmarked integer in \(a\) and mark it. The operations are processed sequentially.

Note: In a real interactive problem you are allowed to ask queries of the form ? i j, but in this offline simulation the values of the integers are directly available.

The identification of the smallest unmarked element can be formalized as:

[ x = \min{i \mid a_i \text{ is unmarked}} ]

After printing the answer, mark \(a_x\) and proceed to the next operation.

inputFormat

The input begins with an integer \(n\) indicating the number of operations.

Then, for each operation \(i\):

• A line containing an integer \(x_i\): the number of integers to append to the array.
• A line containing \(x_i\) space-separated integers representing the numbers to be appended.

It is guaranteed that all integers in the array are distinct.

outputFormat

After each operation, output a single line with an integer \(x\) (1-indexed) corresponding to the position in \(a\) of the smallest unmarked integer. Then, mark \(a_x\).

sample

3
3
5 2 8
2
7 1
1
4

2
5
6

</p>