Faro là một cô gái sợ bóng tối.

Trời đã về chiều, hội nghị học thuật mà Faro tham dự đã kết thúc từ lâu. Lise cũng đã tan học và đến đón Faro về nhà ga.

Tuy nhiên, tòa nhà giảng đường đột ngột bị mất điện, khiến Faro rơi vào bóng tối bao trùm.

May mắn thay, Lise đã đến cùng tầng với tòa nhà giảng đường.

Nhưng do cấu trúc của tòa nhà quá phức tạp, họ không còn nhớ rõ cấu trúc cụ thể của nó nữa. Cấu trúc mỗi tầng trong tòa nhà của trường Lise rất ngăn nắp.

Xét về mặt hình thức, cấu trúc mặt bằng của một tầng có thể được vẽ trên mặt phẳng tọa độ trong một hình chữ nhật con với đỉnh trên trái là $(0,0)$ và đỉnh dưới phải là $(n,m)$ (ký hiệu là hình chữ nhật $(0,0) - (n,m)$). Bốn cạnh của hình chữ nhật này là các bức tường của tòa nhà (hay nói cách khác, bốn đoạn tường này chắc chắn tồn tại).

Lưu ý rằng hệ tọa độ trong bài toán này khác với hệ tọa độ Descartes thông thường: $(0,0)$ là đỉnh trên trái và $(n,m)$ là đỉnh dưới phải. $(i,j)$ biểu thị đỉnh ở hàng thứ $i+1$ và cột thứ $j+1$, chứ không phải đỉnh có hoành độ $i$ và tung độ $j$.

Mỗi đoạn tường (phần không thể đi qua) là một đoạn thẳng nối hai điểm $(i,j)$ và $(i',j')$, ký hiệu là bức tường $(i,j) - (i',j')$, trong đó $|i-i'| + |j-j'| = 1$, $i, i'$ là các số nguyên trong đoạn $[0,n]$ và $j, j'$ là các số nguyên trong đoạn $[0,m]$ (mỗi khi chúng ta sử dụng ký hiệu $(i,j) - (i',j')$ sau này, chúng ta đều đảm bảo thỏa mãn tất cả các điều kiện trên).

Faro biết rằng với cấu trúc này, có một cách để cô có thể tìm thấy Lise: Faro dùng tay trái chạm vào tường, cánh tay vuông góc với mặt tường, giữ nguyên trạng thái này và đi về phía trước, đồng thời giữ tay trái luôn chạm tường ngay cả khi rẽ. Theo cách này, cô có thể đi hết một vòng và có khả năng gặp Lise.

Faro sẽ cung cấp cho bạn cấu trúc ban đầu (của tầng này), sau đó sẽ có $q$ yêu cầu.

• Thao tác $1$: Đọc định dạng $1\ x_0\ y_0\ x_1\ y_1$: Faro yêu cầu thêm một đoạn tường $(x_0, y_0) - (x_1, y_1)$ vào cấu trúc hiện tại, đảm bảo đoạn tường này chưa tồn tại trước đó và không nằm trên bốn cạnh của hình chữ nhật $(0, 0)-(n, m)$.
• Thao tác $2$: Đọc định dạng $2\ x_0\ y_0\ x_1\ y_1$: Faro yêu cầu xóa một đoạn tường $(x_0,y_0) - (x_1,y_1)$ khỏi cấu trúc hiện tại, đảm bảo đoạn tường này đã tồn tại và không nằm trên bốn cạnh của hình chữ nhật $(0,0) - (n,m)$.
• Thao tác $3$: Đọc định dạng $3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1$: Faro hiện đang ở trung điểm của bức tường $(x_0,y_0) - (x_1,y_1)$ là $(\frac{x0+x1}{2},\frac{y_0 + y_1}{2})$, $d_0$ là một số nguyên trong $[0,1]$ dùng để mô tả phía của bức tường mà Faro đang đứng, $d_0 = 0$ đại diện cho phía trái/trên của bức tường, $d_0 = 1$ đại diện cho phía phải/dưới. Lise hiện đang ở trung điểm của bức tường $(x_2,y_2) - (x_3,y_3)$ là $(\frac{x2+x3}{2},\frac{y_2+y_3}{2})$. Định dạng của $d_1$ giống với $d_0$. Đảm bảo rằng hai đoạn tường $(x_0,y_0) - (x_1,y_1)$ và $(x_2,y_2) - (x_3,y_3)$ tồn tại, và vị trí của cả Faro và Lise đều nằm bên trong hình chữ nhật $(0,0) - (n,m)$. Hãy tính quãng đường Faro phải đi theo phương pháp đã nêu để tìm thấy Lise (độ dài của đoạn tường $(i,j) - (i',j')$ là $1$, độ dài của nửa đoạn tường (do điểm bắt đầu và kết thúc đều nằm ở trung điểm của tường) là $\frac{1}{2}$).

Dữ liệu vào

Dữ liệu gồm $2n+q$ dòng.

Dòng đầu tiên chứa ba số nguyên $n,m,q$ với ý nghĩa như đã nêu.

$n$ dòng tiếp theo, mỗi dòng chứa $m-1$ số nguyên trong $[0,1]$, số ở hàng $i$ cột $j$ bằng $1$ nghĩa là đoạn $(i,j) - (i-1,j)$ có tường, bằng $0$ nghĩa là không có tường.

$n-1$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên trong $[0,1]$, số ở hàng $i$ cột $j$ bằng $1$ nghĩa là đoạn $(i,j) - (i,j-1)$ có tường, bằng $0$ nghĩa là không có tường.

$q$ dòng tiếp theo, mỗi dòng là một thao tác với định dạng như đã nêu.

Dữ liệu ra

Với mỗi truy vấn, in ra quãng đường Faro phải đi theo phương pháp đã nêu để tìm thấy Lise. Nếu Faro không thể tìm thấy Lise theo phương pháp đã nêu, hãy in ra $\mathbf{-1}$.

Ví dụ

Ví dụ 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

Kết quả 1

11
16

Ghi chú

Hình trên minh họa phương án di chuyển của Faro trong truy vấn đầu tiên của ví dụ, trong quá trình di chuyển, tay trái của Faro phải luôn chạm vào tường.

Nhiệm vụ con

Với $10\%$ dữ liệu, $5\le n, m\le 50, 1\le q\le 2\times 10^3$.

Với $30\%$ dữ liệu tiếp theo, không có thao tác $1$.

Với $30\%$ dữ liệu tiếp theo, đảm bảo rằng tại bất kỳ thời điểm nào, nếu Faro và Lise đứng ở các vị trí hợp lệ theo định dạng đầu vào, Faro luôn có thể gặp Lise.

Với $100\%$ dữ liệu, $5\le n, m\le 500, 1\le q\le 2\times 10^5$.