题目描述

相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。

活动区域：

贪食蛇的活动区域是一个 $R$ 行 $C$ 列的网格 $A$，贪食蛇活动不能超过这个网格的范围。第 $i$ 行第 $j$ 列的方格用 $A_{i,j}$ 表示。每个方格有一个整数权值，记作 $w(A_{i,j})$。$0 \leq w(A_{i,j}) \leq 8$，$w(A_{i,j}) = 0$时，$A_{i,j}$ 禁止进入；$w(A_{i, j}) > 0$时，$A_{i, j}$ 允许进入。

方向：

对于 $P = (X_0, Y_0)$、$Q = (X_1, Y_1)$，有以下四种基本方向：

• 正左(L)：$X_0 = X_1$ 且 $Y_0 = Y_1 - 1$，则称 $P$ 位于 $Q$ 的正左方向。
• 正右(R)：$X_0 = X_1$ 且 $Y_0 = Y_1 + 1$，则称 $P$ 位于 $Q$ 的正右方向。
• 正上(U)：$X_0 = X_1 - 1$ 且 $Y_0 = Y_1$，则称 $P$ 位于 $Q$ 的正上方向。
• 正下(D)：$X_0 = X_1 + 1$ 且 $Y_0 = Y_1$，则称 $P$ 位于 $Q$ 的正下方向。

贪食蛇：

贪食蛇 $B$ 是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为 $m$，则贪食蛇从头到尾，用 $B_1, B_2, \dots, B_m$表示。记 $p$ 为贪食蛇的形态，若 $B_i$ 位于第 $X_i$ 行第 $Y_i$ 列，则 $p(B_i)=(X_i, Y_i)$。初始情况下，$m = 4$，且运动过程中始终需要满足以下限制：

• 对于 $B_i$ 和 $B_{i + 1}$ $(1 \leq i < m)$，就是贪食蛇的前、后相邻两部分，必须满足 $B_i$ 位于 $B_{i + 1}$ 的L、R、U、D四个方向之一。
• 对于 $B_i$ 和 $B_j$ $(1 \leq i < j \leq m)$，$p(B_i) = (X_i, Y_i)$，$p(B_j) = (X_j,Y_j)$，需要满足 $X_i \neq X_j$ 或 $Y_i \neq Y_j$ 。也就是说，贪食蛇身体的任意一部分不能相交。

食物：

贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。

贪食蛇的运动：

如果贪食蛇的头部 $B1$ 的L、R、U、D四个方向之一的 $A_{i, j}$ 能进入，且 $A_{i, j}$ 上不存在食物，则贪食蛇可以向该方向运动，新的头部位于 $A_{i, j}$ 上。记 $p'$ 为贪食蛇新的形态，则：

• $p'(B_k) = p(B_{k - 1})$，当 $2 \leq k \leq m$。
• $p'(B_k) = (i, j)$，当 $k = 1$。

贪食蛇的进食：

如果贪食蛇的头部 $B_1$ 的L、R、U、D四个方向之一的 $A_{i, j}$ 能进入，且 $A_{i,j}$ 上存在食物，则贪食蛇可以向该方向进食，新的头部位于 $A_{i, j}$ 上，蛇的新长度 $m'=m+1$。记 $p'$ 为贪食蛇新的位置，则：

• $p'(B_k) = p(B_{k-1})$，当 $2 \leq k \leq m'$。
• $p'(B_k) = (i,j)$，当 $k = 1$.

注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。

运动或进食所需要的时间：

贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是P，运动或进食后头部所在的方格是 $Q$，则此次运动或进食的所消耗的时间为 $|w(P) - w(Q)| + 1$。

游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。

输入格式

第一行，两个正整数 $R, C$。

接下来 $R$ 行，每行 $C$ 个没有空格分隔的数字。其中第 $i$ 行第 $j$ 个数字为 $w(A_{i, j})$。

接下来 $4$ 行，每行 $2$ 个正整数。第 $i$ 行的两个整数 $X_i, Y_i$，表示 $p(B_i) = (X_i, Y_i)$。

接下来一个正整数 $N$，表示食物的数量。

接下来 $N$ 行，每行 $2$ 个正整数 $i, j$，表示 $A_{i, j}$上存在一个食物。

输出格式

如果贪食蛇不能吃到所有的食物，输出 No solution.。

否则，输出：

第一行，一个整数，表示所需花费的时间；

第二行，一个由 L、R、U、D 组成的字符串，表示贪食蛇前进的方案。如果存在多种可能，你只需输出任意一种。

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

21
RDDDDRRRULURULU

提示

• 对于 $20\%$ 的数据，$N \leq 1$；
• 对于 $30\%$ 的数据，$R \times C \leq 36$；
• 对于 $40\%$ 的数据，$N \leq 2$；
• 对于 $60\%$ 的数据，$N \leq 3$；
• 对于 $100\%$ 的数据，$N \leq 4$，$R \leq 12$，$C \leq 12$。