전구 퍼즐

격자 판 위에서 전구 두 개를 잇는 퍼즐이 있다.

판은 N행 M열의 칸으로 이루어진다. 각 칸에는 전구가 있거나, 전선이 있거나, 아무것도 없다. 전구는 정확히 두 개이고, 전구마다 인접한 칸 하나와 연결된다. 전선은 두 가지다. q형 전선은 한 꼭짓점만 공유하는 두 칸을 잇고, l형 전선은 서로 마주 보는 두 칸을 잇는다. 그래서 q형 전선은 한쪽 끝이 가로 방향, 다른 쪽 끝이 세로 방향을 향하고, l형 전선은 두 끝이 같은 직선 위에 있다.

전구 두 개를 켜려면 전선으로 두 전구를 이어야 한다. 즉 두 전구를 잇는 전선 경로가 있어야 한다. 각 칸은 원하는 횟수만큼 90도씩 회전할 수 있다. 여기에 조건이 하나 더 붙는다. 판에 있는 전선을 모두 써야 한다. 즉 두 전구를 잇는 경로는 판의 전선 전부로 이루어져야 한다.

아래 그림은 조건을 만족하는 배치의 예다.

판이 주어지면 조건을 만족하는 배치를 찾아라.

첫 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다.

각 테스트 케이스의 첫 줄에는 판의 행 개수 N과 열 개수 M이 공백으로 구분되어 주어진다 (1 ≤ N, M ≤ 500).

다음 N개의 줄에는 판을 나타내는 길이 M짜리 문자열이 주어진다. i번째 문자열의 j번째 문자는 위에서 i번째, 왼쪽에서 j번째 칸을 나타낸다 (1 ≤ i ≤ N, 1 ≤ j ≤ M). 문자는 네 가지다. O(ASCII 79)는 전구, q(ASCII 113)는 q형 전선, l(ASCII 108)은 l형 전선, *(ASCII 42)는 빈 칸이다.

판마다 전구는 정확히 두 개 있다.

각 테스트 케이스마다 다음과 같이 출력한다.

조건을 만족하는 배치가 있으면 첫 줄에 YES를 출력하고, 다음 N개의 줄에 그 배치를 출력한다. 각 줄은 정확히 M개의 문자로 이루어지고, i번째 줄의 j번째 문자는 다음과 같이 정한다 (1 ≤ i ≤ N, 1 ≤ j ≤ M).

• 원래 칸이 전구면, 전구가 연결된 방향에 따라 ^(위, ASCII 94), v(아래, ASCII 118), <(왼쪽, ASCII 60), >(오른쪽, ASCII 62) 중 하나를 쓴다.
• 원래 칸이 q형 전선이면, 두 끝이 향하는 방향에 따라 q(왼쪽과 아래, ASCII 113), d(위와 왼쪽, ASCII 100), b(오른쪽과 위, ASCII 98), p(아래와 오른쪽, ASCII 112) 중 하나를 쓴다.
• 원래 칸이 l형 전선이면, 두 끝이 향하는 방향에 따라 l(위와 아래, ASCII 108), -(왼쪽과 오른쪽, ASCII 45) 중 하나를 쓴다.
• 원래 칸이 빈 칸이면 *(ASCII 42)를 쓴다.

조건을 만족하는 배치가 여럿이면, 출력할 N개의 줄을 위에서부터 이어 붙인 문자열이 ASCII 순으로 가장 작은 배치를 출력한다.

조건을 만족하는 배치가 없으면 NO만 한 줄에 출력한다.