B. Bouncing Chaos
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Abo Adnan is experimenting with two balls bouncing inside a rectangular grid of size $$$n \times m$$$. The grid cells are numbered from $$$(1, 1)$$$ to $$$(n, m)$$$.

Each ball starts at a specific cell with an initial direction of movement: UR (up-right), UL (up-left), DR (down-right), or DL (down-left). These directions correspond to moving $$$(-1, +1)$$$, $$$(-1, -1)$$$, $$$(+1, +1)$$$, and $$$(+1, -1)$$$ in terms of $$$(row, column)$$$ changes respectively.

When a ball hits a horizontal boundary (top or bottom edge), its row direction reverses. When a ball hits a vertical boundary (left or right edge), its column direction reverses. The balls move simultaneously at each step, and when they collide both balls' directions will exchange (see the photos below for more understanding).

After $$$k$$$ steps, determine the positions of both balls and print them in lexicographical order.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \le n, m$$$, $$$n \cdot m \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^{12}$$$) — the grid dimensions and the number of steps.

The second line contains two integers $$$i_1$$$, $$$j_1$$$ and a string $$$d_1$$$ ($$$2 \le i_1 \le n-1$$$, $$$2 \le j_1 \le m-1$$$, $$$d_1 \in \{\texttt{UR}, \texttt{UL}, \texttt{DR}, \texttt{DL}\}$$$) — the starting position and direction of the first ball.

The third line contains two integers $$$i_2$$$, $$$j_2$$$ and a string $$$d_2$$$ ($$$2 \le i_2 \le n-1$$$, $$$2 \le j_2 \le m-1$$$, $$$d_2 \in \{\texttt{UR}, \texttt{UL}, \texttt{DR}, \texttt{DL}\}$$$) — the starting position and direction of the second ball.

It is guaranteed that $$$(i_1, j_1) \ne (i_2, j_2)$$$.

Output

Output two lines, each containing two integers — the positions of the two balls after $$$k$$$ steps. Output the positions of the balls in lexicographical order.

Examples
Input
5 7 10
2 3 UR
4 5 DL
Output
2 1
4 7
Input
6 8 15
3 4 DR
5 6 UL
Output
2 5
4 5