EWF Tribe Road Reconstruction

Long ago, the legendary EWF tribe lived on an \(N\times M\) rectangular land. Their territory, filled with mountains, swamps, plains, and houses, also contained a mysterious road network. Over generations, they built a single closed loop (circuit) on their map. Recently, archaeologists discovered an ancient map represented by an \(N\times M\) matrix. Each cell represents one of the following terrains: mountain, swamp, plain, house, or road. For a road cell, although the original road pattern is lost, experts can tell whether the cell originally contained a straight road or a curved road.

A straight road cell can only be one of two possibilities:

• Horizontal road connecting left and right neighbors (denoted as \(\{L, R\}\)).
• Vertical road connecting top and bottom neighbors (denoted as \(\{U, D\}\)).

A curved road cell can only be one of the following four types (the set of connections is unordered):

• \(\{U, R\}\) → output symbol: └
• \(\{R, D\}\) → output symbol: ┌
• \(\{D, L\}\) → output symbol: ┐
• \(\{L, U\}\) → output symbol: ┘

You are given a map. The first line contains two integers \(N\) and \(M\). Then follow \(N\) lines, each containing \(M\) tokens separated by spaces. Each token is one of:

• M (mountain)
• W (swamp)
• P (plain)
• H (house)
• S (road cell whose type is straight)
• C (road cell whose type is curved)

Your task is to restore the road orientations. For each road cell, determine its two adjacent road neighbors (using 4-directional connectivity) in the unique closed loop. Then, assign an orientation (and corresponding output symbol) following these rules:

• If the two connected directions are \(L\) and \(R\), output -.
• If they are \(U\) and \(D\), output |.
• If they are \(U\) and \(R\), output └.
• If they are \(R\) and \(D\), output ┌.
• If they are \(D\) and \(L\), output ┐.
• If they are \(L\) and \(U\), output ┘.

Non-road cells should be output unchanged.

Note: It is guaranteed that the road cells in the input form a single closed loop, and the input is consistent with the road type (i.e. a cell marked S must have a straight orientation and one marked C must have a curved orientation in the unique solution).

inputFormat

The first line contains two integers \(N\) and \(M\) (the dimensions of the map). Then follow \(N\) lines, each line contains \(M\) tokens separated by spaces. Each token is one of: M, W, P, H, S, or C. The tokens S and C represent road cells with unknown orientation (S for straight, C for curved).

For example, a sample input might be:

3 3
C S C
S P S
C S C

outputFormat

Output the reconstructed map in \(N\) lines. For non-road cells, output the original token. For road cells, output their determined orientation symbol according to the following mapping:

• Straight horizontal: -
• Straight vertical: |
• Curved (\(\{U,R\}\)): └
• Curved (\(\{R,D\}\)): ┌
• Curved (\(\{D,L\}\)): ┐
• Curved (\(\{L,U\}\)): ┘

Tokens in the same row should be separated by a single space.

sample

3 3
C S C
S P S
C S C

┌ - ┐
| P |
└ - ┘

</p>