Cyberland (ABC) 的自动面包店最近买了一张 n × m 的长方形桌子。为了服务食客,ABC 在桌子周围设置了座位。每个座位的大小等于一个单位正方形,所以总共有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 ≤ n ≤ 105, 1 ≤ m ≤ 10, 1 ≤ q ≤ 105),用空格分隔。
接下来n行,每行包含m个字符,描述表格。字符只能是“<^>”之一。
接下来 q 行,每行描述一个事件。格式为“C x y c”或“A x y”(连续元素用空格分隔)。保证 1 ≤ x ≤ n, 1 ≤ y ≤ m。 c 是集合“<^>”中的一个字符。
最多有 10000 个“C”类型的查询。
输出
对于每个“A”类型的事件,在一行中输出两个整数tx,ty,用空格分隔,表示(x,y)的目的地是(tx,ty)。
如果存在无限循环,则应输出 tx = ty = - 1。
示例
输入 #1
2 2 3 >> ^^ A 2 1 C 1 2 < A 2 1
输出 #1
1 3 -1 -1
输入 #2
4 5 7 ><<^< ^<^^> >>>^> >^>>^ A 3 1 A 2 2 C 1 4 < A 3 1 C 1 2 ^ A 3 1 A 2 2
输出 #2
0 4 -1 -1 -1 -1 0 2 0 2
注意
对于第一个样本:
如果面包是从 (2, 1) 出发的,那么它将在 (1, 3) 处离开桌子。
将(1, 2)的传送带改为“<”后,当面包再次从(2, 1)走时,会卡在“"><”处,所以输出为(- 1, - 1)。