题目描述

Your company offers a rental office service on a floor of a building. The floor, which forms a rectangle, is partitioned into square sections of the same size in a grid form. Two sections are said to be adjacent if they share an edge. Some sections may contain pillars. Some sections may be empty for future use. Any other sections are used as offices, where each office consists of two adjacent sections without pillars.

One day, a potential customer came to your company and applied for an office. Because all the existing offices are already rented, you need to set up a new one. Of course, if there are two adjacent empty sections, you can set up an office there. But if not, it may be possible to relocate some of the existing offices to place one more office. That being said, because your company must pay compensation to the affected renters, the rearrangement should minimize the number of affected offices.

More formally, your task is to find a rearrangement plan that satisfies the following conditions.

• The floor contains $k + 1$ offices after the rearrangement, where $k$ is the number of offices before the rearrangement.
• The set of sections with pillars does not change.
• Each office still consists of two adjacent sections without pillars.
• No two offices overlap.
• Among all the possible rearrangement plans satisfying all the above conditions, the number of unaffected offices is maximized. Here, an office, which consists of some two sections before the rearrangement, is unaffected by the rearrangement if these two sections still belong to the same office after the rearrangement.

Please find such a plan if it exists. If there can be multiple plans, output any of them.

输入格式

The input consists of multiple test cases. The first line of input contains an integer $t$ ($1 \leq t \leq 500\,000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is given in the following format.

$$\begin{aligned} & h \ w \\ & s_{1,1} s_{1,2} \cdots s_{1,w} \\ & s_{2,1} s_{2,2} \cdots s_{2,w} \\ & \vdots \\ & s_{h,1} s_{h,2} \cdots s_{h,w} \end{aligned} $$

The first line contains two integers $h$ and $w$ ($h \geq 1$, $w \geq 1$, $h \times w \leq 500\,000$) representing that the floor consists of $h$ rows and $w$ columns of sections.

Each of the following $h$ lines contains $w$ characters. Let us denote by $(r, c)$ the section in the $c$-th column of the $r$-th row. Each character $s_{r,c}$, which represents the information of the section $(r, c)$, is one of ‘#’, ‘.’, ‘^’, ‘v’, ‘<’, and ‘>’. If $s_{r,c}$ is ‘#’, then $(r, c)$ is a section with a pillar. If $s_{r,c}$ is ‘.’, then $(r, c)$ is an empty section. If there is an office consisting of $(r, c)$ and $(r + 1, c)$, then $s_{r,c}$ is ‘^’ and $s_{r+1,c}$ is ‘v’. If there is an office consisting of $(r, c)$ and $(r, c + 1)$, then $s_{r,c}$ is ‘<’ and $s_{r,c+1}$ is ‘>’.

If $s_{r,c}$ is ‘^’, it is guaranteed that $r \leq h - 1$ and $s_{r+1,c}$ is ‘v’. Similarly, if $s_{r,c}$ is ‘v’, then $r \geq 2$ and $s_{r-1,c}$ is ‘^’. If $s_{r,c}$ is ‘<’, then $c \leq w - 1$ and $s_{r,c+1}$ is ‘>’. Finally, if $s_{r,c}$ is ‘>’, then $c \geq 2$ and $s_{r,c-1}$ is ‘<’.

The sum of $h \times w$ over all the test cases does not exceed $500\,000$.

输出格式

For each test case, if there is no valid rearrangement plan, output "No" in one line. Otherwise, output "Yes" in one line, followed by $h$ lines in the same format as the input (without the line of $h$ and $w$). These $h$ lines should describe the information of the floor after the rearrangement. If there are multiple valid rearrangement plans, any of them is accepted.

3
3 4
.##.
^<>#
v.#.
3 3
#.#
.<>
#.#
2 2
..
..

Yes
^##.
v<>#
<>#.
No
Yes
^.
v.