問題文

高橋君は木 $T$ を持っています。$T$ は $500$ 個以下の頂点からなり、各辺には正整数の重みがついています。

高橋君は木 $T$ を用いて以下の操作を行いました。

1. 木 $T$ の頂点からいくつかを選び、頂点集合 $S$ を作る。
2. $S$ から異なる二頂点を選ぶすべての組み合わせについて、二頂点間の距離を計算し、それぞれの距離を黒板に書き出す。 ここで、二頂点間の距離とは、木 $T$ におけるその二頂点を結ぶ単純パスに含まれる辺の重みの総和を指す。

$K$ 要素からなる集合 $D = \{D_1, D_2, \dots, D_K\}$ が与えられます。$D$ の各要素は正の偶数です。 黒板に書き出されたすべての数は $D$ に含まれており、また、$D$ に含まれるすべての数がそれぞれ黒板に一回以上書き出されたことがわかっています。

木 $T$ と高橋君が作成した頂点集合 $S$ の組み合わせとして、あり得るものを一つ求めてください。 なお、この問題の制約下でそのような木と頂点集合の組み合わせが常に存在することが示せます。

入力

$K$
$D_1\ D_2\dots D_K$

• $1 \le K \le 150$
• $2 \le D_i \le 300$
• $D_i$ は偶数である
• $i \neq j$ ならば、$D_i \neq D_j$
• 入力はすべて整数である

出力

以下の形式で木 $T$ と高橋君が選んだ頂点集合 $S$ の組み合わせとしてあり得るものを出力してください。

$N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
$M$
$S_1\ S_2\dots S_M$

$1$ 行目に木 $T$ の頂点数 $N(2 \le N \le 500)$ を出力してください。

$2$ 行目から $N$ 行目の各行には、木 $T$ の $N-1$ 辺の情報を一辺ずつ出力してください。 $i+1$ 行目には $3$ つの整数 $u_i, v_i, w_i(1 \le u_i, v_i \le N, 1 \le w_i \le 1000)$ を空白区切りで出力してください。 この出力は、木 $T$ において $i$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ を重み $w_i$ で双方向に結んでいることを指しています。

$N+1$ 行目に頂点集合 $S$ の大きさ $M(2 \le M \le N)$ を出力してください。

$N+2$ 行目には、$S$ に含まれる $M$ 個の頂点の番号を空白区切りで出力してください。 $S_1, S_2 \dots S_M$ は互いに相異なる $1$ 以上 $N$ 以下の整数である必要があります。

サンプル

3
6 2 4

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