Note: This problem is missing data.

Little Q has a binary tree with $n$ nodes, labeled $1$ to $n$. Little Q has set you a difficult task: you must delete these nodes one by one, with the rule that you can only delete a node that has no parent (i.e., before deleting a node, all of its ancestors must have been deleted). The difficulty of the game is that you do not know the structure of the tree, and you can only learn about it by asking Little Q questions, to which Little Q will answer truthfully.

Query method: Ask about the ancestral relationship between node $p$ and node $q$.

There are three possible answers: $p$ is an ancestor of $q$; $q$ is an ancestor of $p$; or neither is an ancestor of the other.

The definition of an ancestor is: all nodes on the simple path from a node $A$ to the root (excluding $A$ itself) are ancestors of $A$.

Your goal is to delete all nodes using as few queries as possible.

Interaction

This is an interactive problem, and you are required to use C++. At the beginning of your program, we have declared four functions for your use:

int size() // Returns the number of nodes n in the tree

int type() // Returns the type of the tree (1, 2, 3, detailed in the data constraints)

int question(int p, int q) // Returns the relationship between node p and node q. If the return value is 1, p is an ancestor of q. If the return value is -1, q is an ancestor of p. Otherwise, the return value is 0. Note that p and q must be integers from 1 to n.

void submit(int x) // Deletes node x. Note that x must be an integer from 1 to n.

For the first three functions, your program may call them any number of times. For the fourth function, your program can only call it $n$ times, and each node must be deleted exactly once. Furthermore, your program must ensure that every node deleted has no parent at the time of deletion.

If your program satisfies the above requirements and terminates normally within the time limit, the system will count the number of times your program called the question(int p, int q) function as $yournum$ and compare it with the five provided scoring parameters $a_1 \geq a_2 \geq a_3 \geq a_4 \geq a_5$. If $yournum \leq a_i$, you will receive $i$ points; if you satisfy multiple criteria, you will receive the highest score.

Tip: It has been tested that the question() function can be called approximately $2 \times 10^8$ times per second. Please consider this factor when calculating time complexity.

In particular, your program is not allowed to perform any input or output operations; otherwise, it will be scored as 0 points.

Examples

Input 1

(input data)

Output 1

(output data)

Note

The following is an example of how to structure your code:

using namespace std;
int main()
{
    if (size() == 2) // If n=2, the following algorithm guarantees correctness with one query
    {
        if (question(1, 2) == 1) // Query the ancestral relationship between 1 and 2
        {// If 1 is an ancestor of 2, delete 1 then 2
            submit(1);
            submit(2);
        }
        else
        {// Otherwise, delete 2 then 1
            submit(2);
            submit(1);
        }
    }
    else // If n is not 2, delete in order 1~n, though this does not guarantee correctness
        for (int i=1; i<=size(); i++)
            submit(i);
}

Constraints

The data scale is the return value of int size(), representing the number of nodes in the tree.

The data type is the return value of int type():

• 1 indicates that the tree is a "chain"; specifically, each node has at most one child.
• 2 indicates that the tree is a full binary tree.
• 3 indicates that we do not know if the tree has any special structure.