파로는 어둠을 무서워하는 소녀입니다.

저녁이 되어 파로가 참석했던 학술 회의가 끝났습니다. 리세도 수업을 마치고 파로를 데리러 기차역으로 왔습니다.

하지만 강의실 건물에 갑자기 정전이 발생했고, 파로는 칠흑 같은 어둠 속에 갇히고 말았습니다.

다행히 리세는 이미 파로와 같은 층에 도착해 있었습니다.

하지만 건물의 구조가 너무 복잡해서, 두 사람은 건물의 정확한 구조를 기억해내지 못했습니다. 리세의 학교 건물은 각 층의 구조가 매우 규칙적입니다.

형식적으로 말하자면, 건물 한 층의 평면 구조는 2차원 평면상에서 왼쪽 위 꼭짓점이 $(0,0)$이고 오른쪽 아래 꼭짓점이 $(n,m)$인 직사각형(이하 $(0,0) - (n,m)$ 직사각형) 내부에 그릴 수 있으며, 이 직사각형의 네 변은 건물의 외벽(즉, 반드시 존재하는 네 개의 벽)입니다.

본 문제의 좌표계는 일반적인 평면 직각 좌표계와 다르다는 점에 유의하십시오. $(0,0)$은 왼쪽 위 꼭짓점이고 $(n,m)$은 오른쪽 아래 꼭짓점입니다. $(i,j)$는 가로 좌표가 $i$이고 세로 좌표가 $j$인 점이 아니라, 제 $i+1$행 제 $j+1$열의 꼭짓점을 의미합니다.

각 벽(통과할 수 없는 부분)은 두 끝점이 $(i,j)$와 $(i',j')$인 선분으로, $(i,j) - (i',j')$ 벽이라고 표기합니다. 여기서 $|i-i'| + |j-j'| = 1$이며, $i, i'$는 $[0,n]$ 범위의 정수이고, $j, j'$는 $[0,m]$ 범위의 정수입니다(이후 $(i,j) - (i',j')$ 표기를 사용할 때는 항상 이 조건을 만족함을 보장합니다).

파로는 이런 구조에서 리세를 찾을 수 있는 방법이 하나 있다는 것을 알고 있습니다. 파로는 왼손으로 벽을 짚고, 팔을 벽면과 수직으로 유지한 채 앞으로 걸어갑니다. 모퉁이를 돌 때도 왼손이 계속 벽에 닿아 있는 상태를 유지합니다. 이 방법을 따르면 파로는 한 바퀴를 돌아 리세와 만날 수 있습니다.

처음에 이 층의 초기 구조가 주어지며, 이후 $q$개의 요청이 주어집니다.

• 연산 $1$: 입력 형식이 $1\ x_0\ y_0\ x_1\ y_1$인 경우: 현재 구조에 $(x_0, y_0) - (x_1, y_1)$ 벽을 추가합니다. 이전에 해당 벽이 존재하지 않았으며, 해당 벽이 $(0, 0)-(n, m)$ 직사각형의 네 변에 포함되지 않음이 보장됩니다.
• 연산 $2$: 입력 형식이 $2\ x_0\ y_0\ x_1\ y_1$인 경우: 현재 구조에서 $(x_0, y_0) - (x_1, y_1)$ 벽을 삭제합니다. 이전에 해당 벽이 존재했으며, 해당 벽이 $(0,0) - (n,m)$ 직사각형의 네 변에 포함되지 않음이 보장됩니다.
• 연산 $3$: 입력 형식이 $3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1$인 경우: 파로는 현재 $(x_0,y_0) - (x_1,y_1)$ 벽의 중점인 $(\frac{x_0+x_1}{2}, \frac{y_0+y_1}{2})$에 위치하며, $d_0$은 $[0,1]$ 범위의 정수로 파로가 벽의 어느 쪽에 있는지를 나타냅니다($d_0 = 0$은 벽의 왼쪽/위쪽, $d_0 = 1$은 오른쪽/아래쪽). 리세는 현재 $(x_2,y_2) - (x_3,y_3)$ 벽의 중점인 $(\frac{x_2+x_3}{2}, \frac{y_2+y_3}{2})$에 위치하며, $d_1$은 $d_0$과 같은 형식입니다. $(x_0,y_0) - (x_1,y_1)$ 벽과 $(x_2,y_2) - (x_3,y_3)$ 벽이 존재하며, 파로와 리세의 위치가 모두 $(0,0) - (n,m)$ 직사각형 내부에 있음이 보장됩니다. 파로가 문제에서 설명한 방법을 따라 리세를 찾기 위해 이동해야 하는 총 거리를 구하십시오($(i,j) - (i',j')$ 벽의 길이는 $1$이며, 시작점과 끝점이 벽의 중점이므로 반쪽 벽의 길이는 $\frac{1}{2}$입니다).

입력

입력은 총 $2n+q$ 줄입니다.

첫 번째 줄에는 세 정수 $n, m, q$가 주어집니다.

다음 $n$ 줄에는 각 줄마다 $m-1$개의 $[0,1]$ 정수가 주어지며, 제 $i$행 제 $j$열의 정수가 $1$이면 $(i,j) - (i-1,j)$ 구간에 벽이 있음을, $0$이면 벽이 없음을 의미합니다.

다음 $n-1$ 줄에는 각 줄마다 $m$개의 $[0,1]$ 정수가 주어지며, 제 $i$행 제 $j$열의 정수가 $1$이면 $(i,j) - (i,j-1)$ 구간에 벽이 있음을, $0$이면 벽이 없음을 의미합니다.

다음 $q$ 줄에는 각 줄마다 하나의 연산이 문제에 설명된 형식으로 주어집니다.

출력

각 질의에 대해 파로가 문제에서 설명한 방법을 따라 리세를 찾기 위해 이동해야 하는 총 거리를 출력하십시오. 만약 파로가 해당 방법을 따라 리세를 찾을 수 없다면 $\mathbf{-1}$을 출력하십시오.

예제

예제 입력 1

3 3 4
0 0
1 0
0 0
1 0 1
0 0 1
3 3 0 3 1 0 0 3 1 3 0
1 2 1 2 0
2 1 0 1 1
3 2 2 2 3 1 1 2 1 3 0

예제 출력 1

11
16

참고

위 그림은 예제 입력의 첫 번째 질의에서 파로의 이동 경로를 나타내며, 이동하는 동안 파로의 왼손은 반드시 벽에 닿아 있어야 합니다.

서브태스크

• 데이터의 $10\%$: $5\le n, m\le 50, 1\le q\le 2\times 10^3$.
• 데이터의 $30\%$: $1$번 연산이 없음.
• 데이터의 $30\%$: 파로와 리세가 입력 형식상 가능한 임의의 위치에 서 있을 때, 항상 파로가 리세를 만날 수 있음이 보장됨.
• 데이터의 $100\%$: $5\le n, m\le 500, 1\le q\le 2\times 10^5$.