你的任务是在坐标平面上选择 $N$ 个点，并绘制 $M$ 条连接这些点的直线段，使得恰好有 $K$ 个有限面。这里，“面”是指平面被这些线段分割成的区域。其中一个区域是无限的，应忽略不计。

更正式地说，你的配置必须满足以下条件：

• 每个点的 $x$ 和 $y$ 坐标必须是 $1$ 到 $79$ 之间的整数。
• 所有点的位置必须互不相同。
• 连接两个点之间不能有多条线段。
• 两条不同的线段除了在端点处外，不能相交。
• 除线段端点外的点不能位于线段上。

在下图中，(a) 是一个由 3 个点和 3 条线段构成 1 个面的例子。(b) 是一个由 4 个点和 6 条线段构成 3 个面的例子。(c) 是一个错误的输出，因为其中包含曲线；(d) 是一个错误的输出，因为其中包含相交的线段。

输入格式

第一行包含三个正整数 $N$、$M$ 和 $K$，分别表示点的数量、线段的数量以及需要创建的面数 ($3 \le N \le 3000, 0 \le M, 0 \le K$)。

保证对于给定的 $N$、$M$ 和 $K$，一定存在解。

输出格式

在前 $N$ 行中，打印所选点的坐标。这些行中的第 $i$ 行必须包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 79$)：即第 $i$ 个点的坐标。

然后打印 $M$ 行描述线段。每行必须包含两个 $1$ 到 $N$ 之间的整数：由该线段连接的点的索引。

如果存在多个可能的解，打印其中任意一个即可。

样例

输入 1

4 6 3

输出 1

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

输入 2

6 5 1

输出 2

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

说明

左图展示了由 4 个点和 6 条线段构成的 3 个面。 右图展示了由 6 个点和 5 条线段构成的 1 个面。