問題文

1 辺の長さが N の立方体を、 N^3 個の 1 辺の長さが 1 の立方体のピースに分割します。この中から次の条件を満たすようにいくつかのピースを選ぶ方法のうち、選ぶ個数が最も小さいものを一つ構築してください。

• 立方体の面に垂直な 3 方向のうちどの方向から見ても、穴が隣接していない。

ここである方向から見たときの穴とは、ピース N 個が重なって見える 1 辺の長さが 1 の正方形のうち、それら N 個のピースが一つも選ばれていないものを指します。また、 2 つの穴が隣接するとは、それらが辺を共有することを指します。

より厳密には、分割後のピースを 3 整数の組 (x_i,y_i,z_i) に対応させた時、m を選んだ立方体の個数として、3 整数の組の集合 S = \{(x_1,y_1,z_1), (x_2,y_2,z_2), \ldots, (x_m,y_m,z_m)\} (1 \leq x_i,y_i,z_i \leq N) で以下の条件を全て満たすもののうち m が最小となるものを 1 つ構築してください。

• 全ての整数 y, z, y', z' (1 \leq y, z, y', z' \leq N, \lvert y-y' \rvert + \lvert z - z' \rvert = 1) に対し、 (x, y, z) \in S または (x, y', z') \in S を満たす整数 x (1 \leq x \leq N) が存在する。
• 全ての整数 z, x, z', x' (1 \leq z, x, z', x' \leq N, \lvert z-z' \rvert + \lvert x - x' \rvert = 1) に対し、 (x, y, z) \in S または (x', y, z') \in S を満たす整数 y (1 \leq y \leq N) が存在する。
• 全ての整数 x, y, x', y' (1 \leq x, y, x', y' \leq N, \lvert x-x' \rvert + \lvert y - y' \rvert = 1) に対し、 (x, y, z) \in S または (x', y', z) \in S を満たす整数 z (1 \leq z \leq N) が存在する。

なお、この問題の制約下でこれらの条件を満たす選び方が存在することが証明できます。

制約

• 1 \leq N \leq 1000
• 入力はすべて整数

入力例 1

2

出力例 1

2
1 1 2
2 2 1

下の図のようになります。

3 方向いずれから見ても穴が隣り合っていることはありません。