题目描述

Rube 又造出了新的机关。机关是一张 $n$ 行 $m$ 列的网格，其中部分格子放有箭头，箭头方向为向右 > 或向下 v，其余格子为空 .。

每次可以从左上角格子放入一枚弹珠。弹珠按箭头移动：若当前格子的箭头向右，则弹珠移动到右侧相邻格子；若箭头向下，则移动到下方相邻格子。当弹珠离开一个带箭头的格子时，该格子的箭头方向会立刻切换：

• > 变为 v；
• v 变为 >。

当弹珠到达空格，或离开整个网格时，移动停止，弹珠被丢弃。

Rube 卖出了两台形状相同的机关。所谓形状相同，是指两台机关中放有箭头的格子集合完全相同；但对应箭头的初始方向可能不同。

顾客会不断提出修改请求：每次选择其中一台机关的某个箭头格子，将该箭头方向切换一次。修改会永久保留。

在初始状态以及每次修改后，你需要回答：是否存在一种方式，向两台机关中总共放入若干枚弹珠，使它们最终拥有完全相同的箭头方向配置？弹珠可以任意分配给两台机关。

如果不可能，输出 $-1$。如果可能，输出所需放入弹珠总数的最小值。

输入格式

第一行包含三个整数 $n,m,q$，分别表示网格行数、列数和请求数量。

接下来 $n$ 行描述第一台机关，每行包含 $m$ 个字符，字符为 >、v 或 .。

再接下来 $n$ 行描述第二台机关，格式相同。

保证两台机关的形状相同，即箭头所在格子集合相同；左上角格子一定有箭头；并且每个箭头格子都可能在某些放入弹珠的过程中被访问到。

接下来 $q$ 行，每行包含三个整数 $t,r,c$，表示将第 $t$ 台机关中第 $r$ 行第 $c$ 列的箭头切换方向。

输入各部分之间可能存在额外空行。

输出格式

输出 $q+1$ 行，依次表示处理前 $0,1,2,\ldots,q$ 个请求后的答案。

若当前两台机关无法通过放入弹珠达到相同箭头配置，输出 $-1$；否则输出所需放入弹珠总数的最小值。

数据范围

• $1\le n,m\le 100$；
• $1\le q\le 10^5$；
• $t\in\{1,2\}$；
• $1\le r\le n$；
• $1\le c\le m$；
• 每次请求修改的格子一定包含箭头。

样例 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
2
14
-1
-1
-1
-1
0