Story

Haruku was suddenly seized by an urge to destroy, so he has decided to blow up all the buildings in the town where he lives.

The town has several bomb shops that sell bombs, but buying a bomb costs money. Carrying bombs around also incurs a certain cost.

Choose well how to buy and use the bombs, and blow up all the buildings at a low cost.

Problem Statement

There is a town consisting of $N \times N$ squares. The top-left square is $(0,0)$, and the square reached by moving $i$ squares down and $j$ squares right from it is denoted by $(i,j)$.

The square $(i,j)$ is represented by the character $A_{i,j}$. The meaning of each character is as follows.

• ....An empty lot with nothing on it.
• #...An ordinary building.
• @...A bomb shop. At least one always exists.

The bomb shops in this town carry $M$ types of bombs, numbered $1,2,...,M$. Bomb $i$ has cost $C_i$ and blasts $L_i$ locations $(a_1,b_1),(a_2,b_2),\dots,(a_{L_i},b_{L_i})$.

Every bomb shop has $10^{100}$ of each bomb in stock.

Initially, Haruku is at $(0,0)$.

Haruku's goal is to turn all # and @ squares into .. To do so, he can perform one of the following actions per $1$ action.

• Move
  • Choose one of L,R,U,D and move as follows.
    • L...from $(i,j)$ to $(i,j-1)$
    • R...from $(i,j)$ to $(i,j+1)$
    • U...from $(i,j)$ to $(i-1,j)$
    • D...from $(i,j)$ to $(i+1,j)$
  • He can move onto any of the .,#,@ squares, but he cannot move outside the grid.
  • Let $b$ be the total number of bombs he holds. The cost of this action is as follows.
    • If the destination is ....the cost is $(b+1)^2$.
    • If the destination is # or @...the cost is $2\times(b+1)^2$.
• Buy a bomb
  • This can be done only when the current square is @.
  • Choose an integer $x$ and buy bomb $x$. Here, $1\leq x\leq M$ must hold.
  • This costs $C_x$, and the number of bombs $x$ he holds increases by $1$.
• Use a bomb
  • Choose an integer $x$ and use bomb $x$. Here, he must hold at least $1$ of bomb $x$.
  • When he is at $(i,j)$, the $L_x$ squares $(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})$ are blasted and become .. Those outside the grid are ignored.
  • This action has no cost, and the number of bombs $x$ he holds decreases by $1$.
  • Note that on squares that have become . through this action, he may no longer be able to buy bombs and the movement cost may change from then on.

Turn all squares into . using at most $100000$ actions. Among such ways, make the cost as small as possible.

Input

$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}$ is one of .,#,@
• There exists a pair $(i,j)$ such that $A_{i,j}$ is @
• $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)$

Output

Let $Q$ be the number of actions. Print $Q+1$ lines.

On line $1$, print $Q$.

On each of the following $Q$ lines, print as follows.

• Move

  1 x
  

  $x$ must be one of L,R,U,D. Move in direction $x$.

• Buy a bomb

  2 y
  

  $1\leq y\leq M$ must hold. Buy bomb $y$.

• Use a bomb

  3 z
  

  You must hold at least $1$ of bomb $z$. Use bomb $z$.

If you do not follow this format or the conditions in the problem statement, the judge result is undefined.

Scoring

If the output is valid, it is judged as AC. Let $c$ be the sum of the costs of all actions. The score is calculated as follows.

• If a square other than . exists after all actions…the score is $1$.
• If no square other than . exists after all actions…the score is $\max(10,\lfloor \frac{10^{12}}{10^4+c} \rfloor)$.

The score of a submission is the sum of the scores over all 50 test cases.

Input Generation

You do not need to read this section to understand the problem.

The test cases for this problem were generated as follows.

Here, $\text{rand}(l,r)$ is a function that returns a real number uniformly at random between $l$ inclusive and $r$ exclusive, and $\rm{normal}(\mu,\sigma)$ is a function that returns a random real number from the normal distribution with mean $\mu$ and standard deviation $\sigma$.

• Let $N=50,M=20$.
• Initialize every square of $A$ to ..
• Let the density be $d=\rm{rand}(0.5,0.8)$, and turn each square into # with probability $d$.
• Then, let the number of shops be $s=\lfloor \max(10,\rm{normal}(50,10))\rfloor$, choose $s$ squares uniformly at random, and turn them into @.
• Create $M$ bombs as follows.
  • Let the strength of the bomb be $s_i=\rm{rand}(0.2,1)$.
  • For every pair $(a_i,b_i)$ satisfying $-20 \leq a_i,b_i \leq 20$, adopt it with probability $(\max(|a_i|,|b_i|)\times s_i+1)^{-1}$.
  • Let $L_i$ be the number of adopted integer pairs, and let $C_i=\lfloor \max(1,\min(4000,L_i\times \rm{normal}(1,0.2)))\rfloor$.
  • Sort the adopted integer pairs in ascending order of $|a_i|+|b_i|$.

The seed values used will be published after the contest ends. (SHA256...b7384d5a5e0c4a34374b6544b3579f3d9500b2321e4e7d22c92d4db7ba4c5a78)

Tools

GitHub has sample input and output, sample code in C++ and Python, the judge code, an input generator, a visualizer, and more.

See README.md for details.

During the contest, only visualizer results for seed=0 may be shared. After the contest, you may freely share any board.

When sharing, please use #yukicoder and #HakaiProject!

Input