Problem Statement

This is an interactive problem.

There are $3$ piles of cards stacked vertically. The $3$ piles are numbered $1,2,3$.

Each pile consists of $2n$ cards, each with $1$ integer written on its face. Let $V _ {i, k}$ be the integer written on the $k\ (1\leq k\leq 2n)$-th card from the top of pile $i\ (1\leq i\leq 3)$.

Since each card is stacked face down, you do not know the values of $V _ {i, k}$. However, you do know that the following fact holds.

• The cards in each pile are sorted in ascending order from top to bottom. That is, for any integers $i,k,l$ satisfying $1\leq i \leq 3,\ 1\leq k\lt l \leq 2n$, it holds that $V _ {i, k} \leq V _ {i, l}$.

Now, you will play a [Game]. The [Game] proceeds according to the following procedure.

[Game]

1. Let $X\leftarrow 0$.
2. Let $a$ be the number of non-empty piles among the $3$ piles.
   • If $a = 0$, end the game.
   • If $a = 1$, update $X\leftarrow 10 ^ {100}$ and end the game.
   • If $a \geq 2$, you choose any $2$ non-empty piles $i, j\ (i\neq j)$. Remove the top card from each of the $2$ chosen piles. Let $x _ 1, x _ 2$ be the integers written on the $2$ removed cards, update $X\leftarrow \max(X, x _1 + x _ 2)$, and return to step 2.

Your goal is to make $X$ at the end of the game as small as possible. Before the game starts, you may ask the following [Question] at most $3$ times.

[Question]

• Choose integers $i,x,j,y$ satisfying $1\leq i\leq 3, 1\leq x\leq 2n, 1\leq j\leq 3, 1\leq y\leq 2n$, and ask whether $V _ {i, x} \lt V _ {j, y}$ holds.

Let $X ^ \ast$ be the minimum value of $X$ at the end of the game achievable when all the information about the piles is known (that is, when all $V _ {i, k}$ are known).

Find $1$ sequence of operations such that $X$ at the end of the game is exactly equal to $X ^ \ast$.

The judge for this problem is not adaptive. That is, the value of each $V_{i,k}$ is fixed at the beginning and does not change during the interaction.

Input and Output

First, a positive integer $n$ is given from standard input on $1$ line in the following format.

$n$

You may perform the [Question] at most $3$ times. Print the integers $i,x,j,y$ chosen in the [Question] to standard output in the following format, followed by a newline. Here, $i, j$ must be integers between $1$ and $3$, inclusive, and $x, y$ must be integers between $1$ and $2n$, inclusive.

? $i\ x\ j\ y$

In response to this [Question], Yes is given from standard input on $1$ line if $V _ {i, x} \lt V _ {j, y}$ holds, and No otherwise. Note that No is also given when $V _ {i, x} = V _ {j, y}$.

After finishing at most $3$ [Question]s, print a sequence of operations such that $X$ at the end of the game is exactly equal to $X ^ \ast$ to standard output in the following format, followed by a newline. Here, for $t = 1, 2, \ldots, 3n$, $i _ t, j _ t$ are the numbers of the $2$ piles chosen in the $t$-th operation, and they must be distinct integers between $1$ and $3$, inclusive. It can be proved that there exists a sequence of operations such that all the piles become empty after exactly $3n$ operations and $X = X ^ \ast \lt 10 ^ {100}$ is satisfied.

! $i_1\ j_1\ i_2\ j_2\ \cdots\ i_{3n}\ j_{3n}$

After printing the answer, terminate your program immediately.

Constraints

• $n$ is an integer between $1$ and $100$, inclusive
• The values written on the cards are integers between $1$ and $10 ^ 6$, inclusive

Notes

• Each time you print output, add a newline at the end and flush standard output. Otherwise, the judge result is undefined.
• If you print invalid output, exceed the allowed number of questions, or your program terminates midway, the judge result is undefined. In particular, if a runtime error occurs during the execution of your program, the judge result is not necessarily RE.

Sample

The following is an example of the interaction for $n=1$ with $V$ determined as below. Note that in reality $V$ is not given as input.

• $V _ {1, 1} = 2, V _ {1, 2} = 3$
• $V _ {2, 1} = 3, V _ {2, 2} = 4$
• $V _ {3, 1} = 4, V _ {3, 2} = 5$

1

? 2 1 1 1

No

? 1 2 3 1

Yes

! 2 3 1 3 1 2