問題文

正整数 $N$ が与えられます。 $N$ 頂点 $M$ 辺の重み付き連結無向グラフであって、以下の条件を満たすものを一つ構築してください。ただし、頂点には $1$ から $N$ までの、辺には $1$ から $M$ までの番号がそれぞれ付けられているものとします。

• 自己ループを含まない(多重辺はあっても良い)
• $M \leq 2N-3$
• $1 \leq i < j \leq N$ を満たす全ての整数の組 $(i,j)$ に対して、頂点 $i$ から $j$ への単純パスであって、そのパスに含まれる辺の重みの総和が平方数であるものが存在する
• 全ての辺の重みは相異なる $1$ 以上 $200$ 以下の整数である

さらに、あなたが構築したグラフにおける、頂点 $i$ から $j$ へ向かう単純パスであって、そのパスに含まれる辺の重みの総和が平方数であるものの一つを $P_{i,j}$ とします。また、 $P_{i,j}$ が通る辺の番号を通る順に並べた数列を $Q_{i,j}$ とします。 $1 \leq i < j \leq N$ を満たす全ての整数の組 $(i,j)$ に対して、$Q_{i,j}$ を出力してください。

なお、制約下で条件を満たすグラフは必ず構築可能であることが示せます。

制約

• $2 \leq N \leq 100$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

まず、条件を満たすグラフを出力せよ。一行目に辺の本数 $M$ を、続く $M$ 行のうち $i$ 行目には、 辺 $i$ の端点 $U_{i}$ , $V_{i}$ , 重み $C_{i}$ を以下の形式で出力せよ。

$U_{i}$ $V_{i}$ $C_{i}$

さらに、 $1 \leq i < j \leq N$ を満たす全ての整数の組 $(i,j)$ に対して $(i,j)$ の辞書順に、以下の形式で出力を行え。

$|Q_{i,j}|$  $Q_{i,j}$

ただし、 $Q_{i,j}$ の各要素は空白区切りにせよ。

サンプル

3

3
1 2 16
2 3 9
1 3 25
1 1
1 3
1 2