Petya 是一个排序机器人。他的内存中有一个长度为 $n$（$1$ 到 $100$）的数组，其元素是两两不同的整数。数组中的位置从左到右编号为 $1$ 到 $n$。

Nina 是一名机器人操作员。Nina 想要对这个数组进行排序：使得对于任意两个不同的位置，左侧的数字小于右侧的数字。唯一可用的命令是比较两个位置 $i$ 和 $j$ 上的元素。如果左侧位置（可以是位置 $i$ 或 $j$）上的元素大于右侧位置上的元素，Petya 会交换它们并在屏幕上显示数字 $1$。否则，Petya 不会对数组做任何操作，仅在屏幕上显示数字 $0$。

不幸的是，Petya 的电源系统损坏了，因此机器人有时会关机。具体表现为：当收到命令时，Petya 不会执行它，而是在屏幕上显示 $-1$，然后忽略后续的所有命令。

为了让 Petya 再次工作，Nina 会将他拆解并重新组装。数组不会改变。不幸的是，在维修过程中，Nina 忘记了她已经向机器人发出了哪些命令。此后，Petya 会在电池耗尽前一直工作，然后再次关机。

电池有足够的电量供 Petya 执行 $1500$ 条命令。Petya 会关机两次：在执行第 $x$ 条命令后和执行第 $1500$ 条命令后（$0 < x < 1500$，值 $x$ 对 Nina 是未知的）。了解以上所有信息后，请帮助 Nina 使得在 Petya 第二次关机后，他内存中的数组是有序的。

交互

在本题中，你的程序在每个测试点上会被运行两次。你的程序代表 Nina，评测程序代表 Petya。每一行输入都以换行符结束。

这是一个交互式问题。请记住在打印每条命令后立即刷新输出！下面描述了你的程序与评测程序之间的交互过程：在两次运行中该过程相同。

输入的第一行包含一个整数 $n$，即数组的大小（$1 \le n \le 100$）。此后，你的程序发出命令，评测程序执行它们并打印答案。

要发出“比较位置 $i$ 和 $j$ 上的元素”的命令，请打印一行格式为 “$i$ $j$” 的内容，其中 $1 \le i, j \le n$。结果，你将得到一行包含单个整数的输出： $1$ 表示 Petya 交换了位置 $i$ 和 $j$ 上的元素，因为左侧元素大于右侧元素； $0$ 表示 Petya 没有做任何改变，因为左侧元素不大于右侧元素（即左侧元素小于右侧元素，或者 $i = j$）； * $-1$ 表示 Petya 在执行命令前关机了。

在最后一种情况下，程序必须终止。在其他情况下，可以继续发出下一条命令。

如果你想在 Petya 关机前终止交互，请打印一行 “-1 -1” 而不是命令。此后，程序必须终止。

在每个测试中，第一次运行前的数组是预先固定的，第二次运行前的数组处于第一次运行结束时的状态。此外，在每个测试中，Petya 第一次关机时的命令数 $x$（$0 < x < 1500$）也是预先固定的。在第二次运行期间，即使第一次运行的交互在第一次关机前结束，机器人也会在 $1500 - x$ 条命令后关机。

样例

输入 1

5
1
1
0
1
1
0
1
0
-1

输出 1

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

输入 2

5
1
0
0

输出 2

1 2
2 3
1 2
-1 -1