Strelice

Hansel and Gretel are playing a game called "Arrows" on a board with R rows and S columns. Every field of the board holds exactly one arrow, which points in one of the four directions: up, down, left, or right.

Hansel moves first: he colours exactly K fields that are not in the last column. Gretel then places a robot on any field of the first column. From then on the robot moves by itself, each time stepping to the field that the arrow of its current field points to. When the robot reaches a field in the last column, it stops and the game ends.

The winner is decided as follows.

• If the robot stops and the game ends, Hansel wins when the robot passed through exactly one coloured field, and Gretel wins when it passed through zero coloured fields or more than one.
• If the robot never stops (it is stuck in an infinite loop), Hansel wins.

The fields the robot passes through include its starting field, every field it moves onto during the game, and the field where it is when the game ends. The arrows are drawn so that the robot never leaves the board.

Determine whether Hansel can colour fields so that he wins no matter where Gretel places the robot. If he can, output the K fields he colours.

The first line contains the integers R, S, and K ($1 \le R \times S \le 1\,000\,000$, $1 \le K \le 50$).

Each of the next R lines contains S characters, each one of 'L', 'R', 'U', and 'D', giving the direction of the arrow in the corresponding field: L is left, R is right, U is up, and D is down.

If Hansel cannot ensure his victory, output -1.

Otherwise, output the K fields he colours, one per line. Each line contains two integers A and B ($1 \le A \le R$, $1 \le B \le S$) separated by a space: the row and the column of the field. All coloured fields must be different. Output the fields in increasing order of row, and fields in the same row in increasing order of column. This order is called row-major order.

Hansel can often win with several colourings, so output the one defined by the following rule.

• A start is a field of the first column from which the robot eventually stops.
• A field outside the last column is a route field if the robot passes through it when placed on some start. Every other field outside the last column is a spare field. Colouring a spare field never changes the outcome of the game.
• For a route field X, the region of X is the set of route fields from which the robot passes through X, including X itself. A positive integer c is feasible for X if exactly c fields of the region of X can be coloured so that the robot, placed on any start in the region of X, passes through exactly one of them.
• Let s be the smallest integer with $0 \le s \le K$ such that exactly s route fields can be coloured so that the robot, placed on any start, passes through exactly one coloured field, and $K - s$ does not exceed the number of spare fields. If no such s exists, Hansel cannot ensure his victory.
• Colour the first $K - s$ spare fields in row-major order.
• The top fields are the route fields whose arrow points to a field in the last column. Split s among the top fields as described below.
• To split a count t among a list of fields, go through the fields in row-major order and give each field the smallest count c that is feasible for it and leaves a remainder that can be split among the later fields of the list so that each of them gets a feasible count.
• A field X that receives the count c is handled as follows. If c = 1, colour X. If c ≥ 2, leave X uncoloured, split c in the same way among the route fields whose arrow points to X, and handle each of those fields in the same way.

In the first sample, if Hansel colours the field (1, 2), the robot passes through it no matter where Gretel places it, so Hansel wins. Colouring the field (4, 2) also wins, but the output rule gives the answer (1, 2).