题目描述

好消息，江桥不想收集钻石了。

坏消息，江桥开始收集金币了。

有一个 $n \times m$ 的网格地图（$n$ 行 $m$ 列），其中 $(i,j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的单元格。每个单元格中均有一个字符 $s_{i,j}$。江桥将会控制机器人来拾取金币。具体规则如下：

如果 $s_{i,j}$ 是 #，那么 $(i,j)$ 单元格是无法通过的，此处是障碍物；

如果 $s_{i,j}$ 是 .，那么该单元格是可以通过的，此处是空地；

如果 $s_{i,j}$ 是 @，那么该单元格是可以通过的，此处有一个金币（拾取后就会变成空地）。

如果 $s_{i,j}$ 是 R，那么该单元格是可以通过的，此处是机器人的初始位置（机器人离开后就变成空地）。

接下来江桥将会发出 $q$ 条指令，指令格式为 $op \space c \space k$ 。其中 $c$ 为 U,D,L,R 其中之一，分别表示机器人往上/下/左/右移动，即，假设机器人当前位于 $(x,y)$：

如果 $c =$ U 且 $(x-1,y)$ 单元格可以通过，则移动到 $(x-1,y)$ 单元格。

如果 $c =$ D 且 $(x+1,y)$ 单元格可以通过，则移动到 $(x+1,y)$ 单元格。

如果 $c =$ L 且 $(x,y-1)$ 单元格可以通过，则移动到 $(x,y-1)$ 单元格。

如果 $c =$ R 且 $(x,y+1)$ 单元格可以通过，则移动到 $(x,y+1)$ 单元格。

否则，停留在 $(x,y)$ 格。

机器人会按此规则移动 $k$ 次。并且，如果 $op = 1$，则表示移动过程中不收集单元格中的金币，如果 $op = 2$ 则表示移动过程中收集单元格中的金币。如果江桥选择收集，那么机器人移动前所在单元格和移动完成后所在单元格的金币都会被收集。

注意，如果某次移动的目标位置超出了地图边界，或者移动的目标位置是障碍物，机器人都会保持原地不动。

例如，江桥发出的指令为 $2 \space U \space 3$，假设机器人当前位于 $(x,y)$，机器人首先会捡起当前格子的金币（如果存在的话），然后检查 $(x-1,y)$ 是否可通过，是则移动过去并捡起金币（如果有的话），否则站在原地不动。如果可以移动到 $(x - 1,y)$，就再检查 $(x-2,y)$ 是否可通过，是则移动过去并捡起金币（如果有的话），否则站在原地不动。如果还可以移动到 $(x - 2,y)$，就再检查 $(x-3,y)$ 是否可通过，是则移动过去并捡起金币（如果有的话），否则站在原地不动。如此，机器人最多会走 $k = 3$ 步。

请问机器人最终停留的位置，以及机器人捡到金币的数量。

输入格式

第一行两个正整数 $n,m,q$，表示地图的行数和列数、指令数量。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串 $s_i$，表示地图的第 $i$ 行。

接下来 $q$ 行，每行一个指令，格式为 $op \space c \space k$。

输出格式

输出三个整数 $x,y,ans$，分别表示机器人最终位置的单元格坐标、 机器人捡到金币的数量。

5 5 6
#@.#@
...R#
.#@..
@..@.
#@@@.
2 L 1
1 D 10
2 L 3
2 R 5
1 U 3
2 L 2

3 3 4

样例解释

机器人初始位于 $(2,4)$ ，行动如下：

• 2 L 1，机器人从 $(2,4)$ 移动到 $(2,3)$ 。没有捡到金币。
• 1 D 10，机器人从 $(2,3)$ 移动到 $(5,3)$ 。移动 $3$ 次就停止了，因为无法再往下移动了。
• 2 L 3，机器人从 $(5,3)$ 移动到 $(5,2)$ 。移动 $1$ 次就停止了，因为 $(5,1)$ 是障碍物无法通过，所以停留在 $(5,2)$ 。捡到 $(5,2),(5,3)$ 上的 $2$ 枚金币。
• 2 R 5，机器人从 $(5,2)$ 移动到了 $(5,5)$ 。移动 $3$ 次就停止了，因为无法再往右移动了。捡到 $(5,4)$ 上的 $1$ 枚金币（ $(5,2),(5,3)$ 上的金币已经被捡起）。
• 1 U 3，机器人从 $(5,5)$ 移动到了 $(3,5)$ 。移动 $2$ 次就停止了，因为 $(2,5)$ 是障碍物无法通过，所以停留在 $(3,5)$ 。
• 2 L 2，因此机器人从 $(3,5)$ 移动到 $(3,3)$ 。捡到 $(3,3)$ 上的 $1$ 枚金币。

机器人在移动过程中捡到金币的数量为 $1+2+1 = 4$ 。

数据规模与约定

下发文件

下发文件对应子任务 $1,2,3,4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,m,n\times m \leq 2 \times 10^6,1 \leq q \leq 10^5,|s_i| = m,s_{i,j} \in \{.,\#,@,R\}$ 且 R 恰好有一个，$op \in \{1,2\},c \in \{U,D,L,R\},1 \leq k \leq 10^2$。