Hansel and Gretel are playing a well-known game of "Arrows" that takes place on a board with
Hansel plays first, and his move is to colour exactly
The winner of the game is determined in the following way:
- If the robot stopped and the game ended, Hansel is the winner if the robot passed through exactly one coloured field, and Gretel is the winner if the robot passed through zero or more than one coloured fields.
- If the robot did not stop after a finite amount of time (in other words, if the robot is stuck in an infinite loop), Hansel is the winner.
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
Input Specification
The first line of input contains the integers
Each of the following 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).
Output Specification
If Hansel cannot ensure his victory, output -1
.
If Hansel can ensure his victory, output
If multiple solutions exist, output any.
Sample Input 1
4 3 1
DRD
DUD
DUD
RUL
Sample Output 1
4 2
Explanation for Sample Output 1
If Hansel colours the field
Sample Input 2
3 3 2
RRR
RRR
RRR
Sample Output 2
-1
Explanation for Sample Output 2
Since Hansel must colour exactly
Sample Input 3
4 4 2
RRDL
RRDL
DLRD
RRRL
Sample Output 3
2 3
4 1
Explanation for Sample Output 3
Consult the image from the task.
Comments