Faro es una chica que le teme a la oscuridad.

Ha caído la noche y la conferencia académica a la que asistía Faro ya ha terminado. Lise también ha terminado sus clases y ha venido a recoger a Faro para llevarla a la estación de tren.

Sin embargo, la electricidad en el edificio de enseñanza se cortó repentinamente y Faro quedó sumida en la oscuridad total.

Afortunadamente, Lise ya ha llegado al mismo piso del edificio.

No obstante, debido a que la estructura del edificio es demasiado compleja, ya no recuerdan la distribución exacta del mismo. La estructura de cada piso del edificio de la escuela de Lise es muy ordenada.

Formalmente, la estructura plana de un piso del edificio puede dibujarse en un plano bidimensional dentro de un subrectángulo con el vértice superior izquierdo en $(0,0)$ y el vértice inferior derecho en $(n,m)$ (denotado como el rectángulo $(0,0) - (n,m)$). Los cuatro lados de este subrectángulo son las paredes del edificio (o, en otras palabras, cuatro segmentos de pared que se sabe que existen con certeza).

Tenga en cuenta que el sistema de coordenadas en este problema es diferente al sistema de coordenadas cartesianas habitual: $(0,0)$ es el vértice superior izquierdo y $(n,m)$ es el vértice inferior derecho. $(i,j)$ representa el vértice en la fila $i+1$ y la columna $j+1$, no el vértice con coordenada horizontal $i$ y coordenada vertical $j$.

Cada segmento de pared (una parte por la que no se puede pasar) es un segmento de línea con extremos en $(i,j)$ y $(i',j')$, denotado como la pared $(i,j) - (i',j')$, donde $|i-i'| + |j-j'| = 1$, $i, i'$ son enteros en $[0,n]$ y $j, j'$ son enteros en $[0,m]$ (siempre que utilicemos la notación $(i,j) - (i',j')$ en adelante, garantizamos que se cumplen todas las condiciones anteriores).

Faro sabe que, para esta estructura, existe una forma en la que podría encontrar a Lise: Faro coloca su mano izquierda sobre la pared, manteniendo su brazo perpendicular a la superficie de la pared, y camina hacia adelante en este estado, manteniendo su mano izquierda sobre la pared incluso al girar. Siguiendo este método, puede recorrer un circuito completo y posiblemente encontrarse con Lise.

Al principio, se le proporcionará la estructura inicial (de este piso) y, posteriormente, se le darán $q$ solicitudes.

• Operación $1$: El formato de lectura es $1\ x_0\ y_0\ x_1\ y_1$: Faro solicita añadir un segmento de pared $(x_0, y_0) - (x_1, y_1)$ a la estructura actual. Se garantiza que este segmento de pared no existía previamente y que no se encuentra en los cuatro lados del subrectángulo $(0, 0)-(n, m)$.
• Operación $2$: El formato de lectura es $2\ x_0\ y_0\ x_1\ y_1$: Faro solicita eliminar un segmento de pared $(x_0,y_0) - (x_1,y_1)$ de la estructura actual. Se garantiza que este segmento de pared existía previamente y que no se encuentra en los cuatro lados del subrectángulo $(0,0) - (n,m)$.
• Operación $3$: El formato de lectura es $3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1$: Faro se encuentra actualmente en el punto medio de la pared $(x_0,y_0) - (x_1,y_1)$, es decir, en $(\frac{x_0+x_1}{2},\frac{y_0 + y_1}{2})$. $d_0$ es un entero en $[0,1]$ que describe en qué lado de la pared se encuentra Faro; $d_0 = 0$ significa que Faro está a la izquierda/arriba de la pared, y $d_0 = 1$ significa que está a la derecha/abajo. Lise se encuentra actualmente en el punto medio de la pared $(x_2,y_2) - (x_3,y_3)$, es decir, en $(\frac{x_2+x_3}{2},\frac{y_2+y_3}{2})$. El formato de $d_1$ es el mismo que el de $d_0$. Se garantiza que los segmentos de pared $(x_0,y_0) - (x_1,y_1)$ y $(x_2,y_2) - (x_3,y_3)$ existen, y que las posiciones de Faro y Lise se encuentran dentro del subrectángulo $(0,0) - (n,m)$. Calcule qué distancia debe recorrer Faro siguiendo el método descrito en el problema para encontrar a Lise (la longitud del segmento de pared $(i,j) - (i',j')$ es $1$, y la longitud de media pared (dado que tanto el punto de inicio como el de fin están en los puntos medios de las paredes) es $\frac{1}{2}$).

Entrada

La entrada consta de $2n+q$ líneas.

La primera línea contiene tres enteros $n, m, q$, con el significado descrito en el problema.

Las siguientes $n$ líneas contienen, cada una, $m-1$ enteros en $[0,1]$. El entero en la fila $i$ y columna $j$ es $1$ si existe una pared en $(i,j) - (i-1,j)$, y $0$ si no existe.

Las siguientes $n-1$ líneas contienen, cada una, $m$ enteros en $[0,1]$. El entero en la fila $i$ y columna $j$ es $1$ si existe una pared en $(i,j) - (i,j-1)$, y $0$ si no existe.

Las siguientes $q$ líneas contienen, cada una, una operación con el formato descrito en el problema.

Salida

Para cada consulta, imprima la distancia que Faro debe recorrer siguiendo el método descrito para encontrar a Lise. Si Faro no puede encontrar a Lise siguiendo el método descrito, imprima $\mathbf{-1}$.

Ejemplos

Entrada 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

Salida 1

11
16

Nota 1

La imagen anterior muestra el plan de caminata de Faro para la primera consulta de la entrada de ejemplo; durante la caminata, la mano izquierda de Faro debe permanecer pegada a la pared.

Subtareas

Para el $10\%$ de los datos, $5\le n, m\le 50, 1\le q\le 2\times 10^3$.

Para otro $30\%$ de los datos, no hay operaciones de tipo $1$.

Para otro $30\%$ de los datos, se garantiza que en cualquier momento, si Faro y Lise se encuentran en posiciones válidas según el formato de entrada, Faro siempre podrá encontrarse con Lise.

Para el $100\%$ de los datos, $5\le n, m\le 500, 1\le q\le 2\times 10^5$.