Description

The Government decided to build a new highway system through $N$ cities. Each city has already specified the desired location of its junction. The Government has the policy that highways may only be built along straight lines. Miraculously, two highways turned out to be enough to reach all cities, i.e. it is possible to define two lines, such that each of the junction points lies on one of the lines. Also, both of these lines contain at least three of the junctions, and there is no junction at the intersection of the two lines. It is easy to prove that under these conditions the lines are uniquely determined. Your company's job is to build this highway system, therefore you want to know the traces of the two lines. The coordinates of the junction points have been registered at the Land Office, but you are only allowed to submit queries to the office asking whether or not some given three junction points are collinear. Since a query has a significant processing fee (you know these bureaucrats...), you aim to ask as few queries as possible.

Since two junction points completely determine the trace of a straight line, your task is to determine two junction points for the each of the two lines.

You are to write a program that determines two junctions on each of the two highways, with as few queries as possible.

Interaction

This problem requires using interactive I/O.

At the beginning of your program, read a positive integer $N$ from standard input, representing the number of cities. The intersections are numbered from $1$ to $N$.

Then start the interaction. You should output to standard output in the following formats to complete the interaction:

• ? x y z Here, $x,y,z$ are intersection numbers. If intersections $x,y,z$ are collinear, the interactor returns integer $1$; otherwise, it returns $0$.

Note that any two points are always collinear.

• ! a1 b1 a2 b2 This represents your final answer. $a_1, b_1$ are two intersections on one line, and $a_2, b_2$ are two intersections on another line. After outputting this answer, the interactor will not return any further information, and your program should terminate.

For every output operation, you must print a newline and flush the standard output buffer.

Hint

Limitation

For all test cases, $$20 \le N \le 10^5$$.

The grader does not use predetermined input. It answers queries in a way that is always consistent (i.e., it will not contradict itself). Your program will be judged correct only if its final answer is logically implied by the queries it has made. (Guessing is meaningless.)

There are $$25$$ test cases in total. For each test case, if your program is correct and makes $$K$$ queries, then:

• If $$K \le \frac{N}{2} + 2$$, you receive $$4$$ points;
• If $$K \le \frac{2N}{3}$$, you receive $$2$$ points;
• If $$K \le N - 3$$, you receive $$1$$ point;
• Otherwise, you receive $$0$$ points.

You may assume that the grader answers queries in such a way that, unless you make at least $$\frac{N}{3}$$ queries, your program will not be able to produce a correct answer.