ストーリー

はるく君は、唐突に破壊衝動に駆られたので、住んでいる町にあるすべての建物を爆破させることにしました。

町には爆弾屋がいくつかあり、爆弾を売っていますが、爆弾を買うのにはコストがかかります。また、爆弾を持ち運ぶのにも一定のコストがかかります。

爆弾の買い方と使い方をうまく定めることで、少ないコストですべての建物を爆破させてください。

問題文

$N \times N$ マスの町があります。最も左上にあるマスを $(0,0)$ とし、そこから下に $i$ マス、右に $j$ マス進んだ先のマスを $(i,j)$ と表します。

$(i,j)$ のマスは文字 $A_{i,j}$ で表されます。各文字の意味は以下の通りです。

• ....何もない空き地。
• #...普通の建物。
• @...爆弾屋。必ず存在する。

この町にある爆弾屋で取り扱われている爆弾は $M$ 種類あり、$1,2,...,M$ と番号がつけられています。爆弾 $i$ のコストは $C_i$ で、爆破する場所が $(a_1,b_1),(a_2,b_2),\dots,(a_{L_i},b_{L_i})$ の $L_i$ 箇所あります。

また、すべての爆弾はどの爆弾屋にも $10^{100}$ 個の在庫があるものとします。

最初、はるく君は $(0,0)$ にいます。

はるく君の目的は、#と@のマスをすべて.にすることです。そのために、はるく君は $1$ 回の行動で以下のいずれかの行動をすることができます。

• 移動する
  • L,R,U,Dのいずれかを決め、下記の通りに移動する。
    • L...$(i,j)$ から $(i,j-1)$
    • R...$(i,j)$ から $(i,j+1)$
    • U...$(i,j)$ から $(i-1,j)$
    • D...$(i,j)$ から $(i+1,j)$
  • .,#,@のどのマスにも移動できるが、マスをはみ出して移動することはできない。
  • 持っているすべての爆弾の数を $b$ として、この行動のコストは以下である。
    • 移動先が....コストが $(b+1)^2$ かかる。
    • 移動先が#または@...コストが $2\times(b+1)^2$ かかる。
• 爆弾を買う
  • いまいるマスが@であるときのみ行える。
  • 整数 $x$ を決め、爆弾 $x$ を購入する。ここで、$1\leq x\leq M$ を満たす必要がある。
  • コストが $C_x$ かかり、持っている爆弾 $x$ の数が $1$ 増える。
• 爆弾を使う
  • 整数 $x$ を決め、爆弾 $x$ を使用する。ここで、爆弾 $x$ を $1$ つ以上持っている必要がある。
  • $(i,j)$ にいるとき、$(i+a_{x,1},j+b_{x,1}),(i+a_{x,2},j+b_{x,2}),\dots,(i+a_{x,L_x},j+b_{x,L_x})$ の $L_x$ マスが爆破され.になる。ただし、マスの外に出ているようなものは無視される。
  • この行動にコストはかからず、持っている爆弾 $x$ の数が $1$ 減る。
  • この行動によって.になったマスでは、今後爆弾を買えなかったり移動のコストが変化する可能性があることに注意せよ。

高々 $100000$ 回以内の行動で、すべてのマスを.にしてください。その中でも、できる限りコストを小さくしてください。

入力

$N\ M$
$A_{0,0}A_{0,1}\dots A_{0,N-1}$
$A_{1,0}A_{1,1}\dots A_{1,N-1}$
$\vdots$
$A_{N-1,0}A_{N-1,1}\dots A_{N-1,N-1}$
$C_1\ L_1$
$a_{1,1}\ b_{1,1}$
$a_{1,2}\ b_{1,2}$
$\vdots$
$a_{1,L_1}\ b_{1,L_1}$
$C_2\ L_2$
$a_{2,1}\ b_{2,1}$
$a_{2,2}\ b_{2,2}$
$\vdots$
$a_{2,L_2}\ b_{2,L_2}$
$\vdots$
$C_M\ L_M$
$a_{M,1}\ b_{M,1}$
$a_{M,2}\ b_{M,2}$
$\vdots$
$a_{M,L_M}\ b_{M,L_M}$

• $N=50$
• $M=20$
• $A_{i,j}$ は.,#,@のいずれか
• $A_{i,j}$ が@となる $(i,j)$ の組が存在する
• $1\leq C_i \leq 4000$
• $1\leq L_i \leq 2000$
• $-20\leq a_{i,j},b_{i,j}\leq 20$
• $(a_{i,j},b_{i,j})\ne (a_{i,k},b_{i,k})(j\ne k)$
• $(a_{i,1},b_{i,1})=(0,0)$

出力

行動の回数を $Q$ 回として、$Q+1$ 行出力してください。

$1$ 行目には $Q$ を出力してください。

続く $Q$ 行に、以下のように出力してください。

• 移動する

  1 x
  

  $x$ はL,R,U,Dのいずれかでなければならない。$x$ の方向に移動する。

• 爆弾を買う

  2 y
  

  $1\leq y\leq M$ でなければならない。爆弾 $y$ を購入する。

• 爆弾を使う

  3 z
  

  爆弾 $z$ を $1$ つ以上持っていなければならない。爆弾 $z$ を使用する。

この形式や問題文中の条件を守らなかった場合、判定結果は不定です。

得点

出力が正しい場合、ACと判定されます。すべての行動のコストの和を $c$ として、得点は以下のように計算されます。

• すべての行動後に. 以外のマスが存在する…得点は $1$ である。
• すべての行動後に. 以外のマスが存在しない…得点は $\max(10,\lfloor \frac{10^{12}}{10^4+c} \rfloor)$ である。

提出のスコアは、50個のテストケースすべての得点の合計です。

入力生成方法

この項を読まなくても問題の理解に支障はありません。

この問題のテストケースは以下のようにして生成されました。

ただし、$\text{rand}(l,r)$を $l$ 以上 $r$ 未満の実数を一様ランダムに返す関数、$\rm{normal}(\mu,\sigma)$ を平均 $\mu$ 、標準偏差 $\sigma$ の正規分布から実数をランダムに返す関数とします。

• $N=50,M=20$ とする
• $A$ の各マスを.で初期化する
• 密度 $d=\rm{rand}(0.5,0.8)$ とし、各マスについて、確率 $d$ で # にする
• その後、店数 $s=\lfloor \max(10,\rm{normal}(50,10))\rfloor$ とし、マスを一様ランダムに $s$ マス選んで @ にする
• 以下のように爆弾を $M$ 個作成する。
  • 爆弾の強さ $s_i=\rm{rand}(0.2,1)$ とする。
  • $-20 \leq a_i,b_i \leq 20$ を満たすすべての $(a_i,b_i)$ の組について、確率 $(\max(|a_i|,|b_i|)\times s_i+1)^{-1}$ で採用する。
  • $L_i$ を採用した整数の組の数として、$C_i=\lfloor \max(1,\min(4000,L_i\times \rm{normal}(1,0.2)))\rfloor$ とする。
  • 採用した整数の組を $|a_i|+|b_i|$ の昇順にソートする。

コンテスト終了後に、使用されたseed値が公開されます。(SHA256...b7384d5a5e0c4a34374b6544b3579f3d9500b2321e4e7d22c92d4db7ba4c5a78)

各種ツール

GitHubにサンプル入出力、C++とPythonのサンプルコード、ジャッジコード、入力ジェネレータ、ビジュアライザ等があります。

詳しくはREADME.mdを読んでください。

ビジュアライザの結果は、コンテスト中はseed=0のもののみ共有可能とします。コンテスト後は自由な盤面を共有してかまいません。

共有する際は、ぜひ#yukicoderと#HakaiProjectを使用してください！

入力