CF772E.Verifying Kingdom

This is an interactive problem.

The judge has a hidden rooted full binary tree with n leaves. A full binary tree is one where every node has either 0 or 2 children. The nodes with 0 children are called the leaves of the tree. Since this is a full binary tree, there are exactly 2_n_ - 1 nodes in the tree. The leaves of the judge's tree has labels from 1 to n. You would like to reconstruct a tree that is isomorphic to the judge's tree. To do this, you can ask some questions.

A question consists of printing the label of three distinct leaves _a_1, _a_2, _a_3. Let the depth of a node be the shortest distance from the node to the root of the tree. Let LCA(a, b) denote the node with maximum depth that is a common ancestor of the nodes a and b.

Consider X = LCA(_a_1, _a_2), Y = LCA(_a_2, _a_3), Z = LCA(_a_3, _a_1). The judge will tell you which one of X, Y, Z has the maximum depth. Note, this pair is uniquely determined since the tree is a binary tree; there can't be any ties.

More specifically, if X (or Y, Z respectively) maximizes the depth, the judge will respond with the string "X" (or "Y", "Z" respectively).

You may only ask at most 10·n questions.

这是一个交互式问题。

评测机持有一棵隐藏的、以根为起点的满二叉树，该树有 $n$ 个叶子节点。所谓满二叉树，是指每个节点的子节点数恰好为 $0$ 或 $2$。没有子节点的节点称为叶子节点。由于这是满二叉树，因此整棵树恰好包含 $2n - 1$ 个节点。评测机所持树的叶子节点被标记为 $1$ 到 $n$。你希望重构一棵与评测机所持树同构的树。为此，你可以提出若干询问。

每次询问需输出三个互不相同的叶子节点标签 $a_1,\,a_2,\,a_3$。定义一个节点的深度为其到树根的最短距离。记 $LCA(a,\,b)$ 为节点 $a$ 与 $b$ 的最近公共祖先（即所有公共祖先中深度最大的那个节点）。

考虑以下三个节点：
$X = LCA(a_1,\,a_2)$，
$Y = LCA(a_2,\,a_3)$，
$Z = LCA(a_3,\,a_1)$。

评测机会告诉你 $X$、$Y$、$Z$ 中深度最大者是哪一个。注意，由于该树是二叉树，三者深度互不相等，因此该最大值唯一确定。

更具体地，若 $X$（或 $Y$、$Z$）的深度最大，则评测机将分别回应字符串 "X"（或 "Y"、"Z"）。

你至多可提出 $10 \cdot n$ 次询问。

The first line of input will contain a single integer n (3 ≤ n ≤ 1 000) — the number of leaves in the tree.

输入的第一行包含一个整数 $n$（$3 \leq n \leq 1000$）——树中叶子节点的数量。

To print the final answer, print out the string "-1" on its own line. Then, the next line should contain 2_n_ - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root.

Your answer will be judged correct if your output is isomorphic to the judge's tree. In particular, the labels of the leaves do not need to be labeled from 1 to n. Here, isomorphic means that there exists a permutation π such that node i is the parent of node j in the judge tree if and only node π(i) is the parent of node π(j) in your tree.

要输出最终答案，请在单独一行中打印字符串 "-1"。随后的一行应包含 $2n-1$ 个整数。其中第 $i$ 个整数表示第 $i$ 个节点的父节点编号；若该节点为根节点，则输出 -1。

只要你的输出树与评测机的树同构，即判定为正确。特别地，叶子节点的编号无需恰好为 $1$ 到 $n$。此处“同构”是指：存在一个置换 $\pi$，使得在评测机的树中节点 $i$ 是节点 $j$ 的父节点，当且仅当在你的树中节点 $\pi(i)$ 是节点 $\pi(j)$ 的父节点。

For the first sample, the judge has the hidden tree:

Here is a more readable format of the interaction:

The last line can also be 8 6 9 8 9 7 -1 6 7.

对于第一个样例，评测机隐藏的树为：

以下是交互过程的一种更易读的格式：

最后一行也可以是 8 6 9 8 9 7 -1 6 7。