/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
家庭菜園を始めたXは、野菜の手入れと収穫の計画を立てています。
Xの庭は N 行 N 列の区画からなり、区画のi 行 j 列目には品質が A_{i,j} の野菜があります。各区画からはそれぞれ一度だけ野菜を収穫することができます。
Xは以下のどちらかの操作を最大で M 回実行することができます。各操作は、野菜がまだ収穫されていない区画をひとつ指定して実行します。野菜が既に収穫された区画を指定した場合、何もしません。
- （1）手入れ： 選んだ区画にある野菜の品質を 1 増やします。
-
（2）収穫： 選んだ区画とその周辺の区画から野菜を収穫します。収穫するためには次の条件を満たす必要があります。
- 選んだ区画にある野菜の品質を Kとします。
- 選んだ区画から「まだ収穫されていない品質Kの野菜がある区画」だけを辿って上下左右に連結している区画の集合を S とします。（ S には選んだ区画自身を含みます。）
- S に含まれる区画が K 個以上の場合、S に含まれる全ての区画にある野菜を収穫します。
- S に含まれる区画が K 個未満の場合、何もしません。
Xが収穫する野菜の品質の合計値がなるべく大きくなるような計画を立ててください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、Xが収穫する野菜の品質の合計がそのまま得点になります。
- テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。
入力
入力は以下の形式で標準入力から与えられます。
\(\begin{array}{lll}
N ~ M & & \\
A_{ 0,0 } & \ldots & A_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
A_{ N-1,0 } & \ldots & A_{ N-1,N-1 }
\end{array}\)
- N は庭の大きさを表す整数で、N = 50 を満たします。
- M は許容される操作回数の最大値を表す整数で、M = 2500 を満たします。
- A_{i,j} は i 行 j 列目の区画にある野菜の品質を表す整数で、1 ≤ A_{i,j} ≤ 9 を満たします。
出力
1行につき操作をひとつ、最大 M 行出力してください。
\(\begin{array}{lll}
\mathit{op}_0 & r_0 & c_0 \\
\mathit{op}_1 & r_1 & c_1 \\
\vdots & & \\
\end{array}\)
\(\mathit{op}_i\)は 手入れをする場合は1を、収穫する場合は2を出力し、その後に操作対象の区画（r_i 行 c_i 列目）をスペース区切りで出力してください。
テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータは\(A_{i,j}\) を \([1, 9]\) の範囲の整数から一様ランダムに生成します。
テストケースジェネレータはページ下部のリンクより提供しています。
入力例1
3 9 5 5 5 1 5 9 5 9 1
出力例1
2 0 0 1 1 0 1 1 0 1 1 0 1 1 0 2 0 0 2 2 2 1 2 1
| 庭 | 説明 | スコア |
|---|---|---|
 |
入力された庭の様子です。このサンプルは制約 N=50, M=2500 を満たしていません。 | 0 |
 |
最初の操作（2 0 0）では、 (0,0) から見た S に含まれる区画は (0,0), (0,1), (0,2), (1,1) の 4つなので、収穫できる条件を満たしていません。(1,1) と斜め方向で隣接している区画 (2,0) は S に含まれない点に注意してください。 |
0 |
 |
次の4回の操作（1 1 0を4回繰り返し）で (1,0) にある野菜の品質を 1 から 5 に変更します。 |
0 |
 |
次の操作（2 0 0）では、 (0,0) から見た S に含まれる区画は (0,0), (0,1), (0,2), (1,0), (1,1), (2,0) の 6 つなので、収穫できる条件を満たしています。 S に含まれる 6 つの区画のそれぞれから、品質 5 の野菜を収穫します。 |
30 |
 |
次の操作（2 2 2）では、 (2,2) にある野菜を収穫します。品質が 1 の野菜は単体で収穫することもできます。 |
31 |
 |
最後の操作（1 2 1）では、 (2,1) にある野菜の品質を 9 から 10 に変更します。 A_{i,j} は 1 以上 9 以下の整数ですが、野菜の品質は手入れをすることで 10 以上の整数になることもあります。 |
31 |
ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。特に、Internet Explorer 上では動作しないことが確認されています。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。