Long ago, there was a legendary "EWF" tribe that lived for generations on an $N \times M$ rectangular land. Although the region contained mountains, swamps, plains, and houses, the tribe, through their diligence and courage, gradually constructed a circuit on their territory.

Later, the "EWF" tribe mysteriously disappeared. However, archaeologists found a map in the area where they once lived. The map is an $N \times M$ matrix, with the top-left corner at $(0, 0)$ and the bottom-right corner at $(N, M)$. Each cell in the matrix represents either a mountain, a swamp, a plain, a house, or a road. If a cell represents a road, the road passing through it is either straight or a turn. As shown in the figure below, the 2 images on the left represent straight road cells, and the 4 images on the right represent road cells that require a turn. A road cell can only represent one of these cases.

However, due to the age of the map, although archaeologists can distinguish the terrain of a cell, they can only determine whether a road cell represents a straight path or a turn. Now, they are asking for your help to restore the map of the "EWF" tribe.

Input

The first line of the input contains two space-separated positive integers $N$ and $M$, representing the height and width of the map, respectively.

The next $N$ lines, each containing $M$ characters, describe the map. There are no extra characters in the matrix.

The uppercase letter "S" represents a straight road, the uppercase letter "T" represents a turning road, and the dot "." represents mountains, swamps, plains, or houses.

Output

The output should contain $2N-1$ lines, each with $2M-1$ characters, describing the circuit.

All characters at row $2i+1$ and column $2j+1$ are lowercase "o", representing the center $(i, j)$ of the cell at the $i$-th row and $j$-th column of the matrix.

If the circuit includes a path from $(i, j)$ to $(i, j+1)$ or from $(i, j+1)$ to $(i, j)$, the character at row $2i+1$ and column $2j+2$ is a hyphen "-" (ASCII 45).

If the circuit includes a path from $(i, j)$ to $(i+1, j)$ or from $(i+1, j)$ to $(i, j)$, the character at row $2i+2$ and column $2j+1$ is a vertical bar "|" (ASCII 124).

Characters at all other positions not specified above are spaces (ASCII 32).

The input data guarantees that at least one valid solution exists, so your output should contain exactly one circuit. If there are multiple solutions, output any one of them.

Examples

Input 1

3 4
TST.
S.TT
TSST

Output 1

o-o-o o
| | 
o o o-o
| |
o-o-o-o

Constraints

For 20% of the data, $N \le 10$;

For 40% of the data, $1 \le N, M \le 80$;

For 40% of the data, the input contains no ".", and $N, M > 10$;

For 100% of the data, $1 \le N, M \le 800$.