Rube 又带着他那令人惊叹的新发明回归了！该装置由一个 $n$ 行 $m$ 列的网格组成，其中一些格子包含指向右侧或下侧的箭头，另一些格子则是空的。我们可以在网格的左上角放置一个标记（token），随后奇迹发生了：标记会根据箭头的方向在格子间移动。此外，标记每经过一个箭头，该箭头在标记离开格子后就会改变方向。形式化地说，如果标记位于一个指向右侧（或下侧）的箭头所在的格子中，它会移动到紧邻右侧（或下侧）的格子，而原格子中的箭头会切换为指向下侧（或右侧）。当标记到达一个空格子或离开网格时，移动停止，此时标记被丢弃。

举个例子，考虑下方左侧所示的 $3 \times 3$ 网格（“>”和“v”分别描述指向右侧和下侧的箭头，“.”描述空格子）。另外两个网格展示了在网格左上角放置一个标记后，以及在此之后又放置另一个标记后的网格状态。

v> v>> >>> vv> -> v>> -> >>> v.> v.> >.v

Rube 制造了许多该机器的副本并以高价售出。然而，他遇到了两位非常挑剔的顾客，他们认为这些机器看起来一模一样，这冒犯了他们对独特事物的高雅品味。事实上，他们的机器具有相同的形状，即两台机器中包含箭头的格子集合是相同的，尽管箭头配置本身可能不同。

Rube 同意对机器进行修改，使得尽管看起来相似，但无论在其中任何一台或两台机器中投入多少个标记，它们最终都不会达到相同的箭头配置。现在，他被顾客关于如何精确修改机器的请求所淹没：每个请求都是改变其中一台机器中某个箭头的状态。在每次请求后，Rube 需要确定两台机器是否最终能达到相同的箭头配置，如果可以，在达到该状态之前，需要在两台机器中放置标记的总次数的最小值是多少（标记可以任意分配给两台机器）。注意，这些更改是持久的，即在给出请求的答案后，不会撤销任何修改。

Rube 再次感叹他发明的复杂性，因为这项任务看起来极其困难。请帮助他回答所有顾客的请求，避免他因被起诉而破产。

输入格式

第一行包含三个整数 $n, m, q$ —— 网格的维度和请求的数量（$1 \le n, m \le 100, 1 \le q \le 10^5$）。

接下来的 $n$ 行描述了第一台机器的状态。每行包含 $m$ 个字符。每个字符为 “>”、“v” 或 “.”，分别描述指向右侧的箭头、指向下侧的箭头或空格子。

随后的 $n$ 行描述了第二台机器的状态，格式相同。保证两个网格具有相同的形状，即它们在相同的格子集合中包含箭头（无论方向如何）。此外，保证每个网格的左上角都包含一个箭头，并且在每台机器中放置一定数量的标记后，标记可以到达每一个箭头格子。

接下来的 $q$ 行按接收顺序描述请求。每个请求由三个整数 $t, r, c$ 描述 —— 要操作的机器编号（$t \in \{1, 2\}$），以及要切换箭头的格子的行号和列号（$1 \le r \le n, 1 \le c \le m$）。行号从上到下编号，列号从左到右编号，均从 1 开始。保证每次请求中要切换的格子都包含一个箭头。

输出格式

输出 $q + 1$ 行，分别包含处理完第 $0, 1, 2, \dots, q$ 个请求后的答案。如果机器在当前状态下，无论在其中放置多少个标记都无法达到相同的箭头配置，则输出 $-1$。否则，输出在它们达到相同配置之前需要放置的标记总数的最小值。

不要输出前导零。

样例

输入 1

3 3 9
>v>
vv>
v.>
v>>
v>>
v.>
2 3 1
2 2 1
2 1 1
1 3 3
1 2 2
2 3 3
2 3 1
1 1 2
1 2 1

输出 1

1
-1
-1
2
14
-1
-1
-1
-1
0