你的任務是在坐標平面上選取 $N$ 個點，並繪製 $M$ 條連接這些點的直線段，使得平面被這些線段分割出恰好 $K$ 個有限面（finite faces）。這裡的「面」是指平面被線段分割後的區域。其中一個區域是無限大的，應予以忽略。

更正式地說，你的配置必須滿足以下條件：

• 每個點的 $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 個面。