A. Fixing Tube
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Wor is a plumbing repairman.

Wor often helps neighbors in the community to repair broken plumbing. With a high talent for fixing, Wor is confident in his capability. However, now he is facing trouble, as a serious accident happened in the central water supply station that interrupted the whole city's water supply. Because of the complexity of the pipe network, he failed and felt sad. Now, he is seeking your help. Can you help him?

There are four types of plumbing in the central water supply station. Now we define the operation $$$'$$$, which means a $$$90$$$ degree clockwise rotation of the water pipe.

  • type $$$1$$$ plumbing: $$$I$$$-type water pipe and $$$-$$$-type water pipe.

    When we do the operation $$$I'$$$, we can get the $$$-$$$-type pipe. Meanwhile, operation $$$-'$$$ can get the $$$I$$$-type pipe.

    • $$$I$$$-type water pipe represents the vertical water pipe, which means water flow can pass from bottom to top or from top to bottom.

    • $$$-$$$-type water pipe represents the horizontal water pipe, which means water flow can pass from left to right or from right to left.

  • type $$$2$$$ plumbing: $$$+$$$-type water pipe.

    No matter how we use the operation $$$+'$$$, we can only get the $$$+$$$-type pipe.

    • $$$+$$$-type water pipe represents the crossing water pipe, which means water flow can only pass from left to right, right to left, bottom to top, or from top to bottom.

  • type $$$3$$$ plumbing:$$$p$$$-type water pipe, $$$b$$$-type water pipe, $$$d$$$-type water pipe, and $$$q$$$-type water pipe.

    Operation $$$p'$$$ would get the $$$q$$$-type water pipe, $$$q'$$$ would get the $$$d$$$-type water pipe, $$$d'$$$ would get the $$$b$$$-type water pipe, and $$$b'$$$ would get the $$$p$$$-type pipe.

    • $$$p$$$-type water pipe represents the left-top corner pipe, which means water flow can pass from bottom to right or from right to bottom.

    • $$$b$$$-type water pipe represents the left-bottom corner pipe, which means water flow can pass from top to right or from right to top.

    • $$$d$$$-type water pipe represents the right-bottom corner pipe, which means water flow can pass from top to left or from left to top.

    • $$$q$$$-type water pipe represents the right-top corner pipe, which means water flow can pass from bottom to left or from left to bottom.

  • type $$$4$$$ plumbing: $$$x$$$-type water pipe and $$$y$$$-type water pipe.

    Doing operation $$$x'$$$, we can get the $$$y$$$-type water pipe, and we can get the $$$x$$$-type pipe when we do the operation $$$y'$$$.

    • $$$x$$$-type water pipe represents the combination of $$$d$$$-type water pipe and $$$p$$$-type water pipe, looks like $$$dp$$$-type water type, which means water flow can pass from bottom to right, right to bottom, top to left, or from left to top.

    • $$$y$$$-type water pipe represents the combination of $$$q$$$-type water pipe and $$$b$$$-type water pipe, looks like $$$qb$$$-type water type, which means water flow can pass from bottom to left, left to bottom, top to right, or from right to top.

  • type $$$5$$$ plumbing: starting tube and ending tube, which is the entrance of the water flow and the exit of the water flow. There is only one starting tube and one ending tube.

    Starting tube and ending tube have only one direction, $$$u,o,l,r$$$, respectively representing the water flow out and in direction as up, down, left, or right. Attention please, starting tube and ending tube cannot rotate.

    The order of following pictures stick to $$$u,r,o,l$$$.

    • starting tube:

    • ending tube:

    In fact, distinguishing between starting tube and ending tube is meaningless, so there is no distinction between starting tube and ending tube in the data.

Now, Wor would give you the initial status of the plumbing matrix, which is an $$$n \times m$$$ matrix $$$a_{i,j}$$$. Your mission is to find a final fixed matrix $$$b_{i,j}$$$ that is available by only using the operation $$$'$$$ in the initial plumbing matrix, and the water flow can pass through from the starting tube to the ending tube.

Input

The first line contains two integers $$$n,m(2 \le n,m \le 50)$$$ representing the size of the matrix as $$$n \times m$$$.

Then following $$$n$$$ lines and $$$m$$$ columns character matrix represent the initial status of the plumbing matrix $$$a_{i,j}(a_{i,j} \in \{i,+,p,x,u,o,l,r\})$$$.

The character $$$u,o,l,r$$$ represents the starting pipe or ending pipe direction. There must be two characters that are $$$u,o,l,r$$$, no matter which is the starting pipe or ending pipe.

We ensure that the total number of $$$p$$$-type pipes and $$$x$$$-type pipes is less than or equal to $$$20$$$.

Output

An $$$n$$$ lines and $$$m$$$ columns character matrix represents the fixed status of the plumbing matrix $$$b_{i,j}(a_{i,j} \in \{i,-,+,p,b,d,q,x,y,u,o,l,r\})$$$ that can be obtained by only using the operation $$$'$$$ in the initial matrix, and the water flow can pass through from the starting tube to the ending tube.

Examples
Input
5 7
pppiipi
iiupixl
ipi+pii
pipppii
iipiipi
Output
pqp--qi
iiup-xl
ib-+qii
b-qbdii
iib--di
Input
2 5
riiil
iiiii
Output
r---l
iiiii
Input
3 3
oii
pip
iiu
Output
oii
b-q
iiu
Input
5 2
ox
+x
+x
+x
ux
Output
ox
+x
+x
+x
ux
Note

There may be many legal solutions, you only need to output one of them.

The data ensures that there is a legitimate solution, so you don't need to consider situations where there is no solution.

Example 1 explanation: