問題文

$H \times W$ の長方形のマス目を、$1 \times 2$ または $2 \times 1$ の長方形の色付きタイルで完全に敷き詰めて、色付きグリッドを作ります。以下の条件を全て満たす敷き詰め方であって、使用する色の種類数が最も少なくなるものの一例を求めてください。

• 全てのタイルは、マス目のちょうど $2$ マスを完全に覆う
• タイルはマス目からはみ出してはならず、また異なるタイル同士が重なってはならない
• 各タイルを構成する $2$ つのマスは異なる色で塗られている
• 完成した色付きグリッド全体において、同じ色が塗られた領域は四近傍で連結である

ただし、同じ色が塗られた領域が四近傍で連結であるとは、同じ色 $c$ で塗られた任意の $2$ マス $A, B$ について、$A$ から $B$ まで上下左右に隣接する色 $c$ で塗られたマスのみを通って移動できることを指します。

なお、制約の条件下で必ずそのような敷き詰め方が存在することが示せます。

制約

• 入力は全て整数
• $1 \leq H, W \leq 200$
• $HW$ は偶数

入力

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

$H\ W$

出力

使用する色の種類数が最も少なくなる敷き詰め方の一例を、以下の形式で出力してください。

$C$
$x_{1, 1}\ y_{1, 1}\ c_{1, 1}\ x_{1, 2}\ y_{1, 2}\ c_{1, 2}$
$x_{2, 1}\ y_{2, 1}\ c_{2, 1}\ x_{2, 2}\ y_{2, 2}\ c_{2, 2}$
$\vdots$
$x_{\frac{HW}{2}, 1}\ y_{\frac{HW}{2}, 1}\ c_{\frac{HW}{2}, 1}\ x_{\frac{HW}{2}, 2}\ y_{\frac{HW}{2}, 2}\ c_{\frac{HW}{2}, 2}$

ただし、$C$ は使用する色の種類数、マス目の上から $s$ 行目、左から $t$ 番目のマスを $(s, t)$ と表すとき、$i$ 番目のタイルが覆うマス目の $2$ マスを $(x_{i, 1}, y_{i, 1})$ と $(x_{i, 2}, y_{i, 2})$、それら $2$ マスの色をそれぞれ $c_{i, 1}$、 $c_{i, 2}$ とします。

$1 \leq c_{i, 1}, c_{i, 2} \leq C$ を満たし、$1$ 以上 $C$ 以下の各色が少なくとも $1$ つのマスに塗られている必要がある事に注意してください。なお、タイルを出力する順番は任意です。

最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

2 2

出力

2
1 1 1 1 2 2
2 2 2 2 1 1

出力例の敷き詰めは次の図のようになります。

このケースは部分点ケースに含まれます。

以下の出力も問題の条件を満たしますが、使用する色の種類数が最少でないため、正答ではありません。

3
1 1 3 1 2 2
2 2 2 2 1 1

サンプル2

入力

4 1

出力

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

出力例の敷き詰めは次の図のようになります。

同じ色が塗られた領域が連結となるためには、$3$ 色以上必要になります。

このケースは部分点ケースに含まれません。