「FSLOI Round I」迷雾

**[English statement.](https://www.luogu.com.cn/problem/T500989) 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` 四个字符中的一个。 |子任务|分值|特殊性质| |:-----:|:-----:|:-----:| |$1$|$5$|$q=1$| |$2$|$15$|$n,m,q\leq 100$| |$3$|$20$|$k=1$| |$4$|$30$|$n=1$| |$5$|$30$|无|