Problem

There is an $N\times N$ grid, with rows numbered $1$ to $N$ from top to bottom and columns numbered $1$ to $N$ from left to right. The cell at the intersection of row $i$ and column $j$ is denoted $(i,j)$.

Chef is standing at cell $(1,1)$ of the grid, and would like to get to cell $(N,N)$. To do this, he can move one step up/down/left/right from the cell he’s standing at, as long as he remains within the grid.
That is, from cell $(i,j)$ he can move to one of $\{(i-1,j),(i+1,j),(i,j-1),(i,j+1)\}$.
Unfortunately, there are snakes in the grid!

Each snake has an initial cell (��,��)(xi​,yi​), and a direction ��di​. The direction is one of 'U', 'D', 'L', or 'R' – denoting up, down, left, and right respectively. This snake acts as follows:

• In the beginning, it occupies only point (��,��)(xi​,yi​).
• At the end of each second, it will extend one unit in its respective direction.
  For example, if (��,��)=(4,7)(xi​,yi​)=(4,7) and ��=Ldi​=L, then:
  • At first, this snake occupies $(4,7)$
  • After one second, it occupies $(4,7)$ and $(4,6)$ (i.e, it occupies one point more to the left).
  • After another second, it occupies $(4,7),(4,6),$ and $(4,5)$; and so on.

Snakes stop extending when they reach the boundary of the grid.
Multiple snakes are allowed to occupy the same cell.
Chef calls a point dangerous if at least one snake occupies it.
The danger of a path from $(1,1)$ to $(N,N)$ is the number of dangerous points it contains.

Help Chef answer $Q$ queries of the following form:

• Given $T$, what’s the minimum danger of a path from $(1,1)$ to $(N,N)$ at the start of time $T$?

Input Format

• The first line of each test case contains two space-separated integers $N$ and $Q$ — the size of the grid and the number of queries.
• The next $N$ lines describe the grid. The $i$-th of them contains a string ��Si​ of length $N$, denoting row $i$.
• Each character of the string is one of five from ".LRUD", where '.' denotes an empty cell and the other four denote a snake at that cell with the specified direction.
• The next $Q$ lines describe the queries. The $i$-th of them contains a single integer ��Ti​, the time for the $i$-th query.

Output Format

For each test case, output $Q$ lines. The $i$-th of them should contain a single integer: the answer to the $i$-th query.

Constraints

Sample 1:

5 3
....L
..D..
.....
R..U.
.....
1
3
6

0
1
3

Explanation:

The initial grid looks as follows:

with one possible path from $(1,1)$ to $(5,5)$ marked out, that has danger $0$.
This is the answer to the first query.

The second query has $T=3$, meaning we’re at the start of the third second. All snakes have moved twice (recall that snakes move at the end of a second). One possible path with danger $1$ now is:

The third query is $T=6$, so all snakes have moved five times. One optimal path with danger $3$ is:

Note that the cells $(1,1)$ and/or $(N,N)$ may themselves be dangerous, in which case they must be counted into the answer as well.