L. Tornado Destroys the Parking Lot
time limit per test
2 seconds
memory limit per test
1024 MB
input
standard input
output
standard output

You are assigned to manage a severely congested grid parking lot. The parking lot can be viewed as an $$$N \times M$$$ matrix. Each cell in the matrix is either empty (denoted by .), or occupied by a car with a fixed driving direction, which can be one of the four types: U (up), D (down), L (left), or R (right).

You may send a "leave" signal to these cars in any order. After receiving the signal, a car will successfully leave the parking lot if and only if, starting from its current position and moving straight toward the boundary in the direction it is facing, there is no other car blocking its path. Once a car leaves, its current cell becomes empty (.).

Determine whether there exists an order of sending signals such that all cars in the parking lot can be evacuated. If it is possible, output the sequence of coordinates of the cars to which signals are sent in order; otherwise, if the cars block each other in a deadlock and cannot all be evacuated, output $$$-1$$$.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 2000$$$), representing the number of rows and columns of the parking lot, respectively.

The next $$$N$$$ lines each contain a string of length $$$M$$$, consisting only of the characters U, D, L, R, and ..

Output

If it is possible to evacuate all cars, output $$$K$$$ lines, where $$$K$$$ is the total number of cars initially in the parking lot. Each line should contain two integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le N$$$, $$$1 \le c \le M$$$), indicating the row and column of the car to which the signal is sent, in order (coordinates are 1-indexed). If there are multiple valid evacuation orders, output any one of them.

If it is impossible to evacuate all cars regardless of the order, output a single line containing $$$-1$$$.

Examples
Input
3 3
D..
R..
.UL
Output
2 1
3 2
1 1
3 3
Input
2 2
RD
UL
Output
-1
Note

In the first sample, we can evacuate the cars in the following order:

1. Send a signal to the car at $$$(2, 1)$$$ facing right (R). Since there is no other car blocking its straight path to the right boundary, it successfully leaves.

2. Send a signal to the car at $$$(3, 2)$$$ facing up (U). Its path upward is clear, so it successfully leaves.

3. Send a signal to the car at $$$(1, 1)$$$ facing down (D). The car at $$$(2, 1)$$$ that originally blocked it has already left, so it can now leave successfully.

4. Send a signal to the car at $$$(3, 3)$$$ facing left (L). The car at $$$(3, 2)$$$ that originally blocked it has already left, so it also leaves successfully.

At this point, all cars have been successfully evacuated. Note that there may be more than one valid output order.

In the second sample, the car at $$$(1, 1)$$$ is blocked by the car at $$$(1, 2)$$$; the car at $$$(1, 2)$$$ is blocked by the car at $$$(2, 2)$$$; the car at $$$(2, 2)$$$ is blocked by the car at $$$(2, 1)$$$; and the car at $$$(2, 1)$$$ is in turn blocked by the car at $$$(1, 1)$$$. Initially, no car can move, so a deadlock occurs and complete evacuation is impossible. Therefore, the answer is $$$-1$$$.