CF1335F.Robots on a Grid

There is a rectangular grid of size $n \times m$. Each cell of the grid is colored black ('0') or white ('1'). The color of the cell $(i, j)$ is $c_{i, j}$. You are also given a map of directions: for each cell, there is a direction $s_{i, j}$ which is one of the four characters 'U', 'R', 'D' and 'L'.

• If $s_{i, j}$ is 'U' then there is a transition from the cell $(i, j)$ to the cell $(i - 1, j)$;
• if $s_{i, j}$ is 'R' then there is a transition from the cell $(i, j)$ to the cell $(i, j + 1)$;
• if $s_{i, j}$ is 'D' then there is a transition from the cell $(i, j)$ to the cell $(i + 1, j)$;
• if $s_{i, j}$ is 'L' then there is a transition from the cell $(i, j)$ to the cell $(i, j - 1)$.

It is guaranteed that the top row doesn't contain characters 'U', the bottom row doesn't contain characters 'D', the leftmost column doesn't contain characters 'L' and the rightmost column doesn't contain characters 'R'.

You want to place some robots in this field (at most one robot in a cell). The following conditions should be satisfied.

• Firstly, each robot should move every time (i.e. it cannot skip the move). During one move each robot goes to the adjacent cell depending on the current direction.
• Secondly, you have to place robots in such a way that there is no move before which two different robots occupy the same cell (it also means that you cannot place two robots in the same cell). I.e. if the grid is "RL" (one row, two columns, colors does not matter there) then you can place two robots in cells $(1, 1)$ and $(1, 2)$, but if the grid is "RLL" then you cannot place robots in cells $(1, 1)$ and $(1, 3)$ because during the first second both robots will occupy the cell $(1, 2)$.

The robots make an infinite number of moves.

Your task is to place the maximum number of robots to satisfy all the conditions described above and among all such ways, you have to choose one where the number of black cells occupied by robots before all movements is the maximum possible. Note that you can place robots only before all movements.

You have to answer $t$ independent test cases.

有一个大小为 $n \times m$ 的矩形网格。网格中每个单元格被染成黑色（'0'）或白色（'1'）。单元格 $(i, j)$ 的颜色为 $c_{i, j}$。同时，你还会得到一个方向地图：对每个单元格，给定一个方向 $s_{i, j}$，其值为四个字符之一：'U'、'R'、'D' 或 'L'。

• 若 $s_{i, j}$ 为 'U'，则存在从单元格 $(i, j)$ 到单元格 $(i - 1, j)$ 的转移；
• 若 $s_{i, j}$ 为 'R'，则存在从单元格 $(i, j)$ 到单元格 $(i, j + 1)$ 的转移；
• 若 $s_{i, j}$ 为 'D'，则存在从单元格 $(i, j)$ 到单元格 $(i + 1, j)$ 的转移；
• 若 $s_{i, j}$ 为 'L'，则存在从单元格 $(i, j)$ 到单元格 $(i, j - 1)$ 的转移。

保证：最上面一行不含字符 'U'，最下面一行不含字符 'D'，最左一列不含字符 'L'，最右一列不含字符 'R'。

你希望在此网格中放置若干机器人（每个单元格至多放置一个机器人），并满足以下条件：

• 首先，每个机器人每次必须移动（即不能跳过移动）；在每次移动中，每个机器人根据当前所在单元格的方向移动到相邻单元格；
• 其次，机器人的初始放置方式需满足：在任意一次移动发生前，不存在两个不同的机器人占据同一单元格（这也意味着你不能将两个机器人放在同一个单元格中）。例如，若网格为 "RL"（单行两列，颜色无关），则可在单元格 $(1, 1)$ 和 $(1, 2)$ 各放一个机器人；但若网格为 "RLL"（单行三列），则不能在单元格 $(1, 1)$ 和 $(1, 3)$ 同时放置机器人，因为第一秒后两个机器人均会到达单元格 $(1, 2)$。

机器人将进行无限次移动。

你的任务是：在满足上述所有条件的前提下，放置尽可能多的机器人；在所有满足最大机器人数量的方案中，再选择其中在初始时刻（即所有移动开始前）被机器人占据的黑色单元格数量最多的方案。注意：机器人只能在所有移动开始前放置。

你需要回答 $t$ 个独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($1 \lt nm \le 10^6$) — the number of rows and the number of columns correspondingly.

The next $n$ lines contain $m$ characters each, where the $j$-th character of the $i$-th line is $c_{i, j}$ ($c_{i, j}$ is either '0' if the cell $(i, j)$ is black or '1' if the cell $(i, j)$ is white).

The next $n$ lines also contain $m$ characters each, where the $j$-th character of the $i$-th line is $s_{i, j}$ ($s_{i, j}$ is 'U', 'R', 'D' or 'L' and describes the direction of the cell $(i, j)$).

It is guaranteed that the sum of the sizes of fields does not exceed $10^6$ ($\sum nm \le 10^6$).

输入的第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^4$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \lt nm \le 10^6$），分别表示网格的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符；其中第 $i$ 行的第 $j$ 个字符为 $c_{i, j}$（若 $c_{i, j}$ 为 '0'，则单元格 $(i, j)$ 为黑色；若为 '1'，则为白色）。

再接下来的 $n$ 行，每行也包含 $m$ 个字符；其中第 $i$ 行的第 $j$ 个字符为 $s_{i, j}$（$s_{i, j}$ 为 'U'、'R'、'D' 或 'L' 中的一个，表示单元格 $(i, j)$ 所指的方向）。

保证所有网格的总大小不超过 $10^6$（即 $\sum nm \le 10^6$）。

For each test case, print two integers — the maximum number of robots you can place to satisfy all the conditions described in the problem statement and the maximum number of black cells occupied by robots before all movements if the number of robots placed is maximized. Note that you can place robots only before all movements.

对于每个测试用例，输出两个整数：满足题目所述所有条件的前提下，最多可以放置的机器人数量；以及在放置机器人数量达到最大值的前提下，所有移动开始前机器人所占据的黑色格子的最大数量。注意，你只能在所有移动开始前放置机器人。