Yan is starting a game company! His first creation is a maze puzzle game, where the player needs to reach the target cell in the smallest possible number of steps. The maze is represented by an $$$N \times M$$$ grid and has several types of cells:

• Free cells (.): cells one can freely walk through.
• Walls (#): blocked cells that cannot be walked through.
• Starting position (*): where the player begins.
• Final position (F): the goal to be reached.
• Diagonal walls (\ or /): cells with a wall connecting two opposite corners. It is always possible to enter a cell of this type, but one cannot cross the diagonal wall, which restricts which neighboring cells can be walked to next.

  More specifically, upon entering a cell with a diagonal wall, the possible moves depend on the wall's orientation:

  • In a \ cell, it is possible to move between up and right (U $$$\leftrightarrow$$$ R) or between down and left (D $$$\leftrightarrow$$$ L).
  • In a / cell, it is possible to move between up and left (U $$$\leftrightarrow$$$ L) or between down and right (D $$$\leftrightarrow$$$ R).
• Switches (X): for each diagonal wall, there is exactly one corresponding switch that, when triggered, flips the orientation of that wall (\ becomes / and vice versa). A switch can only be triggered if you are standing on its cell.

The $$$k$$$-th switch X (in reading order, row by row from left to right) is associated with the $$$k$$$-th diagonal wall (also in reading order).

It is allowed to move in the four cardinal directions (U, D, L, R) or trigger the switch on the current cell (X). Each of these actions counts as one move.

Yan wants the final stage to be extremely challenging! Help him by creating a solvable maze of dimensions $$$N \times M$$$ ($$$1 \leq N, M \leq 100$$$) containing at most $$$10$$$ diagonal walls, such that the minimum number of moves needed to solve it is at least $$$10^{5}$$$ steps.