Faro is a girl who is afraid of the dark.

It is evening, and the academic conference Faro attended has long since ended. Lise has finished her classes and come to pick Faro up to return to the train station.

However, the power in the teaching building suddenly went out, and Faro was plunged into total darkness.

Fortunately, Lise has already arrived on the same floor of the teaching building.

Due to the overly complex structure of the building, they can no longer remember its exact layout. The teaching building at Lise's school has a very orderly structure on each floor.

Formally, the floor plan of the teaching building can be drawn on a 2D plane within a sub-rectangle with the top-left vertex at $(0,0)$ and the bottom-right vertex at $(n,m)$ (denoted as the rectangle $(0,0) - (n,m)$). The four sides of this sub-rectangle are the walls of the building (or, in other words, four segments known to exist).

Note that the coordinate system in this problem differs from a standard Cartesian coordinate system: $(0,0)$ is the top-left vertex and $(n,m)$ is the bottom-right vertex. $(i,j)$ denotes the vertex in the $(i+1)$-th row and $(j+1)$-th column, rather than a vertex with horizontal coordinate $i$ and vertical coordinate $j$.

Each wall (an impassable part) is a line segment between endpoints $(i,j)$ and $(i',j')$, denoted as the wall $(i,j) - (i',j')$, where $|i-i'| + |j-j'| = 1$, $i, i' \in [0,n]$, and $j, j' \in [0,m]$ (whenever we use the notation $(i,j) - (i',j')$ hereafter, we guarantee that all these conditions are satisfied).

Faro knows that for this type of structure, there is a way she might find Lise: Faro places her left hand on a wall, keeps her arm perpendicular to the wall surface, and walks forward in this state, maintaining contact with the wall even when turning. By following this method, she can traverse a full cycle and potentially meet Lise.

You are given the initial structure of the floor, followed by $q$ requests.

• Operation 1: Input format $1\ x_0\ y_0\ x_1\ y_1$: Faro requests to add a wall $(x_0, y_0) - (x_1, y_1)$ to the current structure. It is guaranteed that this wall does not currently exist and is not one of the four boundary walls of the $(0,0) - (n,m)$ rectangle.
• Operation 2: Input format $2\ x_0\ y_0\ x_1\ y_1$: Faro requests to remove the wall $(x_0, y_0) - (x_1, y_1)$ from the current structure. It is guaranteed that this wall currently exists and is not one of the four boundary walls of the $(0,0) - (n,m)$ rectangle.
• Operation 3: Input format $3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1$: Faro is currently at the midpoint of the wall $(x_0, y_0) - (x_1, y_1)$, which is $(\frac{x_0+x_1}{2}, \frac{y_0+y_1}{2})$. $d_0$ is an integer in $[0,1]$ describing which side of the wall Faro is on; $d_0 = 0$ means Faro is to the left/above the wall, and $d_0 = 1$ means she is to the right/below. Lise is currently at the midpoint of the wall $(x_2, y_2) - (x_3, y_3)$, which is $(\frac{x_2+x_3}{2}, \frac{y_2+y_3}{2})$. $d_1$ follows the same format as $d_0$. It is guaranteed that the walls $(x_0, y_0) - (x_1, y_1)$ and $(x_2, y_2) - (x_3, y_3)$ exist, and that both Faro and Lise are located inside the $(0,0) - (n,m)$ rectangle. Calculate the total distance Faro must travel to find Lise using the method described (the length of a full wall segment $(i,j) - (i',j')$ is $1$, and the length of a half-segment, since the start and end points are at wall midpoints, is $\frac{1}{2}$).

Input

The input consists of $2n+q$ lines.

The first line contains three integers $n, m, q$, as defined in the problem.

The next $n$ lines each contain $m-1$ integers in $[0,1]$. The integer in the $i$-th row and $j$-th column is $1$ if there is a wall between $(i,j)$ and $(i-1,j)$, and $0$ otherwise.

The next $n-1$ lines each contain $m$ integers in $[0,1]$. The integer in the $i$-th row and $j$-th column is $1$ if there is a wall between $(i,j)$ and $(i,j-1)$, and $0$ otherwise.

The next $q$ lines each contain an operation, formatted as described in the problem.

Output

For each query, output the total distance Faro must travel to find Lise using the described method. If Faro cannot find Lise using this method, output $-1$.

Examples

Input 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

Output 1

11
16

Note 1

The image above shows Faro's path for the first query in the sample input; during the walk, Faro's left hand must remain in contact with the wall.

Subtasks

For $10\%$ of the data, $5 \le n, m \le 50$, $1 \le q \le 2 \times 10^3$.

For another $30\%$ of the data, there are no type 1 operations.

For another $30\%$ of the data, it is guaranteed that at any time, if Faro and Lise are standing at any valid position as defined in the input format, Faro will always be able to meet Lise.

For $100\%$ of the data, $5 \le n, m \le 500$, $1 \le q \le 2 \times 10^5$.