Bulb Puzzle

A puzzle asks you to connect two bulbs on a board.

The board has N rows and M columns of cells. Each cell holds a bulb, a wire, or nothing. There are exactly two bulbs, and each bulb connects to one adjacent cell. There are two kinds of wire. A q-type wire joins two cells that share only a vertex, and an l-type wire joins two cells that lie opposite each other. So one end of a q-type wire points horizontally and the other points vertically, while the two ends of an l-type wire lie on the same line.

To light the two bulbs you have to connect them with wires, that is, there must be a path of wires joining the two bulbs. You may rotate each cell by 90 degrees as many times as you want. One more condition applies. Every wire on the board has to be used, so the path joining the two bulbs must consist of all the wires on the board.

The figure below shows a placement that satisfies the conditions.

Given the board, find a placement that satisfies the conditions.

The first line contains the number of test cases T (1 ≤ T ≤ 10).

The first line of each test case contains the number of rows N and the number of columns M of the board, separated by a space (1 ≤ N, M ≤ 500).

Each of the next N lines contains a string of length M describing the board. The j-th character of the i-th string describes the cell in the i-th row from the top and the j-th column from the left (1 ≤ i ≤ N, 1 ≤ j ≤ M). There are four characters. O (ASCII 79) is a bulb, q (ASCII 113) is a q-type wire, l (ASCII 108) is an l-type wire, and * (ASCII 42) is an empty cell.

Every board holds exactly two bulbs.

For each test case, print the following.

If a placement satisfying the conditions exists, print YES on the first line, then print the placement on the next N lines. Each line holds exactly M characters, and the j-th character of the i-th line is decided as follows (1 ≤ i ≤ N, 1 ≤ j ≤ M).

• If the cell was a bulb, write one of ^ (up, ASCII 94), v (down, ASCII 118), < (left, ASCII 60), > (right, ASCII 62), according to the direction the bulb connects to.
• If the cell was a q-type wire, write one of q (left and down, ASCII 113), d (up and left, ASCII 100), b (right and up, ASCII 98), p (down and right, ASCII 112), according to the directions of its two ends.
• If the cell was an l-type wire, write one of l (up and down, ASCII 108), - (left and right, ASCII 45), according to the directions of its two ends.
• If the cell was empty, write * (ASCII 42).

If several placements satisfy the conditions, print the one whose N printed lines, concatenated from top to bottom, form the smallest string in ASCII order.

If no placement satisfies the conditions, print NO on a single line.