Bài 1. Mê cung

Một mê cung được biểu diễn bằng một bảng vuông \(A\) kích thước \(n \times n\) ô, các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải, ô nằm giao giữa hàng \(i\) và cột \(j\) được gọi là ô \((i, j)\). Một số ô của bảng có chướng ngại vật và được đánh dấu là \(1\), những ô còn lại là các ô trống và được đánh dấu \(0\). Một robot chỉ di chuyển trong bảng và có thể đi từ ô trống này sang ô trống khác lân cận kề cạnh. Một đường đi của robot giữa hai ô trống là một dãy các ô lân cận từ ô này tới ô kia và không có ô nào đi qua quá một lần, độ dài của đường đi được tính bằng số lượng ô mà robot đi qua. Bảng \(A\) là mê cung nên giữa hai ô trống bất kỳ của bảng có đúng một đường đi giữa chúng.

Hãy xử lí \(q\) thao tác, mỗi thao tác thuộc một trong hai dạng sau:

• Thao tác dạng: 1 u v, thao tác này sẽ thực hiện đặt chướng ngại vật vào ô \((u, v)\). Chú ý rằng, sau khi thực hiện thao tác loại này, bảng \(A\) có thể không còn là mê cung nữa;
• Thao tác dạng: 2 u v x y, thao tác này cần tính độ dài đường đi từ ô \((u, v)\) đến ô \((x, y)\). Nếu không tồn tại đường đi đưa ra -1.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\);
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa xâu \(n\) ký tự {0, 1} mô tả hàng thứ \(i\) của \(A\);
• Dòng thứ \(j\) trong \(q\) dòng tiếp theo mô tả thao tác thứ \(j\).

Output

• Gồm một số dòng tương ứng là các câu trả lời cho thao tác tìm độ dài đường đi giữa hai ô.

Example

3 2
000
110
000
2 1 1 3 1
1 2 3
2 1 1 3 1

7
-1

Subtask

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\); \(q \le 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 1000\); \(q \le 10^5\) và chỉ có thao tác loại \(2\);
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 1000\); \(q \le 10^5\).