这是一个交互式问题。

在正方形 $\mathbb{D} = [1, N] \times [1, N]$ 的 $N^2$ 个整点中，隐藏着一个神秘的文物。你的任务是找到这个文物。你拥有一个雷达，其单次使用方式如下：

• 首先，将雷达放置在 $\mathbb{D}$ 中的任意整点上。
• 如果文物恰好位于该点，雷达会亮起绿灯，屏幕上会显示文物和雷达所在的坐标，考古挖掘随之结束。
• 否则，假设你将雷达放置在点 $R$，而文物位于点 $A \neq R$。此时雷达会亮起黄灯，并显示一个整点 $B \in \mathbb{D}$ 的坐标，满足 $\angle ARB < 90^\circ$。在所有满足条件的整点中，雷达会等概率随机显示其中一个；特别地，如果 $A \neq R$，雷达总是有机会显示点 $A$ 的坐标（因为 $\angle ARA = 0^\circ < 90^\circ$），但它永远不会显示点 $R$。

你可以假设，除了前五个测试点（在“说明”部分描述）外，在正方形 $\mathbb{D}$ 的所有可能点中，文物是等概率随机选择的，该位置在每个测试中是固定的，且不依赖于你程序的响应。上述所有随机选择都是独立进行的。

你的雷达电量不足，因此最多只能使用 90 次。编写一个程序，指示将雷达放置在何处，以便它最终亮起绿灯。

交互

第一行包含一个整数 $N$：隐藏文物的正方形的边长 ($1 \le N \le 10^9$)。然后，你的程序应打印使用雷达的请求。每个请求由两个整数 $R_{xi}$ 和 $R_{yi}$ 组成：你想要放置雷达的下一个点的坐标 ($1 \le R_{xi}, R_{yi} \le N$)。每次请求后，你必须打印换行符并刷新输出缓冲区。之后，你可以读取两个整数 $B_{xi}$ 和 $B_{yi}$：雷达屏幕上显示的点的坐标 ($1 \le B_{xi}, B_{yi} \le N$)。如果 $B_{xi} = R_{xi}$ 且 $B_{yi} = R_{yi}$，则说明你已成功通过测试，程序应立即终止以获得该测试点的 OK 判定。否则，如果你尚未进行 90 次请求，则应继续进行请求。

如果进行 90 次请求后雷达仍未亮起绿灯，你的程序应立即终止以获得 Wrong Answer 判定；否则，判定结果可能是不可预知的。

样例

样例输入 1

1
1 1

样例输出 1

1 1

样例输入 2

2
2 2
1 2
1 2
2 2
1 1
1 2
1 1
1 2
1 1

样例输出 2

1 1
2 1
2 1
2 1
2 2
2 2
1 2

说明

本题共有 50 个测试点，包括样例。

测试点 1 与第一个样例一致。

在测试点 2-5 中，$N = 2$。第二个测试点中的文物隐藏在点 $(1, 2)$，如第二个样例所示；但并不保证在第二个测试点中，交互器会提供与样例中相同的响应。测试点 2-5 保证涵盖了所有四种可能的文物位置。

在接下来的 28 个测试点中，$N$ 依次取值为 $4, 8, 15, 30, \dots, \frac{10^9}{4}, \frac{10^9}{2}$。形式化地，对于每个 $i \in \{6, \dots, 33\}$，在第 $i$ 个测试点中 $N = \lceil 10^9/2^{34-i} \rceil$。在这些测试点中，文物均隐藏在等概率随机选择的点上。

在接下来的 17 个测试点中，$N$ 依次取值为 $10^9-5, \dots, 10^9-1, 10^9, \dots, 10^9$。形式化地，对于每个 $i \in \{34, \dots, 50\}$，在第 $i$ 个测试点中 $N = 10^9 + \min\{0, i - 39\}$。在这 17 个测试点中，文物也均隐藏在等概率随机选择的点上。

如果提交多次，且在某个测试点中程序发出了相同的查询，它们将从交互式评测程序中收到相同的回答。