Hidden Tree

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

This problem is interactive. Make sure to call the flush method after outputting each line.

Zenyk and Marichka are trying to guess the tree in front of them. A tree is a connected graph with \(n\) vertices and \(n - 1\) edges, where there is a unique simple path between every pair of vertices. Also, each edge has a unique weight \(w_i\), meaning all \(w_i\) are distinct.

Initially, Zenyk and Marichka only know the number of vertices \(n\). Then in one minute, they can choose a pair of vertices \(u\) and \(v\) and find out the weight of the heaviest edge on the path from \(u\) to \(v\). In total, they can perform this operation no more than 4477 times. After that, the pair wants to find a tree that is similar to the original one. A tree is called similar to the original one if for any pair of vertices \(u\) and \(v\) the weight of the heaviest edge on the path between them is the same as in the original one.

Help Zenyk and Marichka build a strategy to find a similar tree.

Interaction

First, you need to read a single integer \(n\).

Then, to ask a question, output ? and two different integers \(u\) and \(v\) (\(1 \le u, v \le n\), \(u \ne v\)). After that, read the line with the answer to the question — the weight of the heaviest edge on the path between \(u\) and \(v\). You can ask no more than 4477 questions.

When you are sure that you know at least one similar tree, output !. After that, in the next \(n-1\) lines, output 3 integers \(x_i\), \(y_i\), \(z_i\) — an edge between \(x_i\) and \(y_i\) with weight \(z_i\). The constraints \(1 \le x_i, y_i \le n\), \(1 \le z_i \le 10^9\) must hold.

Note that for each test case, the tree is fixed before the questions from Zenyk and Marichka, and cannot change during the process.

Constraints

\(2 \le n \le 477\),

\(1 \le u_i, v_i \le n\),

\(1 \le w_i \le 10^9\),

all \(w_i\) are distinct.

Samples

Notes

Pairs of vertices for which Zenyk and Marichka found the answer:

• Vertex 1 and 4 – the heaviest edge of weight 17 between vertices 4 and 7.

• Vertex 1 and 5 – the heaviest edge of weight 7 between vertices 1 and 7.

• Vertex 6 and 3 – the heaviest edge of weight 5 between vertices 2 and 3.

• Vertex 5 and 6 – the heaviest edge of weight 7 between vertices 1 and 7.

Then Zenyk and Marichka guess a similar tree. It does not completely match the original tree, but for every pair of vertices, the weight of the heaviest edge on the path is the same.