Problem B
Maple Tree

As a cryptoarborist, you study secret trees. Today, you have been out in the forest and encountered an exciting specimen with $N$ nodes and $N-1$ edges of varying lengths, all with positive lengths. Additionally, it is known that each node has at most $3$ edges.

It is not easy to determine the structure of the tree – which nodes are connected to each other – but you have obtained a device that you believe can help you. The device compares distances in the tree. Let $d(x, y)$ denote the sum of the edge lengths on the path between nodes $x$ and $y$. With one use of the device, given three nodes $A, B, C$ (where $A \neq B$), you can compare whether $d(A, C)$ is less than or greater than $d(B, C)$.

Using the device at most $20,000$ times, can you find which edges exist in the tree? You do not need to find the length of the edges.

Interaction

Your program should first read an integer $N$ ($3 \leq N \leq 1000$), the number of nodes in the tree.

Then you can start performing measurements with your device, up to $20,000$ times. For each measurement, you should print a line in the format ? A B C ($1 \leq A, B, C \leq N$, $A \neq B$), and then read a line which will contain either the character A (if $d(A, C) < d(B, C)$) or B (if $d(A, C) > d(B, C)$). It is guaranteed that $d(A, C) \neq d(B, C)$ for all $A \neq B$.

Finally, you should print a line with the character !, followed by $N-1$ lines, each containing the edges of the tree. Each line should contain two integers $a, b$ ($1 \leq a, b \leq N$), the names of the nodes the edge connects.

It is guaranteed that the tree in each test case is predetermined and does not change adaptively in response to your measurements.

To simplify testing of your program, we provide a tool that you can download at the bottom of this page. See the comment at the top of the file for a description of how it can be used.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of sample

In the example interaction, a maple tree with $5$ nodes is studied. Using the measuring device, it is determined that the length of the path between node $1$ and $3$ is shorter than that between $2$ and $3$, and that the length of the path between $1$ and $5$ is longer than that between $4$ and $5$. Based on that information, the guess is made that the tree has the four edges $(1, 3)$, $(2, 3)$, $(4, 3)$, and $(4, 5)$. In reality, more measurements would need to be performed to determine the structure of the tree with certainty.

 5

 ? 1 2 3

 A

 ? 1 4 5

 B

 !
 1 3
 2 3
 4 3
 4 5