406123: GYM102271 B The Cybermen Moonbase (Hard)

B. The Cybermen Moonbase (Hard)time limit per test15 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Thanks to your estimates, Doctor Who and Heidi arrived safely to the Cybermen Moonbase. They just need to find the watches before they can fly away saving the cows. But it's too early to celebrate – the base is protected by Cybermen armed with cannons. Fortunately, the Cybermen have poor implementation of the coordinate system, and can only fire along vertical and horizontal directions. Moreover, you have hacked the Cybernetwork and know at what times the Cybermen are going to fire. You can easily save the Doctor and Heidi by calculating a safe path and uploading it to the TARDIS console before any Cyberman has a chance to fire!

You are given a $$$H \times (W + 1)$$$ grid, where the columns are numbered $$$0$$$ to $$$W$$$ (left to right), and the rows are numbered $$$1$$$ to $$$H$$$ (bottom to top).

The TARDIS starts (at $$$t = 0$$$) from cell $$$(0, S)$$$ (i.e., the cell at $$$0$$$-th column, $$$S$$$-th row) and it needs to reach cell $$$(W, E)$$$. At each time step it can move to one of the three adjacent cells in the next column, i.e., if it is in cell $$$(c, r)$$$, it can move to one of $$$(c + 1, r - 1)$$$, $$$(c + 1, r)$$$, or $$$(c + 1, r + 1)$$$ as long as they are within the grid boundary.

There are $$$W$$$ cannons placed just outside the top-boundary, one per each column $$$1, \dots, W$$$ (facing down). Similarly, there are $$$W$$$ cannons just outside the bottom boundary (facing up), and $$$H$$$ more cannons at the right boundary, one per each row $$$1, \dots, H$$$ (facing left). The Cybermen fire cannons fire at arbitrary times. Once fired, the cannonball travels one cell at each time instant in the firing direction.

The total number of cannon firings is $$$N$$$. The $$$i$$$-th cannon fire is described by a tuple $$$(t_i,d_i,p_i)$$$, where $$$t_i$$$ denotes the time of the firing, and $$$d_i \in \{\text{'U', 'D', 'L'}\}$$$ and $$$p_i$$$ indicate which cannon is fired.

• If $$$d_i = \text{'U'}$$$, then the firing cannon is the one facing up at column $$$p_i$$$.
• If $$$d_i = \text{'D'}$$$, it is the one facing down at column $$$p_i$$$.
• If $$$d_i = \text{'L'}$$$, it is the one facing left at row $$$p_i$$$.

Note that $$$t_i$$$ is the time the $$$i$$$-th cannonball first appears in the cell immediately in front of the fired cannon. Before $$$t_i$$$, the $$$i$$$-th cannonball does not exist. E.g. $$$(10, \text{'D'}, 15)$$$ says that the cannon at the top of the $$$15$$$-th column facing down fires, and at $$$t = 10$$$, the cannonball is at $$$(15, H)$$$.

Your task is to find a path of valid moves from $$$(0,S)$$$ to $$$(W,E)$$$ so that the TARDIS does not collide with any cannonball. Keep in mind that cannonballs themselves can collide with each other, and if two or more cannonballs collide, then they vanish from the grid after the collision.

A collision of entities (the TARDIS or cannonballs) can happen:

1. If they are in the same cell at time $$$t$$$. Then the collision occurs at time $$$t$$$ and none of them will exist after $$$t$$$.
2. If two entities are in two horizontally or vertically adjacent cells at time $$$t$$$, and trying to swap the cells in time $$$t + 1$$$ (i.e., traveling exactly towards each other). In this case the collision occurs between time $$$t$$$ and $$$t+1$$$, and again none of them will exist in time $$$t + 1$$$.

Input

The first line contains 3 space-separated integers, $$$H$$$, $$$W$$$, and $$$N$$$ ($$$2 \leq H \leq 2500$$$, $$$2 \leq W \leq 15000$$$, and $$$1 \leq N \leq 10^6$$$).

The next line contains two space-separated integers $$$S$$$ and $$$E$$$ ($$$1 \leq S, E \leq H$$$).

$$$N$$$ more lines follow, each of which contains an integer $$$t_i$$$ $$$(1 \leq t_i \leq W)$$$, a single upper case letter $$$d_i \in \{ \text{'U', 'D', 'L'}\}$$$, and another integer $$$p_i$$$.

It is guaranteed that if $$$d_i = \text{'L'}$$$, then $$$1 \leq p_i \leq H$$$ and if $$$d_i \in \{\text{'U', 'D'}\}$$$, then $$$1 \leq p_i \leq W$$$.

All tuples $$$(t_i, d_i, p_i)$$$ are distinct.

Output

If there exists a valid path from $$$(0, S)$$$ to $$$(W, E)$$$ that does not collide with a cannonball, output $$$W + 1$$$ lines of integers $$$r_i$$$ which corresponds to the row positions of the path for each column $$$i = 0, \dots, W$$$.

Thus it must hold that $$$r_0 = S$$$, $$$r_W = E$$$, and for all $$$i > 0$$$, $$$|r_i - r_{i-1}| \leq 1$$$.

Otherwise, if no valid path exists, output $$$-1$$$.

ExamplesInput

3 4 1
1 3
1 L 2

Output

1
1
1
2
3

Input

3 4 2
1 3
1 L 2
1 D 3

Output

1
1
2
2
3

Input

3 4 5
1 3
1 L 2
1 D 3
1 U 1
2 D 1
2 D 2

Output

1
2
2
2
3

Input

3 4 7
1 3
1 L 2
1 D 3
1 U 1
2 D 1
2 D 2
2 L 2
2 L 3

Output

-1

Note

Example 1: Here, there are six valid paths and outputting any of them is okay. They are "1 1 1 2 3", "1 1 2 3 3", "1 2 1 2 3", "1 2 2 3 3", "1 2 3 2 3", and "1 2 3 3 3". However, the paths "1 1 2 2 3" and "1 2 2 2 3" are not valid solutions as they would result in a collision of type 2 when traveling from (2, 2) to (3, 2) because the cannonball is traveling from (3,2) to (2,3) at the same time.

Example 2: In this example, the second cannonball collides with the first one at time 2. Hence, in addition to the valid paths of Example 1, the paths "1 1 2 2 3" and "1 2 2 2 3" are also possible in this case.

Example 3: Here, we can no longer use paths "1 1 1 2 3", "1 1 2 3 3", or "1 1 2 2 3" because they collide with the third cannonball in the list. The paths "1 2 3 2 3" and "1 2 3 3 3" are also invalid as they collide with the fifth cannonball in the list.

Example 4: In this last example, it is easy to see that even the remaining three paths of Example 3 are no longer valid, and hence it is impossible for the TARDIS to reach the destination using valid moves.