골드버그 기계 2

루베가 새롭고 놀라운 장치를 들고 다시 사업에 나섰다! 이 장치는 $n$행 $m$열 격자로 이루어져 있다. 일부 칸에는 오른쪽 또는 아래쪽을 가리키는 화살표가 있고, 나머지 칸은 비어 있다. 왼쪽 위 모서리 칸에 토큰을 놓으면 토큰이 화살표 방향을 따라 움직이기 시작한다. 토큰이 지나간 화살표는 토큰이 그 칸을 떠날 때 방향이 바뀐다. 구체적으로, 토큰이 오른쪽 화살표 칸에 있으면 바로 오른쪽 칸으로 이동하고, 원래 칸의 화살표는 아래쪽으로 바뀐다. 아래쪽 화살표 칸에 있으면 바로 아래 칸으로 이동하고, 원래 칸의 화살표는 오른쪽으로 바뀐다. 토큰이 빈 칸에 도착하거나 격자 밖으로 나가면 이동이 멈추고 토큰은 버려진다.

예를 들어 아래 왼쪽의 $3 \times 3$ 격자를 보자. ">"는 오른쪽 화살표, "v"는 아래쪽 화살표, "."는 빈 칸을 나타낸다. 나머지 두 격자는 왼쪽 위 모서리에 토큰을 하나 놓은 뒤의 상태와, 그 뒤에 토큰을 하나 더 놓은 뒤의 상태이다.

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

루베는 자신의 장치를 여러 개 만들어 좋은 값에 팔고 있다. 그런데 매우 까다로운 고객 두 명이 자기 장치가 똑같아 보인다고 주장한다. 독특한 것을 좋아하는 그들의 취향에 맞지 않는다는 것이다. 실제로 두 장치는 모양이 같다. 즉 화살표가 있는 칸의 집합은 두 장치에서 같지만, 화살표 방향의 배치는 다를 수 있다.

루베는 장치를 수정하기로 했다. 겉보기에는 비슷해도, 두 장치 중 한쪽이나 양쪽에 토큰을 몇 개든 넣은 뒤에 화살표 배치가 같아지는 일이 절대 없도록 만드는 것이다. 고객들은 요청을 보내며, 각 요청은 두 장치 중 하나에서 화살표 방향 하나를 바꾼다. 요청마다 루베는 두 장치가 결국 같은 화살표 배치에 도달할 수 있는지 판단해야 한다. 도달할 수 있다면, 토큰을 두 장치에 어떻게 나누어 넣든 같은 배치가 되기까지 필요한 토큰의 최소 총개수를 구해야 한다. 변경 사항은 계속 유지되며, 요청에 답한 뒤에도 되돌리지 않는다.

루베는 장치가 너무 복잡해서 이 문제가 무척 어려워 보인다고 다시 한숨을 쉰다. 고객의 요청에 모두 답해 주어 회사가 소송으로 문을 닫는 일을 막아 달라.

첫째 줄에 세 정수 $n$, $m$, $q$가 주어진다. 각각 격자의 크기와 요청의 개수이다($1 \leq n, m \leq 100$, $1 \leq q \leq 10^5$).

이어지는 $n$줄은 첫 번째 장치의 상태를 나타낸다. 각 줄은 $m$개의 문자로 이루어지며, 각 문자는 ">", "v", "." 중 하나이다. 이는 각각 오른쪽 화살표, 아래쪽 화살표, 빈 칸을 뜻한다.

그 다음 $n$줄은 두 번째 장치의 상태를 같은 형식으로 나타낸다. 두 격자는 모양이 같다. 즉 화살표(방향은 무관)가 있는 칸의 집합이 같다. 각 격자의 왼쪽 위 모서리 칸에는 화살표가 있으며, 각 장치에 토큰을 몇 개 넣으면 모든 화살표 칸에 토큰이 도달할 수 있다.

그 다음 $q$줄은 받은 순서대로 요청을 나타낸다. 각 요청은 세 정수 $t$, $r$, $c$로 이루어진다. 이는 조작할 장치 번호($t \in \{1, 2\}$)와 방향을 바꿀 칸의 행과 열이다($1 \leq r \leq n$, $1 \leq c \leq m$). 행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 1부터 번호를 매긴다. 각 요청에서 지정된 칸에는 반드시 화살표가 있다.

구역 사이에는 보기 편하도록 빈 줄이 있을 수 있다.

$q + 1$줄을 출력한다. $0, 1, 2, \ldots, q$개의 요청을 차례로 처리한 뒤의 답을 순서대로 출력한다. 현재 상태의 두 장치가 두 장치 중 어디에든 토큰을 몇 개 넣더라도 같은 화살표 배치에 도달할 수 없다면 $-1$을 출력한다. 그렇지 않다면 같은 배치에 도달하기까지 넣어야 하는 토큰의 총개수의 최솟값을 출력한다.

숫자 앞에 0을 붙이지 않는다.