If you competed in the CodeRams Contest #8, you might remember a problem involving mirrors and light. This is a more difficult and updated version of that problem.
You are in a hall of mirrors, and you shine a laser beam in a certain direction. Given the position of several diagonal mirrors, figure out the path of the laser beam.
You shine your laser beam from the back of the hall of mirrors (on a computer screen, this will look like the "bottom" of the image).
*This problem also adds "star blocks", which shine light in all directions when light passes through them*.
The first line of input contains two space-separated integers $n$, $m$, and $x$. $n$ and $m$ represent the number of rows and columns, respectively, and the number $x$ represents the index on the bottom row that you start shining the laser pointer at (with 0-based indices). The next $n$ lines contain $m$ characters representing the hall of mirrors. If a position does not contain a mirror, it will be pictured as a single dot. If it does have a mirror, it will be represented with either a forward slash ("/") or a backslash, which represents the direction that it reflects light in. See the example cases if you are confused on this. Additionally, if the position contains a star block, it will be pictured as an asterisk ("*"). Star blocks redirect light in all four immediate directions (up, down, left, and right).
Output the given input matrix, however, replace any positions without a mirror or star block that the laser pointer shines through horizontally with a hyphen, and replace any positions without a mirror or star block that the laser pointer shines through vertically with a pipe ("|"), above the ENTER key on a keyboard. If the laser pointer travels through a space in both directions, replace the dot in that position with a plus symbol ("+").
## Input
The first line of input contains two space-separated integers $n$, $m$, and $x$. $n$ and $m$ represent the number of rows and columns, respectively, and the number $x$ represents the index on the bottom row that you start shining the laser pointer at (with 0-based indices). The next $n$ lines contain $m$ characters representing the hall of mirrors. If a position does not contain a mirror, it will be pictured as a single dot. If it does have a mirror, it will be represented with either a forward slash ("/") or a backslash, which represents the direction that it reflects light in. See the example cases if you are confused on this. Additionally, if the position contains a star block, it will be pictured as an asterisk ("*"). Star blocks redirect light in all four immediate directions (up, down, left, and right).
## Output
Output the given input matrix, however, replace any positions without a mirror or star block that the laser pointer shines through horizontally with a hyphen, and replace any positions without a mirror or star block that the laser pointer shines through vertically with a pipe ("|"), above the ENTER key on a keyboard. If the laser pointer travels through a space in both directions, replace the dot in that position with a plus symbol ("+").
[samples]
**Definitions**
Let $ n, m, x \in \mathbb{Z} $ with $ n \geq 1 $, $ m \geq 1 $, $ 0 \leq x < m $.
Let $ G \in \{ \text{`.`}, \text{`/`}, \text{`\`}, \text{`*`} \}^{n \times m} $ be the grid representing the hall of mirrors, where:
- `.` denotes empty space,
- `/` denotes a diagonal mirror reflecting light 90° clockwise or counterclockwise (depending on incident direction),
- `\` denotes a diagonal mirror reflecting light 90° in the opposite direction,
- `*` denotes a star block that emits light in all four cardinal directions (up, down, left, right) upon being struck.
Let $ \mathcal{L} \subseteq \{ (i, j, d) \mid 0 \leq i < n, 0 \leq j < m, d \in \{ \text{up}, \text{down}, \text{left}, \text{right} \} \} $ be the set of all light rays, each represented by position and direction.
Initial ray: $ (n-1, x, \text{up}) $.
**Constraints**
1. The laser beam propagates according to mirror reflection rules:
- `/` reflects:
- right → up,
- left → down,
- up → right,
- down → left.
- `\` reflects:
- right → down,
- left → up,
- up → left,
- down → right.
2. `*` emits four new rays in directions up, down, left, right upon being hit (regardless of incoming direction).
3. Light propagates until it exits the grid or enters a cycle.
4. Each grid cell may be traversed by multiple rays.
**Objective**
Construct output grid $ O \in \{ \text{`.`}, \text{`/`}, \text{`\`}, \text{`*`}, \text{`-`}, \text{`|`}, \text{`+`} \}^{n \times m} $, where:
- $ O[i][j] = G[i][j] $ if $ G[i][j] \in \{ \text{`/`}, \text{`\`}, \text{`*`} \} $,
- Otherwise, for each empty cell $ (i,j) $:
- If traversed **only horizontally** (left/right): $ O[i][j] = \text{`-`} $,
- If traversed **only vertically** (up/down): $ O[i][j] = \text{`|`} $,
- If traversed **both horizontally and vertically**: $ O[i][j] = \text{`+`} $,
- Otherwise: $ O[i][j] = \text{`.`} $.
Output $ O $.