Verifying Kingdom
Contest: VK Cup 2017 - Round 2
Difficulty rating: 3200
Tags: binary search, divide and conquer, interactive, trees

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 2n - 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 a1, a2, a3. 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(a1, a2), Y = LCA(a2, a3), Z = LCA(a3, a1). 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.

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

Output format:
To print the final answer, print out the string "-1" on its own line. Then, the next line should contain 2n - 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.

Interaction format:
To ask a question, print out three distinct integers a1, a2, a3. These integers should be between 1 and n, inclusive.

The judge will respond with a single character, either "X", "Y", "Z".

If the string is "X" (or "Y", "Z" respectively), that means the pair (a1, a2) (or (a2, a3), (a3, a1) respectively) has the deepest LCA among the three pairs.

You may only ask a question at most 10·n times, otherwise, you will get Wrong Answer.

When you are ready to answer, print out a single integer "-1" on its own line. The next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root. Do not forget to flush the final answer as well. Printing the answer does not count as asking a question.

You will get Wrong Answer verdict if

- Your question or answers are not in the format described in this statement.
- You ask strictly more than 10·n questions.
- Your question contains duplicate indices.
- Your final answer is not isomorphic to the judge tree.

You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

To flush you can use (just after printing an integer and end-of-line):

- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- See the documentation for other languages.

If at any moment your program reads -1 as an answer, it should immediately exit normally (for example, by calling exit(0)). You will get Wrong Answer in this case, it means that you made more queries than allowed, or made an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Hacking To hack someone, use the following format

This denotes a tree where the parent of the i-th node is pi (pi =  - 1 or n < pi ≤ 2n - 1). If pi is equal to -1, then node i is the root. This input must describe a valid full rooted binary tree.

Of course, contestant programs will not be able to see this input.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Here is a more readable format of the interaction:

$$\begin{array}{|c|c|}
\hline
\text{Judge} & \text{Contestant} \\
\hline
5 & 142 \\
X & 124 \\
Z & 241 \\
Y & 235 \\
Y & 243 \\
X & -1 \\
& -1112233366 \\
\hline
\end{array}$$

Example input:
5
X
Z
Y
Y
X

Example output:
1 4 2
1 2 4
2 4 1
2 3 5
2 4 3
-1
-1 1 1 2 2 3 3 6 6

Editorial:
Consider building the tree leaf by leaf.
The base case of two leaves is trivial.
Now, suppose want to add another leaf wi.
We can define the "centroid" as a tree such that after removing the centroid, all remaining connected components has at most half the number of leaves (note this is different from the standard definition of centroid).
Notice, each internal node can be represented as a pair of leaves (x,y), where x comes from the left child, and y comes from the right child.
Ask the judge (x,y,w_i).
Depending on the response, we can remove the centroid, and know which subtree that w_i lies in (i.e. either the left child, right child, or upper child). So, we can recurse on that tree.
So, inserting a node takes log_2 i questions and O(i) time, so overall we ask n log n questions and take n^2 time.