|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||2||2||1||100.000%|
Hansel and Gretel are playing a well-known game of “Arrows” that takes place on a board with R rows and S columns. On each field there is exactly one arrow that points to one of the four main directions.
Hansel plays first, and his move is to colour exactly K fields on the board that are not located in the final column. Gretel then places a robot on an arbitrary field in the first column. Now the robot can move on his own, by moving from the current field to the field that the arrow points to. If at some point the robot is located in the last column, he stops and the game ends.
The winner of the game is determined in the following way:
We consider that the robot passed through the starting field, through the fields it moved on throughout the game, and the field it was when the game ended. Also, the arrows will be drawn so that the robot never exists outside the board’s boundaries.
Determine whether Hansel can ensure his victory no matter where Gretel initially places the robot. If the answer is positive, output K fields he can colour in order to win.
The first line of input contains the integers R, S, K (1 ≤ R * S ≤ 1 000 000, 1 ≤ K ≤ 50).
Each of the following R lines contains S characters ‘L’, ‘R’, ‘U’ or ‘D’ that denote the direction of the arrow in the corresponding field of the board (L - left, R - right, U - up, D - down).
If Hansel cannot ensure his victory, output -1.
If Hansel can ensure his victory, output K lines. In each line, output space-separated numbers A and B (1 ≤ A ≤ R, 1 ≤ B ≤ S) that denote the row and column of the field that Hansel has to colour. All coloured fields must be different.
If multiple solutions exist, output any.
4 3 1 DRD DUD DUD RUL
3 3 2 RRR RRR RRR
4 4 2 RRDL RRDL DLRD RRRL
2 3 4 1
If Hansel colours the field (4, 2), the robot will pass through it no matter where Gretel initially places it, so Hansel will be the winner.