Problem Description

Gujyo and Chin-Lan are playing a game. They have a deck of $n$ cards, with exactly one card of each value from $1$ to $n$. A card sequence is defined as good if and only if it can be generated by performing the following process once:

Sort the $n$ cards in increasing order by value, split them into several consecutive segments, then for each segment, choose one card in the segment and move it to the end of this segment (for example, segment $(1,2,3,4)$ can become $(2,3,4,1)$, $(1,3,4,2)$, $(1,2,4,3)$, or $(1,2,3,4)$ after the operation). Finally, concatenate all segments in their original order to obtain a new sequence.

Now Chin-Lan designs a good card sequence and places it face down in a row. Gujyo tries to guess the position of the card with value $1$. Specifically, Gujyo will make multiple queries. Each time, she gives an index and learns the value of the card at that position, until the value is $1$, at which point the game ends. Gujyo is very smart, so each time she will choose an index that makes her total number of queries in the worst case as small as possible. Note that Gujyo knows the sequence is good.

However, Chin-Lan has very skillful hands: she can quickly swap the positions of two cards that Gujyo has not queried yet. To avoid being noticed by Gujyo, she must ensure that when the game ends, there exists at least one good sequence such that the values at the positions Gujyo has already learned are consistent with it. She wants to maximize Gujyo's number of queries when the game ends, and based on that, minimize the lexicographical order of the card sequence at the end of the game. If there are still unknown positions when the game ends, treat the final card sequence as the lexicographically smallest one among all valid sequences that match all known positions exactly.

Now you play as Chin-Lan. The interactive library will make multiple queries. For each query, it gives an index, and you need to return the value of the card at that position given by Chin-Lan.

Implementation Details

This is a functional interactive problem. Contestants do not need to, and should not, implement the main function, and must not read from or write to stdin/stdout, otherwise it will be considered cheating. Instead, you need to implement the following functions in your program:

void init(int c,int n);

For each test point, this function will be called exactly once by the judge at the beginning of the program. $c,n$ denote the subtask number and the $n$ in the statement.

int query(int id);

The interactive library will call this function exactly once for each query operation. $id$ is the index of the query. This function should return the answer you give for that query.

Input Format

None.

Output Format

None.

Hint

Sample & Explanation

The sample shows one possible interactive process. $n=5$, Gujyo queries positions $5,3,4,2,1$ in order, and the card sequence constructed by Chin-Lan is $1,2,4,3,5$. It can be proven that this sequence is good, maximizes Gujyo's number of queries, and is lexicographically smallest among all sequences that satisfy the requirements.

Constraints

For all testdata, $1\le n\le 5\times 10^6$.

::cute-table{tuack} |Subtask ID|$n\le$|Special property|Score| |:---:|:---:|:---:|:---:| |#1|$3$|None|$10$| |#2|$10$|^|$10$| |#3|$20$|^|$20$| |#4|$10^5$|^|$20$| |#5|^|Yes|$10$| |#6|$5\times 10^6$|^|$10$| |#7|^|None|$20$|

Special property: when Gujyo has multiple query positions that satisfy the condition, she will choose the position with the smallest index to query.

Translated by ChatGPT 5