Faro to dziewczyna, która boi się ciemności.

Zapadł wieczór, a konferencja naukowa, w której uczestniczyła Faro, już dawno się zakończyła. Lise również skończyła zajęcia i przyszła odebrać Faro, aby wrócić razem na stację kolejową.

Nagle w budynku dydaktycznym wyłączono prąd i Faro pogrążyła się w całkowitej ciemności.

Na szczęście Lise dotarła już na to samo piętro budynku.

Jednak ze względu na zbyt skomplikowaną strukturę budynku, nie pamiętają one już jego dokładnego układu. Struktura każdego piętra w szkole Lise jest bardzo regularna.

Formalnie rzecz biorąc, plan piętra budynku można narysować na płaszczyźnie dwuwymiarowej wewnątrz prostokąta o lewym górnym wierzchołku $(0,0)$ i prawym dolnym wierzchołku $(n,m)$ (oznaczanego jako prostokąt $(0,0) - (n,m)$). Cztery boki tego prostokąta stanowią ściany budynku (lub cztery odcinki ścian, o których wiadomo, że na pewno istnieją).

Uwaga: układ współrzędnych w tym zadaniu różni się od standardowego układu kartezjańskiego. $(0,0)$ to lewy górny wierzchołek, a $(n,m)$ to prawy dolny wierzchołek. $(i,j)$ oznacza wierzchołek w $(i+1)$-szym wierszu i $(j+1)$-szej kolumnie, a nie wierzchołek o współrzędnych poziomych $i$ i pionowych $j$.

Każdy odcinek ściany (część nieprzejezdna) to odcinek łączący punkty $(i,j)$ oraz $(i',j')$, oznaczany jako ściana $(i,j) - (i',j')$, gdzie $|i-i'| + |j-j'| = 1$, przy czym $i, i'$ są liczbami całkowitymi z przedziału $[0,n]$, a $j, j'$ są liczbami całkowitymi z przedziału $[0,m]$ (ilekroć używamy zapisu $(i,j) - (i',j')$, gwarantujemy spełnienie wszystkich powyższych warunków).

Faro wie, że w takiej strukturze istnieje sposób, który może pozwolić jej odnaleźć Lise: Faro kładzie lewą rękę na ścianie, trzymając ramię prostopadle do powierzchni ściany, i porusza się przed siebie, utrzymując ten stan. Nawet na zakrętach Faro utrzymuje lewą rękę w kontakcie ze ścianą. Stosując tę metodę, może ona obejść cały obszar i potencjalnie spotkać Lise.

Na początku otrzymasz początkową strukturę piętra, a następnie $q$ zapytań.

• Operacja $1$: format $1\ x_0\ y_0\ x_1\ y_1$: Faro prosi o dodanie ściany $(x_0, y_0) - (x_1, y_1)$ do obecnej struktury. Gwarantuje się, że ściana ta wcześniej nie istniała i nie znajduje się na żadnym z czterech boków prostokąta $(0, 0)-(n, m)$.
• Operacja $2$: format $2\ x_0\ y_0\ x_1\ y_1$: Faro prosi o usunięcie ściany $(x_0, y_0) - (x_1, y_1)$ z obecnej struktury. Gwarantuje się, że ściana ta wcześniej istniała i nie znajduje się na żadnym z czterech boków prostokąta $(0, 0)-(n, m)$.
• Operacja $3$: format $3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1$: Faro znajduje się obecnie w punkcie środkowym ściany $(x_0, y_0) - (x_1, y_1)$, czyli $(\frac{x_0+x_1}{2}, \frac{y_0+y_1}{2})$. $d_0$ jest liczbą całkowitą z przedziału $[0,1]$ opisującą, po której stronie ściany znajduje się Faro ($d_0 = 0$ oznacza lewą/górną stronę ściany, $d_0 = 1$ oznacza prawą/dolną stronę). Lise znajduje się obecnie w punkcie środkowym ściany $(x_2, y_2) - (x_3, y_3)$, czyli $(\frac{x_2+x_3}{2}, \frac{y_2+y_3}{2})$. $d_1$ ma ten sam format co $d_0$. Gwarantuje się, że ściany $(x_0, y_0) - (x_1, y_1)$ oraz $(x_2, y_2) - (x_3, y_3)$ istnieją, a pozycje Faro i Lise znajdują się wewnątrz prostokąta $(0,0) - (n,m)$. Oblicz, jaki dystans musi pokonać Faro, stosując opisaną metodę, aby odnaleźć Lise (długość ściany $(i,j) - (i',j')$ wynosi $1$, długość połowy ściany wynosi $\frac{1}{2}$).

Wejście

Wejście zawiera łącznie $2n+q$ wierszy.

Pierwszy wiersz zawiera trzy liczby całkowite $n, m, q$, zgodnie z opisem w treści zadania.

Kolejne $n$ wierszy zawiera po $m-1$ liczb całkowitych z przedziału $[0,1]$. Liczba w $i$-tym wierszu i $j$-tej kolumnie równa $1$ oznacza, że istnieje ściana $(i,j) - (i-1,j)$, a $0$ oznacza jej brak.

Kolejne $n-1$ wierszy zawiera po $m$ liczb całkowitych z przedziału $[0,1]$. Liczba w $i$-tym wierszu i $j$-tej kolumnie równa $1$ oznacza, że istnieje ściana $(i,j) - (i,j-1)$, a $0$ oznacza jej brak.

Kolejne $q$ wierszy zawiera po jednej operacji w formacie opisanym w treści zadania.

Wyjście

Dla każdego zapytania wypisz dystans, jaki musi pokonać Faro, aby odnaleźć Lise zgodnie z opisaną metodą. Jeśli Faro nie jest w stanie odnaleźć Lise, wypisz $\mathbf{-1}$.

Przykład

Przykład 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

Wyjście 1

11
16

Uwagi

Powyższy rysunek przedstawia trasę Faro dla pierwszego zapytania z przykładu. Podczas poruszania się lewa ręka Faro musi cały czas dotykać ściany.

Podzadania

Dla $10\%$ danych: $5\le n, m\le 50, 1\le q\le 2\times 10^3$.

Dla kolejnych $30\%$ danych: brak operacji typu $1$.

Dla kolejnych $30\%$ danych: gwarantuje się, że w dowolnym momencie, jeśli Faro i Lise stoją w dowolnych poprawnych pozycjach, Faro zawsze może spotkać Lise.

Dla $100\%$ danych: $5\le n, m\le 500, 1\le q\le 2\times 10^5$.