これは出力のみの問題です。テキストファイルではなく、出力を表示するプログラムを提出する必要があることに注意してください。

グラフの有効な 3-彩色とは、グラフの各頂点に対して集合 $\{1, 2, 3\}$ から色（番号）を割り当てることであり、グラフの任意の辺 $(u, v)$ に対して、頂点 $u$ と $v$ が異なる色を持つようにするものです。$n$ 個の頂点を持つグラフの 3-彩色の数は最大で $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)$ の形式でグラフの辺を出力してください。

次に、$k = 1$ から $500$ まで、それぞれ以下の処理を行ってください。

この特定の $k$ に対して追加する辺の数 $e$ ($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 1 1 3 ... (k=3から500までの出力が続く) ```

注記

サンプル出力は例として示されています。これには $k = 1, 2$ の場合の出力が含まれています。