Faro est une jeune fille qui a peur du noir.

La soirée est tombée et la conférence académique à laquelle Faro assistait est terminée depuis longtemps. Lise est venue la chercher après ses cours pour rentrer à la gare.

Cependant, une coupure de courant a soudainement plongé le bâtiment d'enseignement dans l'obscurité totale, laissant Faro dans le noir complet.

Heureusement, Lise est déjà arrivée au même étage du bâtiment.

Mais en raison de la complexité de la structure du bâtiment, elles ne se souviennent plus de sa configuration exacte. La structure de chaque étage du bâtiment de l'école de Lise est très régulière.

Formellement, la structure plane d'un étage peut être représentée dans un plan bidimensionnel à l'intérieur d'un sous-rectangle ayant pour sommet supérieur gauche $(0,0)$ et pour sommet inférieur droit $(n,m)$ (noté rectangle $(0,0) - (n,m)$). Les quatre côtés de ce rectangle constituent les murs du bâtiment (ou, en d'autres termes, quatre segments de mur dont l'existence est garantie).

Veuillez noter que le système de coordonnées utilisé ici diffère du système cartésien habituel : $(0,0)$ est le sommet supérieur gauche et $(n,m)$ est le sommet inférieur droit. $(i,j)$ désigne le sommet situé à la $(i+1)$-ième ligne et à la $(j+1)$-ième colonne, et non un sommet de coordonnées $(x,y)$ où $x=i$ et $y=j$.

Chaque segment de mur (une partie infranchissable) est un segment reliant les points $(i,j)$ et $(i',j')$, noté mur $(i,j) - (i',j')$, où $|i-i'| + |j-j'| = 1$, $i, i' \in [0,n]$ sont des entiers, et $j, j' \in [0,m]$ sont des entiers (chaque fois que nous utilisons la notation $(i,j) - (i',j')$, nous garantissons que toutes ces conditions sont remplies).

Faro sait qu'avec cette structure, il existe un moyen de retrouver Lise : Faro pose sa main gauche sur le mur, garde son bras perpendiculaire à la surface du mur, et avance tout en maintenant sa main gauche en contact permanent avec le mur, même dans les virages. En suivant cette méthode, elle peut parcourir un cycle complet et potentiellement rencontrer Lise.

Faro vous donne la structure initiale (de cet étage), suivie de $q$ requêtes.

• Opération $1$ : Format $1\ x_0\ y_0\ x_1\ y_1$ : Faro demande d'ajouter un mur $(x_0, y_0) - (x_1, y_1)$ à la structure actuelle. Il est garanti que ce mur n'existait pas auparavant et qu'il ne fait pas partie des quatre côtés du rectangle $(0, 0)-(n, m)$.
• Opération $2$ : Format $2\ x_0\ y_0\ x_1\ y_1$ : Faro demande de supprimer un mur $(x_0,y_0) - (x_1,y_1)$ de la structure actuelle. Il est garanti que ce mur existait et qu'il ne fait pas partie des quatre côtés du rectangle $(0,0) - (n,m)$.
• Opération $3$ : Format $3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1$ : Faro se trouve actuellement au milieu du mur $(x_0,y_0) - (x_1,y_1)$, soit au point $(\frac{x_0+x_1}{2},\frac{y_0 + y_1}{2})$. $d_0$ est un entier dans $[0,1]$ décrivant de quel côté du mur se trouve Faro : $d_0 = 0$ signifie que Faro est à gauche/au-dessus du mur, et $d_0 = 1$ signifie qu'elle est à droite/en dessous. Lise se trouve actuellement au milieu du mur $(x_2,y_2) - (x_3,y_3)$, soit au point $(\frac{x_2+x_3}{2},\frac{y_2+y_3}{2})$. Le format de $d_1$ est identique à celui de $d_0$. Il est garanti que les murs $(x_0,y_0) - (x_1,y_1)$ et $(x_2,y_2) - (x_3,y_3)$ existent, et que les positions de Faro et Lise se trouvent à l'intérieur du rectangle $(0,0) - (n,m)$. Calculez la distance que Faro doit parcourir en suivant la méthode décrite pour trouver Lise (la longueur d'un mur $(i,j) - (i',j')$ est $1$, et la longueur d'un demi-mur, puisque le point de départ et d'arrivée sont au milieu d'un mur, est $\frac{1}{2}$).

Entrée

L'entrée contient $2n+q$ lignes.

La première ligne contient trois entiers $n, m, q$, dont la signification est donnée dans l'énoncé.

Les $n$ lignes suivantes contiennent chacune $m-1$ entiers valant $0$ ou $1$. L'entier à la $i$-ième ligne et $j$-ième colonne vaut $1$ si le segment $(i,j) - (i-1,j)$ est un mur, et $0$ sinon.

Les $n-1$ lignes suivantes contiennent chacune $m$ entiers valant $0$ ou $1$. L'entier à la $i$-ième ligne et $j$-ième colonne vaut $1$ si le segment $(i,j) - (i,j-1)$ est un mur, et $0$ sinon.

Les $q$ lignes suivantes contiennent chacune une opération, au format décrit dans l'énoncé.

Sortie

Pour chaque requête, affichez la distance que Faro doit parcourir pour trouver Lise en suivant la méthode décrite. Si Faro ne peut pas trouver Lise en suivant cette méthode, affichez $\mathbf{-1}$.

Exemples

Entrée 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

Sortie 1

11
16

Remarque 1

L'image ci-dessus illustre le chemin parcouru par Faro lors de la première requête de l'exemple. Pendant son déplacement, la main gauche de Faro doit rester en contact avec le mur.

Sous-tâches

Pour $10\%$ des données, $5\le n, m\le 50, 1\le q\le 2\times 10^3$.

Pour $30\%$ des données supplémentaires, il n'y a pas d'opération $1$.

Pour $30\%$ des données supplémentaires, il est garanti qu'à tout moment, si Faro et Lise se trouvent à des positions valides selon le format d'entrée, Faro peut rencontrer Lise.

Pour $100\%$ des données, $5\le n, m\le 500, 1\le q\le 2\times 10^5$.