Wincent is about to open a grand new building! It has a single floor which consists of \(n\) rows, each consisting of \(m\) square rooms of identical size. Each room is connected to each of its adjacent rooms by a door. Also, if a side of a room is on the edge of the building, then it also has a door that leads outside.
The grand opening is near, but you just discovered a rather pressing safety issue: the matter of emergency exits. In each room there is an arrow pointing to the door to take in case of an emergency (such as dragon fire). Sometimes this door leads directly outside and we are saved, other times it leads us to a different room where we need to find and follow another arrow.
To satisfy safety standards, it must be the case that if one follows emergency exit arrows, one eventually ends up outside. Unfortunately, this is currently not necessarily the case.
To ensure the safe operation of the building, you need to redirect some arrows in such a way that if one starts from any room, following emergency exit arrows will eventually lead them outside. Unfortunately, you found that some of the arrows are glued too well, and so only some of them can be redirected.
Since the opening is near, you want to change the orientation of as few arrows as possible so that the safety standards are ensured.
The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.
Each test case starts with a line consisting of the two positive integers \(n\) and \(m\) separated by a space. You may assume that \(1\leq n, m\leq 10^5\) and that \(n\cdot m\leq 3\cdot 10^5\).
The next \(n\) lines contain the
description of the current state of emergency exit arrows. The \(i\)-th of these lines describes the \(i\)-th row of rooms: it is a string of
length \(m\) consisting of characters
<>^v, denoting arrow directions left, right, up and
down, respectively.
Then follow another \(n\) lines, each consisting of \(m\) space-separated zeros and ones. These denote whether the arrow in the corresponding room can (\(1\)) or cannot (\(0\)) be reoriented.
It is guaranteed that for each input there is a solution (a valid orientation of arrows).
For each test case, output \(n+1\) lines.
The first line of a test case’s output should contain a single non-negative integer \(k\): the minimum number of changes needed.
On the next \(n\) lines, output a safety-standards-satisfying orientation of the emergency exit arrows. Your output must have exactly \(k\) differences from the input, and it must have all the required properties.
For each subproblem, you will get 50% of points if your solution outputs the correct value \(k\) of each test case. Note that in order to score these points your submission must still be syntactically valid enough so that the grader can parse it. (To be safe, always print some grid of arrows with the correct dimensions.)
Input file: A1.in
Constraints: \(t=20\) and in each test case \(1\leq n\cdot m\leq 25\).
Input file: A2.in
Constraints: \(t=20\) and in each test case \(1\leq n\cdot m\leq 1000\).
Input file: A3.in
Constraints: \(t=23\) and in each test case \(1\leq n\cdot m\leq 3\cdot 10^5\).
The sum of \(n\cdot m\) over all test cases does not exceed \(5\cdot 10^6\).
input3 4 4 ><>v ^v>v v>^< <<^^ 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 4 4 ><>v ^v>v v>^< <<^^ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 ^^^ ^^^ 0 0 0 0 0 0 | output3 >>^v ^v^< v>^< <<^^ 2 >>>v ^v>> v>^< <<^^ 0 ^^^ ^^^ |
In the first case, not all arrows can be reoriented. In that case, one solution is to reorient the arrow in the second and third room in the first row, and the arrow in the third room of the second row. Note also that the changes do not necessarily have to lead to the shortest evacuation paths.
In the second case, any arrow can be reoriented, and so in this case we can reorient the arrow in the second room in the first row, and in the fourth room in the second row (this arrow couldn’t be reoriented in the first test case).
In the third case, all arrows must remain fixed, but they already work so everything is fine.
