这是一个交互式问题。

通常，VKOSHP 的参赛者每解决一个问题就会获得一个气球，但这一次，每解决一个问题，队伍将获得一棵树！回忆一下，树是一个无环的连通无向图。

由于比赛中共有 $n$ 道题，因此需要准备 $n$ 棵不同的树，每棵树包含 $2n$ 个顶点，顶点编号为 $1$ 到 $2n$。

然而，事实证明，树往往会不断发生变化。在将某棵树交付给解决该问题的队伍之前，可以对该树应用以下操作不超过 $n - 1$ 次：

• 选择数字 $a, b, c, d$，使得边 $(a, b)$ 在树中，而边 $(c, d)$ 不在树中；
• 然后，从树中删除边 $(a, b)$ 并添加边 $(c, d)$。保证在此操作后，图仍然是一棵树。

你希望能够区分每个队伍解决的题目，因此你需要找到 $n$ 棵树，使得即使在经过上述修改后，它们仍然可以相互区分。

上图展示了 $n = 2$ 时测试样例中气球的示例。

上图展示了你的程序在测试样例中所需的树的示例。

本题的测试流程如下。首先，你向评测程序报告 $n$ 棵树，每棵树包含 $2n$ 个顶点。

之后，你将依次收到 $q$ 棵树，每棵树都是通过对你给出的某棵原始树应用不超过 $n - 1$ 次上述操作得到的。对于每棵树，你必须指出它是从哪棵原始树演变而来的。

交互

首先，你的程序应该从标准输入中读取整数 $n$ 和 $q$（$1 \le n, q \le 100$）。

然后，程序应该输出 $n$ 棵树。对于每棵树，你需要输出 $2n - 1$ 对数字，即该树的边描述。

在此之后，评测程序将向你提供 $q$ 次询问，每次询问给出通过上述操作得到的一棵树。对于每次询问，你必须输出一个整数 $x$——表示该树所对应的原始树的索引（从 $1$ 到 $n$ 的整数）。

样例

在样例测试中，评测程序与选手程序之间的交互信息用空行隔开，以便直观地展示哪些信息是相互对应的。在实际交互中，不会有空行，你也不应该输出任何空行。

输入样例 1

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

输出样例 1

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

说明

在你的程序的每次操作后，输出一个换行符。

在你的程序的每次操作后，清空输出流（flush）。

如果你在 Pascal 中使用 writeln，在 C++ 中使用 cout << ... << endl，在 Java 中使用 System.out.println，在 Python 中使用 print，在 C# 中使用 Console.WriteLine，则输出流会自动清空，你不需要做任何额外的事情。如果你使用其他输出方法，建议手动清空输出流。请注意，在任何情况下都必须输出换行符。