这是一个只读输出问题。请注意，你仍然需要提交能够打印出输出结果的代码，而不是直接提交文本文件。

图的有效 3-染色是指将集合 $\{1, 2, 3\}$ 中的颜色（数字）分配给图的每个顶点，使得对于图中的任意边 $(a, b)$，顶点 $a$ 和 $b$ 的颜色不同。对于一个具有 $n$ 个顶点的图，最多有 $3^n$ 种这样的染色方案。

你在一家公司工作，目标是成为创建具有特定数量 3-染色方案的图的专家。有一天，你得知傍晚时分你将收到一个订单，要求生成一个恰好有 $6k$ 种 3-染色方案的图。你不知道 $k$ 的确切值，只知道 $1 \le k \le 500$。

你不想等到 $k$ 的具体值确定后再开始创建图。因此，你预先构建了一个最多包含 19 个顶点的图。然后，在得知具体的 $k$ 值后，你被允许向图中添加最多 17 条边，以获得所需的恰好有 $6k$ 种 3-染色方案的图。

你能做到吗？

输入格式

本题没有输入。

输出格式

首先，输出 $n$ 和 $m$ ($1 \le n \le 19, 1 \le m \le \frac{n(n-1)}{2}$) —— 初始图（预先构建的图）的顶点数和边数。然后，输出 $m$ 行，每行格式为 $(u, v)$ —— 图的边。

接下来，对于从 1 到 500 的每一个 $k$，执行以下操作：

输出 $e$ —— 你为该特定 $k$ 添加的边数 ($1 \le e \le 17$)。然后，输出 $e$ 行，每行格式为 $(u, v)$ —— 你将添加到图中的边。

图中不能有自环，并且对于每一个 $k$，你使用的所有 $m + e$ 条边必须两两不同。对于特定的 $k$，该图的 3-染色方案数必须恰好为 $6k$。

样例

输入 1

-

输出 1

3 2
1 2
2 3
1
1 3
0

说明

样例输出仅作为示例提供。它包含了 $k = 1, 2$ 的输出。