法珞（ファロ）は暗闇を怖がる女の子です。

夕方になり、法珞が参加していた学会はすでに終わりました。黎瑟（リーゼ）も授業を終えて、法珞を駅まで迎えに来ました。

しかし、校舎で突然停電が発生し、法珞は真っ暗闇の中に閉じ込められてしまいました。

幸い、黎瑟はすでに同じ階に到着しています。

校舎の構造が複雑すぎるため、二人は校舎の正確な構造を思い出せません。黎瑟の学校の校舎は、各階の構造が非常に整然としています。

形式的に述べると、校舎の1階の平面構造は、左上の頂点を $(0,0)$、右下の頂点を $(n,m)$ とする長方形（$(0,0) - (n,m)$ の長方形と記す）の中に描くことができます。この長方形の4辺は校舎の外壁（あるいは必ず存在することが分かっている4つの壁）です。

本問題における座標系は通常の平面直角座標系とは異なり、$(0,0)$ が左上の頂点、$(n,m)$ が右下の頂点であることに注意してください。$(i,j)$ は横座標が $i$、縦座標が $j$ である点ではなく、第 $i+1$ 行第 $j+1$ 列の頂点を表します。

各壁（通行不可能な部分）は、端点が $(i,j)$ と $(i',j')$ である線分であり、$(i,j) - (i',j')$ の壁と記します。ここで $|i-i'| + |j-j'| = 1$ であり、$i, i'$ は $[0,n]$ の整数、$j, j'$ は $[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)$ の長方形の4辺上にはないことが保証されます。
• 操作 $2$：$2\ x_0\ y_0\ x_1\ y_1$ という形式で入力されます。現在構造から $(x_0, y_0) - (x_1, y_1)$ の壁を削除します。この壁は存在し、かつ $(0, 0) - (n, m)$ の長方形の4辺上にはないことが保証されます。
• 操作 $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$ は $[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$ 行です。

1行目に3つの整数 $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$ 行には、各操作が与えられます。

出力形式

各クエリに対し、法珞が指定された方法で黎瑟を見つけるまでに移動する距離を出力してください。もし指定された方法で黎瑟を見つけることができない場合は $\mathbf{-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

注記

上図はサンプル入力における最初のクエリの法珞の移動経路です。移動中、法珞の左手は常に壁に触れている必要があります。

サブタスク

• $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$