Snake

Everyone has played the Snake game. Now, there is a modified version of the game. Like the traditional game, the snake moves within an activity area and eats food, but this modified version has some special rules.

Activity Area

The activity area for the snake is an $R \times C$ grid $A$. The snake cannot move outside the boundaries of this grid. The cell at row $i$ and column $j$ is denoted by $A_{i,j}$. Each cell has an integer weight, denoted by $w(A_{i,j})$. $0 \le w(A_{i,j}) \le 8$. When $w(A_{i,j}) = 0$, $A_{i,j}$ is impassable; when $w(A_{i,j}) > 0$, $A_{i,j}$ is passable.

Directions

For $P=(X_0, Y_0)$ and $Q=(X_1, Y_1)$, there are four basic directions: Left (L): $X_0 = X_1$ and $Y_0 = Y_1 - 1$, then $P$ is to the left of $Q$. Right (R): $X_0 = X_1$ and $Y_0 = Y_1 + 1$, then $P$ is to the right of $Q$. Up (U): $X_0 = X_1 - 1$ and $Y_0 = Y_1$, then $P$ is above $Q$. Down (D): $X_0 = X_1 + 1$ and $Y_0 = Y_1$, then $P$ is below $Q$.

The Snake

The snake $B$ is a figure occupying several cells. The number of occupied cells is the length of the snake, denoted by $m$. The snake is represented from head to tail as $B_1, B_2, \dots, B_m$. Let $p$ be the configuration of the snake. If $B_i$ is located at row $X_i$ and column $Y_i$, then $p(B_i) = (X_i, Y_i)$. Initially, $m=4$, and the following constraints must be satisfied throughout the movement: For $B_i$ and $B_{i+1}$ ($1 \le i < m$), which are adjacent parts of the snake, $B_i$ must be in one of the L, R, U, or D directions relative to $B_{i+1}$. For $B_i$ and $B_j$ ($1 \le i < j \le m$), where $p(B_i) = (X_i, Y_i)$ and $p(B_j) = (X_j, Y_j)$, it must be that $X_i \neq X_j$ or $Y_i \neq Y_j$. In other words, no part of the snake's body can intersect itself.

Food

There is some food in the activity area. Each piece of food is located on a passable cell, and food items do not overlap. Each piece of food can be eaten only once.

Movement

If the cell $A_{i,j}$ in one of the L, R, U, or D directions from the snake's head $B_1$ is passable and contains no food, the snake can move in that direction. The new head is at $A_{i,j}$. Let $p'$ be the new configuration of the snake: $p'(B_k) = p(B_{k-1})$ for $2 \le k \le m$. $p'(B_k) = (i, j)$ for $k = 1$.

Eating

If the cell $A_{i,j}$ in one of the L, R, U, or D directions from the snake's head $B_1$ is passable and contains food, the snake can move in that direction to eat. The new head is at $A_{i,j}$, and the new length of the snake is $m' = m + 1$. Let $p'$ be the new position of the snake: $p'(B_k) = p(B_{k-1})$ for $2 \le k \le m'$. $p'(B_k) = (i, j)$ for $k = 1$.

Note: After moving or eating, one only needs to consider whether the new configuration satisfies the constraints; the process of transformation does not need to be considered. That is, the head of a snake in a valid configuration can move to the position of its tail, because after the transformation, the head and tail will not overlap.

Time Required for Movement or Eating

Moving or eating consumes time. Let $P$ be the cell where the head is located before the move or eat, and $Q$ be the cell where the head is located after the move or eat. The time consumed for this action is $|w(P) - w(Q)| + 1$.

The initial position of the snake and the locations of all food are given at the start of the game. Your task is to eat all the food in the minimum amount of time.

Input

The first line contains two positive integers $R$ and $C$. The next $R$ lines each contain $C$ digits without spaces. The $j$-th digit in the $i$-th line is $w(A_{i,j})$. The next 4 lines each contain two positive integers. The $i$-th line contains $X_i, Y_i$, representing $p(B_i) = (X_i, Y_i)$. The next line contains a positive integer $N$, representing the number of food items. The next $N$ lines each contain two positive integers $i, j$, representing that there is food at $A_{i,j}$.

Output

If the snake cannot eat all the food, output "No solution." (without quotes). Otherwise, output: The first line contains an integer representing the total time spent. The second line contains a string consisting of L, R, U, D, representing the snake's movement plan. If there are multiple possibilities, you only need to output one of them.

Examples

Input 1

5 5
11011
11011
11011
11011
11411
1 1
2 1
3 1
4 1
4
5 5
4 4
2 5
1 4

Output 1

21
RDDDDRRRULURULU

Subtasks

• For 20% of the data, $N \le 1$.
• For 40% of the data, $N \le 2$.
• For 60% of the data, $N \le 3$.
• For 100% of the data, $N \le 4$.
• For 30% of the data, $R \times C \le 36$.
• For 100% of the data, $R \le 12, C \le 12$.