Minje 经营着一家游戏厅。其中一个游戏在一个大小为 $N \times M$ 的网格中进行。每个单元格中都写有 L、R、U、D 四个字符之一，分别代表左、右、上、下方向。玩家可以在网格内自由移动，但他不能向其所在单元格标注的方向移动，也不能移出网格。

Minje 会在玩家进入并离开网格后清理网格。然而，清理所有 $N \times M$ 个单元格非常累人。因此，Minje 只想清理玩家可能访问过的单元格。

共有 $Q$ 名玩家参与了游戏。Minje 记得每位玩家在游戏过程中站立的第一个单元格和最后一个单元格。这些单元格不一定位于角落或边缘。请计算 Minje 需要清理的单元格数量。每场游戏都是独立的，不会影响其他游戏的结果。

输入格式

第一行包含三个整数 $N, M, Q$，分别表示网格的大小和玩家人数。($1 \le N, M \le 1000, 1 \le Q \le 300\,000$)

接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，表示网格中每个单元格标注的字符。每个字符都是 L、R、U、D 中的一个。

接下来的 $Q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$。这表示玩家在单元格 $(x_1, y_1)$ 开始游戏，并在单元格 $(x_2, y_2)$ 结束游戏。($1 \le x_1, x_2 \le N, 1 \le y_1, y_2 \le M$)

输出格式

对于每组询问，按输入顺序输出一行，包含一个整数，表示答案。查询的答案为：

• 如果无法从单元格 $(x_1, y_1)$ 移动到单元格 $(x_2, y_2)$，则输出 0。
• 否则，输出 Minje 需要清理的单元格数量。

样例

样例输入 1

5 5 5
DDDDD
RDDDL
RRDLL
RUUUL
UUUUU
1 1 5 5
2 2 5 5
3 3 5 5
4 4 5 5
5 5 5 5

样例输出 1

0
14
20
14
5