The Foggy Forest

You are given a foggy forest represented by an \(n \times m\) matrix. Each cell is either a fog cell denoted by X or a clear cell denoted by .. The rows are numbered \(1,2,\dots,n\) from top to bottom, and the columns are numbered \(1,2,\dots,m\) from left to right. Additionally, a fog coefficient \(k\) is provided.

There are \(q\) moves. The \(i\)-th move is given by a direction character \(c_i\) and two integers \(a_i\) and \(b_i\):

• If \(c_i = 'U'\), move up \(a_i\) steps.
• If \(c_i = 'D'\), move down \(a_i\) steps.
• If \(c_i = 'L'\), move left \(a_i\) steps.
• If \(c_i = 'R'\), move right \(a_i\) steps.

When executing a move, you attempt to take \(a_i\) steps one by one. However, if you are about to leave the \(n \times m\) grid, you immediately stop the current move.

After a move finishes, if your current cell contains fog (i.e. the cell is X), then a modification is applied to some future moves. Specifically, starting from move \(i+k\), and then every \(k\)-th move, you modify a total of \(b_i\) moves. That is, for moves \(c_{i+k}, c_{i+2k}, \dots, c_{i+b_i\cdot k}\) (it is guaranteed that \(i+b_i\cdot k \le q\)), you must replace the moving direction according to the following rules:

• If the direction is U, change it to D.
• If the direction is D, change it to U.
• If the direction is R, change it to L.
• If the direction is L, change it to R.

You start at position \((1,1)\). After executing all \(q\) moves (with modifications applied when required), output your final position as \((x, y)\).

inputFormat

The first line contains four integers \(n\), \(m\), \(k\) and \(q\).

The next \(n\) lines each contain a string of length \(m\) representing the grid. The character X denotes a fog cell and . denotes a clear cell.

Each of the following \(q\) lines contains a character and two integers \(c_i\), \(a_i\), and \(b_i\), representing the \(i\)-th move.

outputFormat

Output two integers \(x\) and \(y\) representing the final row and column positions after performing all moves.

sample

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

3 1