题目描述

你需要在平面上放置 $N$ 个点，并在这些点之间画出 $M$ 条线段，使图形恰好形成 $K$ 个区域。

这里的“区域”指平面中的一个有界空白部分，其边界必须完全由所画线段组成。一个区域可以包围另一个区域。

输出必须满足以下全部条件：

1. 每个点的 $x,y$ 坐标都是 $1$ 到 $79$ 之间的整数；
2. 所有点的位置互不相同；
3. 不允许存在连接同一对点的多条线段；
4. 每条线段必须连接两个不同的点；
5. 任意两条不同线段不能在公共端点以外的位置相交；
6. 除一条线段的两个端点外，其他任何输出点都不能位于该线段上。

下图中：

• (a) 用 3 个点和 3 条线段形成 1 个区域，是合法输出；
• (b) 用 4 个点和 6 条线段形成 3 个区域，是合法输出；
• (c) 含有曲线，不合法；
• (d) 线段在非端点处相交，不合法。

输入格式

第一行包含三个整数 $N,M,K$，分别表示点数、线段数和需要形成的区域数。

保证存在一组满足条件的 $N$ 个点和 $M$ 条线段，能够形成恰好 $K$ 个区域。

输出格式

前 $N$ 行，第 $i$ 行输出两个整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

接下来 $M$ 行，每行输出两个整数 $u,v$，表示画一条连接第 $u$ 个点和第 $v$ 个点的线段。

输出任意满足全部条件的构造即可。

样例 1

输入

4 6 3

一种合法输出

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

样例 2

输入

6 5 1

一种合法输出

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