题目背景

English statement. You must submit your code at the Chinese version of the statement.

小 F 来到了迷雾之森。

题目描述

整个迷雾之森可以由一个 $n \times m$ 的矩阵表示，X 代表有迷雾的地块，. 代表空地。从上到下给每行标号为 $1,2,\cdots,n$，从左到右给每列标号为 $1,2,\cdots,m$。除此之外，还会给定一个迷雾系数 $k$。

小 F 进行了 $q$ 次移动。第 $i$ 次移动由一个字符 $c_i$，两个数字 $a_i,b_i$ 描述，更具体地说：

• $c_i$ 为 U 时，向上走 $a_i$ 步。
• $c_i$ 为 D 时，向下走 $a_i$ 步。
• $c_i$ 为 L 时，向左走 $a_i$ 步。
• $c_i$ 为 R 时，向右走 $a_i$ 步。

当然，小 F 不可以走出这个 $n \times m$ 的范围。换句话说，若走到边界处，立即结束此次移动。

若第 $i$ 次移动结束后小 F 停留在有迷雾的地块上，则小 F 会对从 $i+k$ 开始，之后每 $k$ 次移动的 $c$ 进行一次修改，一共修改 $b_i$ 个移动。也就是说，小 F 会对 $c_{i+k},c_{i+2\times k},\cdots,c_{i+b_i \times k}$ 进行一次修改（保证 $i+b_i\times k \leq q$）。若 $b_i=0$ 则相当于不做修改。注意所有操作的 $k$ 是一样的。

修改 $c_x$ 即为按照以下规则替换 $c_x$：

• 若 $c_x$ 为 U，则替换为 D。
• 若 $c_x$ 为 D，则替换为 U。
• 若 $c_x$ 为 R，则替换为 L。
• 若 $c_x$ 为 L，则替换为 R。

初始时小 F 在点 $(1,1)$ 处，请输出 $q$ 次移动后小 F 所在的位置 $(x,y)$。

输入格式

第一行四个整数 $n,m,q,k$。

接下来 $n$ 行，每行一个长度为 $m$，由 . 和 X 构成的字符串，描述整个迷雾之森。

接下来 $q$ 行，每行先是一个字符 $c_i$，然后依次是两个整数 $a_i,b_i$，描述每次移动。

输出格式

共一行。

两个整数 $x,y$，表示小 F 最终的位置。

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

提示

【样例 1 解释】

小 F 的位置变化如下：

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

序列 $c$ 的变化如下：

$ \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$

【数据规模与约定】

本题采用捆绑测试。

对于 $100 \%$ 的数据，保证：

• $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$ 为 L，R，U，D 四个字符中的一个。