Robots on a Grid
Contest: Codeforces Round 634 (Div. 3)
Difficulty rating: 2200
Tags: data structures, dfs and similar, dsu, graphs, greedy, matrices

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.

Input format:
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 < 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$$$).

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
1 2
01
RL
3 3
001
101
110
RLL
DLD
ULL
3 3
000
000
000
RRD
RLD
ULL

Example output:
2 1
4 3
2 2

Editorial:
First of all, I want to say about $$$O(nm)$$$ solution. You can extract cycles in the graph, do some dynamic programming on trees, use some hard formulas and so on, but it is a way harder to implement than the other solution that only has an additional log, so I'll describe the one which is easier to understand and much easier to implement.
Firstly, consider the problem from the other side. What is this grid? It is a functional graph (such a directed graph that each its vertex has exactly one outgoing edge). This graph seems like a set of cycles and ordered trees going into these cycles. How can it help us? Let's notice that if two robots meet after some move, then they'll go together infinitely from this moment. It means that if we try to make at least $$$nm$$$ moves from each possible cell, we will obtain some "equivalence classes" (it means that if endpoints of two cells coincide after $$$nm$$$ moves then you cannot place robots in both cells at once).
So, if we could calculate such endpoints, then we can take for each possible endpoint the robot starting from the black cell (if such exists) and otherwise the robot starting from the white cell (if such exists).
How can we calculate such endpoints? Let's number all cells from $$$0$$$ to $$$nm-1$$$, where the number of the cell $$$(i, j)$$$ is $$$i \cdot m + j$$$. Let the next cell after $$$(i, j)$$$ is $$$(ni, nj)$$$ (i.e. if you make a move from $$$(i, j)$$$, you go to $$$(ni, nj)$$$). Also, let's create the two-dimensional array $$$nxt$$$, where $$$nxt[v][deg]$$$ means the number of the cell in which you will be if you start in the cell number $$$v$$$ and make $$$2^{deg}$$$ moves. What is the upper bound of $$$deg$$$? It is exactly $$$lognm = \lceil\log_{2}(nm + 1)\rceil$$$.
Well, we need to calculate this matrix somehow. It is obvious that if the number of the cell $$$(i, j)$$$ is $$$id$$$ and the number of the next cell $$$(ni, nj)$$$ is $$$nid$$$ then $$$nxt[id][0] = nid$$$. Then let's iterate over all degrees $$$deg$$$ from $$$1$$$ to $$$lognm - 1$$$ and for each vertex $$$v$$$ set $$$nxt[v][deg] = nxt[nxt[v][deg - 1]][deg - 1]$$$. The logic behind this expresion is very simple: if we want to jump $$$2^{deg}$$$ times from $$$v$$$ and we have all values for $$$2^{deg - 1}$$$ calculated then let's just jump $$$2^{deg - 1}$$$ times from $$$v$$$ and $$$2^{deg - 1}$$$ times from the obtained vertex. This technique is called binary lifting.
Now we can jump from every cell $$$nm$$$ times in $$$O(\log nm)$$$ time: just iterate over all degrees $$$deg$$$ from $$$0$$$ to $$$lognm-1$$$ and if $$$nm$$$ has the $$$deg$$$-th bit on, just jump from the current vertex $$$2^{deg}$$$ times (set $$$v := nxt[v][deg]$$$). The rest of solution is described above.
Time complexity: $$$O(nm \log_{2}nm)$$$.