Interactive Full Binary Tree Reconstruction

This is an interactive problem.

There is a full binary tree with \(n\) nodes. When \(n=1\), the root has degree \(0\); otherwise, the root has degree \(2\). The nodes are numbered in an unknown order.

You can ask queries of the form pitaj a b (with \(1 \le a, b \le n\)). For each query, the judge returns the identifier of the node on the path from \(a\) to \(b\) that is closest to the root (in \(\LaTeX\) format, the query result is defined by the function \(f(a,b)\)).

Your task is to determine the parent of every node by using no more than \(5 \times 10^{4}\) queries. Note that by definition, the parent of the root is the root itself.

Interaction

1. The first line of input contains a single integer \(n\), the number of nodes in the full binary tree.
2. You can then issue at most \(5 \times 10^{4}\) queries, each in the form of pitaj a b, where \(1 \le a, b \le n\). Each query returns the node on the path from \(a\) to \(b\) that is closest to the root.
3. When you have determined all parent relationships, output kraj on a new line followed by \(n\) lines, where the i-th line contains the parent of node \(i\).

Note: In this problem, nodes are arbitrarily numbered. In offline simulation of this interactive problem, after the integer \(n\) the judge will provide exactly \(n\) integers representing the parent for each node (from node 1 to node n).

inputFormat

The first line of input is an integer \(n\) denoting the number of nodes in the full binary tree. In the offline testing environment, the next \(n\) integers are provided representing the parent of each node (from node 1 to node \(n\)).

outputFormat

First, output a line containing kraj. Then output \(n\) lines, where the i-th line contains the parent of node \(i\) in the tree.

sample

1
1

kraj
1