题目背景

小明觉得好久没出交互题了，所以出一道。

题目描述 4s 512MB

请注意，这里面3秒是留给交互库的时间

小明有一个长度为$n$的$1,...,n$的排列，但小明只告诉了你$n$。

你可以猜最多$2n+200$次，每次猜两个不同的位置$x,y$，小明会告诉你$\gcd(a_x,a_y)$。

在用完猜测次数，或者是你想提前结束时，输出两个位置$x,y$，你需要确保$\gcd(a_x,a_y)\geq \lceil \frac{n}{3}\rceil$。

交互格式

首先从标准读入读入一个数字$n$。

接下来开始你的交互：

你可以输出1 x y代表你要猜一次，记得在输出后使用endl或者cout.flush()来刷新缓冲区。

接下来你可以读入一个数字，代表这次猜测的结果。

你也可以输出2 x y来代表你的答案，记得在输出后使用endl或者cout.flush()来刷新缓冲区。

输出完答案后，你可以结束你的程序了。

请注意，在这个过程中，你不能输出一样的两个位置$x,y$，无论是1 x y还是2 x y。

当你次数超了，或者是你输出了不合理的元素，则会得到re之类的结果。

样例输入 #1

4
1
1
1
1
2

样例输出 #1

1 1 2
1 1 3
1 1 4
1 2 3
1 2 4
2 2 4

样例解释 #1

这个过程是动态的，交互库的数列其实是$[1,2,3,4]$。

你读入了$n=4$，然后问了$1,2$，得到了返回$1$，你问了$1,3$，得到了返回$1$，...，你问了$2,4$，得到了返回$2$。

于是你输出了$2,4$作为答案。

贴心的大样例提交地址

数据范围

sub 1（15分）：$n\leq 15$。

sub 2（10分）：$n\leq 20$。

sub 3（25分）：保证$n\leq 10000$。

sub 4（20分）：保证$n=2^k$

sub 5（30分）：$15\leq n\leq 10^5$。

对于所有数据：$15\leq n\leq 10^5$。