Problem H
Frenemies

Grogar was a legendary tyrant who once wreaked havoc across Equestria. Ages ago, his mythical bell and source of power was stolen and hidden at the top of the treacherous Mt. Everhoof, and he was forced to go into hiding.

At long last, he has decided that the time is ripe for revenge. Even in his weakened form, he coerced three hardened criminals to team up and retrieve his bell; with it, all of Equestria will kneel before him once again.

Figure 1: Illustration by Kyle Coate.

Cozy Glow, Lord Tirek and Queen Chrysalis, three villains with nothing in common other than their lust for power, now face their toughest challenge yet: working together.

Through their individual efforts, they have each managed to reach the highest level of the mountain. Recovering the bell, however, will require them to combine their powers.

The highest level of Mt. Everhoof can be represented as a grid with $R$ rows and $C$ columns. Each of the cells in this grid is either:

• solid ground, which can freely be entered;

• a huge rock, which is an impassable obstacle that cannot be entered;

• a hole, which when entered will result in certain death;

• a hostile guard, which when entered by Lord Tirek or Queen Chrysalis will result in certain death, but when entered by Cozy Glow is subdued and permanently becomes solid ground;

• a lethal magic barrier, which when entered by Cozy Glow or Queen Chrysalis will result in certain death, but when entered by Lord Tirek is subdued and permanently becomes solid ground;

• an Ophiotaurus, which when entered by Cozy Glow or Lord Tirek will result in certain death, but when entered by Queen Chrysalis is subdued and permanently becomes solid ground;

• slippery ice, which when entered from a certain direction will result in sliding to the next cell in that direction, unless the next cell is a huge rock, in which case one stops on this cell. Note that it is possible to slide into a lethal obstacle or fall off the mountain (if the next cell is out of the grid), and both cases will result in certain death;

• the cell containing Grogar’s bell. In order to successfully retrieve the bell, all three of the villains need to be on this cell simultaneously. For all other purposes, it can be treated as solid ground.

In one move, you can direct a character to move in one of the four cardinal directions. The three characters initially begin in different cells, but they are allowed to occupy the same cell at the same time and will not obstruct each other’s movements.

As you can tell, they are new to this whole “cooperation” thing, so they will need a bit of help. Can you give them a list of moves that will allow them to successfully retrieve Grogar’s bell?

If the task is truly impossible, you must also say so.

Input

The first line of input contains two integers, $R$ and $C$ ($1 \leq R, C$; $4 \leq R\cdot C \leq 300\, 000$), the number of rows and the number of columns of the grid, respectively.

The next $R+2$ lines each contain $C+2$ characters. In particular, the $j^\text {th}$ character on the $i^\text {th}$ of these lines is either:

• +, if either $i = 1$ or $i = R+2$, and at the same time either $j = 1$ or $j = C+2$;

• -, if either $i = 1$ or $i = R+2$, and at the same time $j \neq 1$ and $j \neq C+2$;

• |, if either $j = 1$ or $j = C+2$, and at the same time $i \neq 1$ and $i \neq R+2$;

  Note that the above three characters are purely decorative. They serve only to clarify the boundaries of the grid. In particular, they are not walls, and they are not cells.

• if none of the above are satisfied, then this character represents the content of the cell in row $i-1$ and column $j-1$, and is either:

  • a space, which represents solid ground;

  • c, which represents Cozy Glow’s initial position and is solid ground;

  • l, which represents Lord Tirek’s initial position and is solid ground;

  • q, which represents Queen Chrysalis’s initial position and is solid ground;

  • #, which represents a huge rock;

  • O, which represents a hole;

  • C, which represents a hostile guard;

  • L, which represents a lethal magic barrier;

  • Q, which represents an Ophiotaurus;

  • ., which represents slippery ice;

  • %, which represents the cell containing Grogar’s bell.

It is guaranteed that there is exactly one each of c, l, q and % in the grid.

Output

If it is not possible to retrieve the bell, output a single line containing the string IMPOSSIBLE.

Otherwise, on the first line, output a single integer $m$ ($1 \leq m \leq 2\cdot 10^6$), the number of moves in your solution.

Then, on the next $m$ lines, output the moves in your solution. In particular, the $i^\text {th}$ of these lines should contain one of c, l or q followed by one of ^, <, v or >, separated by a space, denoting that the $i^\text {th}$ move should involve Cozy Glow, Lord Tirek or Queen Chrysalis moving up, left, down or right, respectively.

Note that you do not need to minimize $m$.

It is legal to attempt to move into a huge rock, although nothing will happen. It is also legal to perform more moves even after all three characters have reached the cell containing Grogar’s bell, as long as all three characters are at the cell containing Grogar’s bell at the end of all the moves.

If there are multiple correct answers, you can output any of them.

The input will be such that if a solution exists, then a solution exists with $m \leq 2\cdot 10^6$.

4 9
+---------+
|cO...  l |
|   # .###|
|##LC .C q|
|%Q   #   |
+---------+

32
l <
l <
l v
l <
l v
l <
l <
l ^
c v
c >
c >
c v
c >
c >
c >
q <
q <
q <
q v
q <
q <
q <
q <
l v
l <
l <
c <
c v
c <
c <
c <
c <

2 4
+----+
|lcq |
|###%|
+----+

9
l >
l >
l >
l v
c >
c >
c v
q >
q v

2 4
+----+
|lcq.|
|###%|
+----+

IMPOSSIBLE