题目背景

1G, 8s, hoppers2

请注意本题特殊的时间限制。

题目描述

Joshua 在 Minecraft 中建造了一个工厂，它由一个网格组成，网格的每个单元格里都有一个所谓的漏斗（hopper）。一个漏斗可以在其内部存放一件物品，并指向另一个漏斗，该漏斗要么位于它的正上方、正下方、左侧或右侧。每秒一次，若某个漏斗内有物品，它会将该物品推送到其所指向的那个漏斗。有时这会导致某个漏斗在同一时刻同时拥有多件物品。显然这不可行，因为在那一秒内被推入该漏斗的所有物品都会被销毁。

Joshua 希望拥有一个碰撞不多且稳定的工厂。他因此给出了一份关于物品如何摆放以及工厂应当如何布局的方案，并且现在想要知道对每件物品来说，它会发生碰撞还是会在工厂中无限循环。对于所有会发生碰撞的物品，他还想知道碰撞发生的位置，以便之后更新设计。请你编写程序帮助他！

$\qquad$

图 1：样例 1 中的工厂在启动前以及 1 秒后的状态。注意中央格子里有 3 个物品发生了碰撞。

输入格式

第一行包含整数 $R, C$（满足 $2 \le R \cdot C \le 10^6$）和 $N$（$1 \le N \le 10^5$），分别表示网格的行数与列数，以及方案中的物品数量。

接下来有 $R$ 行描述工厂的布局。每一行由一个长度为 $C$ 的字符串组成。网格中的每个字符表示该格子里的漏斗所指向的方向。字符只会是 v（向下）、<（向左）、^（向上）或 >（向右）。保证每个漏斗都指向另一个漏斗。

随后有 $N$ 行，每行包含两个整数 $P_r$（$0 \le P_r \le R - 1$）和 $P_c$（$0 \le P_c \le C - 1$），表示第 $i$ 个物品的起始行与列。保证初始时没有任何漏斗同时包含两件或以上的物品。

输出格式

按输入顺序对每件物品各输出一行：如果该物品永远不会与任何东西发生碰撞，则输出字符串 $\texttt{cycle}$；否则输出 “$r\ c$”，表示它在第 $r$ 行第 $c$ 列的漏斗处发生碰撞（从 0 开始计数）。

3 3 5
vvv
>v<
>>^
0 1
1 0
1 2
2 0
2 2

1 1
1 1
1 1
cycle
cycle

1 2 2
><
0 0
0 1

cycle
cycle

3 3 3
vvv
v<<
>^^
0 0
0 2
2 2

cycle
1 2
1 2

提示

子任务

本题采用捆绑测试。

子任务编号	分值	限制
$1$	$10$	$R \cdot C \le 1000,\ N \le 1000$
$2$	$35$	$N \le 1000$
$3$	$15$	若某个漏斗属于一个环路，则最多只有一个其他漏斗指向它。
$4$	$25$	没有漏斗指向上方。
$5$	$15$	无额外限制。