This is an interactive problem. In the interaction section below you will see the information about flushing the output.

Vera is baking an ice cream cake consisting of $N\times N$ flavours of ice cream in the shape of an $N\times N$ rectangle. Let $(i,j)$ denote a flavour where $1\le i,j\le N$. Each flavour has tastiness $t_{i,j}$ and no two flavours have the same tastiness. A flavour is more tasty than another if it has higher tastiness.

Two flavours $(i,j)$ and $(k,l)$ are adjacent if and only if $|i-k|+|j-l|=1$. Vera thinks a flavour $(i,j)$ is delicious if it is more tasty than all of its adjacent flavours.

Vera does not know the tastiness of each flavour but she can take a nibble of any two different flavours $(i,j)$ and $(k,l)$ and determine which flavour is more tasty.

Given integer $N$, tell Vera which flavours to nibble and find a delicious flavour. Vera would like to eat her delicious flavour soon so you can only ask her to nibble $Q$ times. She is sure that you can find a delicious flavour after knowing the result of $Q$ nibbles.

Constraints

For all subtasks:

$1\le N$

$N$ is an integer.

Subtask 1 [25%]

$Q=N^2$ and $N\le 100$

Subtask 2 [25%]

$Q=12\times N$ and $N\le 1024$

Subtask 3 [50%]

$Q=4\times N$ and $N\le 1024$

Input Specification

Format:

$N$

Output Specification

To print the answer, print one line in the format:

2 $i$ $j$

where $(i,j)$ is a delicious flavour. Do not forget to flush your answer!

If there are multiple delicious flavours print any of them.

After printing the answer your program must terminate.

Interaction

First you must read $N$. Then you can ask Vera to nibble.

To ask Vera to nibble flavours $(i,j)$ and $(k,l)$ print one line in the format:

1 $i$ $j$ $k$ $l$

Note, you must flush your output to get a response.

Vera's response will be printed on one line in the format:

$x$

If $x=0$ then flavour $(k,l)$ is more tasty than flavour $(i,j)$. Otherwise $x=1$ and flavour $(i,j)$ is more tasty than flavour $(k,l)$.

If your nibble request is not in the correct format or you ask for too many nibbles you will get WA.

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.

Sample Input

3
0
1
1
0
0
1
1
0

Sample Output

1 1 2 1 1
1 1 3 1 1
1 2 1 1 3
1 2 2 2 1
1 2 3 2 1
1 3 1 2 1
1 3 2 3 1
1 3 3 3 2
2 3 2

Explanation of Sample Output

This is a possible interaction when the cake has the following tastiness:

2 1 3
6 5 4
7 9 8

$8$ nibbles were made and the delicious flavour is $(3,2)$ with tastiness $9$.