CF487D Conveyor Belts

赛博之地的自动面包店（ABC）最近购买了一张 $n \times m$ 的矩形餐桌。为了招待食客，ABC 在餐桌周围放置了座位。每个座位的大小都是 $1$ 个单位正方形，所以一共放置了 $2(n+m)$ 个座位。 ABC 在餐桌的每一个单位格子上都设置了传送带。传送带有三种类型：“^”、“”。“^” 传送带可以将物品向上运送，“” 可以向右运送。 我们将餐桌的行自上而下编号为 $1$ 到 $n$，列自左到右编号为 $1$ 到 $m$。我们认为桌面上方和下方的座位分别位于第 $0$ 行和第 $n+1$ 行。桌面左侧和右侧的座位分别位于第 $0$ 列和第 $m+1$ 列。由于传送带方向的限制，目前还没有办法让坐在第 $n+1$ 行的食客被服务到。 给定最初的餐桌状态，随后将会有 $q$ 个事件，依次进行。事件有两种类型： - “A $x$ $y$” 表示在第 $x$ 行第 $y$ 列会出现一块面包（我们用 $(x, y)$ 表示该位置）。面包会沿着传送带的方向移动，直到到达某一位食客的座位。也有可能面包会陷入无限循环。你的任务是模拟这一过程，并输出面包的最终位置，或者判断是否会陷入无限循环。 - “C $x$ $y$ $c$” 表示将 $(x,y)$ 位置的传送带类型更改为 $c$。 每一次查询都是独立的，即便面包陷入了无限循环，也不会影响随后的查询。 #

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n \le 10^{5}, 1 \le m \le 10, 1 \le q \le 10^{5}$），用空格分隔。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述餐桌上的传送带。字符只可能是 “”。 接下来的 $q$ 行，每行描述一个事件，格式为 “C x y c” 或 “A x y”（各元素之间用空格分隔）。保证 $1 \le x \le n, 1 \le y \le m$。$c$ 是集合 “” 中的一个字符。 “C” 事件最多不超过 $10000$ 次。 #

对于每个 “A” 类型的事件，输出两个整数 $tx$、$ty$，用空格分隔，表示起点 $(x,y)$ 的面包最终会到达 $(tx,ty)$ 位置。 如果陷入了无限循环，应该输出 $tx=ty=-1$。 #

对于第一个样例： 如果面包从 $(2,1)$ 出发，它会从 $(1,3)$ 出界。 在将 $(1,2)$ 的传送带更改为 “