Description

The Misty Forest can be represented as a grid of size $n \times m$, where cells with character X have dense fog, while cells with character . are empty.

Denote the cell in the $i$-th row from the top and the $j$-th column from the left as $(i,j)$.

A fog constant $k$ is given.

FL_sleake made $q$ moves. The $i$-th move consists of one character $c_i$ and two integers $a_i$ and $b_i$. Specifically:

• If $c_i$ is U, take $a_i$ steps upwards.
• If $c_i$ is D, take $a_i$ steps downwards.
• If $c_i$ is L, take $a_i$ steps to the left.
• If $c_i$ is R, take $a_i$ steps to the right.

In each step, he will go by exactly one cell towards the given direction. However, if he will move outside of the forest after the step, he just stays in the current cell instead.

If FL_sleake stays in a cell with fog after he performs the $i$-th move, he will perform an operation on $c_{i+k},c_{i+2\times k},\dots, c_{i+b_i\times k}$. If $b_i=0$, No operations will be performed.

An operation on a character $c$ is replacing it with another character representing the opposite direction of $c$. That is:

• If $c$ is U, replace it with D.
• If $c$ is D, replace it with U.
• If $c$ is L, replace it with R.
• If $c$ is R, replace it with L.

Initially FL_sleake is at $(1,1)$, please find his position after the $q$ moves.

Recall that $k$ is the same for all moves.

Input Format

The first line of the input contains four integers $n,m,q,k$.

In the following $n$ lines, each line contains a string of length $m$, representing the Misty Forest.

In the following $q$ lines, the $i$-th line contains one character $c_i$, and two integers $a_i$ and $b_i$, representing the $i$-th move.

Output Format

Output a single line containing two integers $x$ and $y$, representing that FL_sleake's position after the $q$ moves is $(x,y)$.

3 3 4 1
..X
.XX
XXX
D 1 2
R 1 2
D 2 0
L 1 0

1 3

10 10 8 2
XX.XX.X...
XXX..XXX.X
XXX.X.XXXX
XXXXXXX.X.
.XX...XX.X
.XXX.X.X.X
...XXX.XXX
XX...XX...
X..XX....X
XXXXX...XX
U 2 1
L 1 3
R 3 1
L 1 2
D 2 1
R 5 1
L 4 0
D 3 0

1 10

Hint

Example Explanation

In the first example, FL_sleake's position at the beginning and after each move is as follow:

$(1,1) \rightarrow (2,1) \rightarrow (2,2)\rightarrow (1,2) \rightarrow (1,3)$

The sequence $c_1,c_2,\dots,c_q$ at the beginning and after each move is as follow:

$\lbrace \texttt{D,R,D,L} \rbrace \rightarrow \lbrace \texttt{D,R,D,L} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace \rightarrow \lbrace \texttt{D,R,U,R} \rbrace$

Constraints

Subtasks are used in this problem.

For all tests, it is guaranteed that:

• $1 \leq n,m \leq 500$
• $1 \leq k \leq 20$
• $1\leq q \leq 2 \times 10^5$
• $1 \leq a_i,b_i \leq 10^6$
• $c_i \in \{\texttt{L,R,U,D}\}$