시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 107 | 25 | 20 | 21.978% |
Jeehak Yoon is a member of United Committee of Puzzle Creation. Recently, he has made a puzzle to light all the bulbs on the board. The puzzle looks like the following:
The board consists of N rows and M columns of cells. Each cell contains either a bulb, a wire or nothing. There are exactly two bulbs, and each bulb can be connected with an adjacent cell. There are two types of wires in this puzzle: q-type and l-type. A q-type wire connects two cells that share a vertex, and a l-type wire connects two cells that are opposite to each other.
In order to light all the bulbs, they should be connected by wires. (i.e. there must be a path of wires connecting the two bulbs) It can be done by rotating each cell by 90-degree as many times as you want. Jeehak thought this was too easy, so he added one more constraint: all the wires must be used to connect the bulbs. (i.e. the path of wires connecting two bulbs must consist of all the wires in the board)
The figure below shows an example of a valid solution.
Jeehak provided this idea to UCPC and got the test version of this puzzle. He tried to solve the puzzle, but he couldn’t solve it because the size of puzzle was quite large for him. Why don’t you help Jeehak to solve the puzzle?
The first line of input contains an integer T (1 ≤ T ≤ 10), the number of test cases.
Each test case starts with a line containing two space-separated integers N and M (1 ≤ N, M ≤ 500), where N is the number of rows of the board and M is the number of columns of the board.
Each of the next N lines contains a string of length M, describing the board. The j-th character of the i-th string (1 ≤ i ≤ N, 1 ≤ j ≤ M) describes the cell in the i-th row from the top and the j-th column from the left. There are four kinds of characters ‘O’ (ASCII code 79), ‘q’ (ASCII code 113), ‘l’ (ASCII code 108), and ‘*’ (ASCII code 42) which describes a cell: ‘O’ means a bulb, ‘q’ means a q-type wire, ‘l’ means a l-type wire and ‘*’ means nothing.
For each test case,
If there exists several solutions, it is allowed to print any of them.
4 3 4 qlq* OOqq *qlq 2 4 Oqqq Oqqq 5 8 *qq*qq** qqOqqqq* qq*qqqq* *qqqqqqO **qq**qq 6 7 qlqqllq qqqqqlq *qOqqqq qqqq*Ol lqqqlql qllq*qq
YES p-q* ^vbq *b-d NO YES *pq*pq** pd^pdbq* bq*bqpd* *bqpdbqv **bd**bd YES p-qp--q bqbdp-d *b<pdpq pqpd*^l lbdp-ql b--d*bd