座標平面上に $N$ 個の点を選択し、$M$ 本の直線セグメントでそれらを結ぶことで、ちょうど $K$ 個の有限な面（face）が作られるようにしてください。ここで、面とはセグメントによって分割された平面上の領域を指します。無限に広がる領域は面には含めず、無視するものとします。

より形式的には、構成は以下の条件を満たす必要があります。

• 各点の $x$ 座標および $y$ 座標は $1$ から $79$ までの整数でなければならない。
• すべての点は異なる位置になければならない。
• 2つの点を結ぶ複数の直線セグメントがあってはならない。
• 2つの異なる直線セグメントは、端点以外で交差してはならない。
• セグメントの端点以外の点は、そのセグメント上に存在してはならない。

以下の図において、(a) は3つの点と3つの直線セグメントで1つの面が作られる例です。(b) は4つの点と6つの直線セグメントで3つの面が作られる例です。(c) は曲線が含まれているため不正な出力であり、(d) は直線セグメントが交差しているため不正な出力です。

入力

1行目に、3つの正の整数 $N, M, K$ が与えられます。これらはそれぞれ点の数、セグメントの数、作成すべき面の数を表します ($3 \le N \le 3000, 0 \le M, 0 \le K$)。

与えられた $N, M, K$ に対して、解が存在することが保証されています。

出力

最初の $N$ 行に、選択した点の座標を出力してください。$i$ 行目には、$i$ 番目の点の座標を表す2つの整数 $x_i$ と $y_i$ ($1 \le x_i, y_i \le 79$) を出力してください。

続いて、セグメントを表す $M$ 行を出力してください。各行には、そのセグメントによって結ばれる点のインデックスを表す2つの整数（$1$ から $N$ の間）を出力してください。

複数の解が存在する場合は、そのうちのどれを出力しても構いません。

入出力例

入出力例 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

注記

左の図は4つの点と6つの直線セグメントで3つの面が作られる様子を示しています。 右の図は6つの点と5つの直線セグメントで1つの面が作られる様子を示しています。