Problem
After looking at Move Pads III and playing the game Wool Crush, Alice came with a new idea! In this version, instead of moving around with the players, why don’t we move the pads?
There is a $N \times M$ grid with $N$ rows and $M$ columns, $(1, 1)$ denotes the top-left corner and $(N, M)$ denotes the bottom-right corner. There are also $K$ pads, the $i^{th}$ pad is located at $(X_i, Y_i)$, with a designated direction $D_i$. $D_i$ is either U (up), D (down), L (left) or R (right).
Alice is planning to clear the grid such that no pads remain on it. To do this, she can push the pads away. For a pad, there are some restrictions on its movements:
- It can only travel along its designated direction.
- It can only be pushed away if and only if there are no other pads currently on the grid along its path to the boundary.
- Once it’s pushed away, it leaves the grid and no longer block other pads.
As Alice wants to leave the grid, she asks you: Is it possible to clear the grid? If so, she also wants a possible sequence of moves of pushing away the pads.
Input
The first line contains three integers $N, M$ and $K$, denoting the grid size and the number of pads.
For the following $K$ lines, each line contains $X_i, Y_i$ and $D_i$, denoting the position and the direction of the $i^{th}$ pad respectively.
Output
If it’s impossible to clear the grid, output $-1$ on a single line.
Otherwise, output $K$ lines. Each line contains two integers, denoting which pad is being pushed away in order. If there are multiple answers, output any of them.
Subtasks
For all test cases, $1 \le N, M \le 10^6$, $1 \le K \le min(N \times M, 5 \times 10^5)$, $1 \le X_i \le N$, $1 \le Y_i \le M$, $D_i =$ U, D, L or R
| Subtask | Score | Additional Constraints |
|---|---|---|
| $1$ | $13$ |
$N = 1$ $K = 2$ All pads have the same direction |
| $2$ | $11$ |
$N, M \le 3000$ All pads have the same direction |
| $3$ | $18$ | $N = 1$ |
| $4$ | $16$ |
$N, M \le 20$ |
| $5$ | $20$ |
$N, M \le 300$ |
| $6$ | $14$ |
$N \times M \le 9 \times 10^6$ $K \le 10^5$ |
| $7$ | $8$ | No Additional Constraints |
Push Pads Game
Sample Test Cases
| Input | Output | |
|---|---|---|
| 1 4 2 1 2 L 1 4 L |
1 2 1 4 |
|
This test case satisfies the special constraints of subtasks $1-3$. Refer to the image. We can first push away $(1, 2)$ first to clear up the road for $(1, 4)$, then push away $(1, 4)$. 
|
||
| 2 3 3 1 2 D 2 1 R 2 3 U |
1 2 2 3 2 1 |
|
This image shows how the pads are pushed away for sample test $2$. 
|
||
Scoring: Per Subtask
Authored by s22f26
Appeared in 2026 Mini Comp 4