Codeforces Round 634 (Div. 3) |
---|
Finished |
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'.
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.
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.
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$$$).
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.
3 1 2 01 RL 3 3 001 101 110 RLL DLD ULL 3 3 000 000 000 RRD RLD ULL
2 1 4 3 2 2
Name |
---|