Фалло — девочка, которая боится темноты.

Наступил вечер, академическая конференция, на которой была Фалло, давно закончилась. Лисе тоже закончила занятия и пришла забрать Фалло, чтобы вместе вернуться на вокзал.

Однако в учебном корпусе внезапно отключили электричество, и Фалло оказалась в полной темноте.

К счастью, Лисе уже добралась до того же этажа учебного корпуса.

Но из-за слишком сложной структуры здания они уже не помнят его точную планировку. Структура каждого этажа учебного корпуса Лисе очень упорядочена.

Формально, план этажа можно представить на двумерной плоскости в виде прямоугольника с левым верхним углом в $(0,0)$ и правым нижним углом в $(n,m)$ (обозначим его как прямоугольник $(0,0) - (n,m)$). Четыре стороны этого прямоугольника являются стенами здания (или, другими словами, четырьмя отрезками стен, которые гарантированно существуют).

Обратите внимание, что система координат в этой задаче отличается от обычной декартовой системы: $(0,0)$ — это левый верхний угол, а $(n,m)$ — правый нижний. $(i,j)$ обозначает вершину в $(i+1)$-й строке и $(j+1)$-м столбце, а не вершину с абсциссой $i$ и ординатой $j$.

Каждый отрезок стены (непроходимая часть) — это отрезок между $(i,j)$ и $(i',j')$, обозначаемый как стена $(i,j) - (i',j')$, где $|i-i'| + |j-j'| = 1$, $i, i' \in [0,n]$ — целые числа, а $j, j' \in [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 \in [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$ строках содержатся операции, формат которых описан выше.

Выходные данные

Для каждого запроса выведите длину пути, который пройдет Фалло, следуя описанному методу, чтобы найти Лисе. Если Фалло не может найти Лисе, следуя описанному методу, выведите $-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

Примечание 1

На рисунке выше показан маршрут Фалло для первого запроса из примера. Во время движения левая рука Фалло должна постоянно касаться стены.

Ограничения

Для $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$.