Giàn đèn

Một giàn đèn trang trí kích thước $m\times n$, các hàng đánh số từ $1$ đến $m$ từ trên xuống dưới, các cột đánh số từ $1$ đến $n$ từ trái sang phải. Ô nằm giao giữa hàng $r$ và cột $c$ gọi là ô $(r,c)$. Trên mỗi ô có một bóng đèn, mỗi bóng đèn có ba trạng thái: hoặc tắt, hoặc bật sáng màu xanh, hoặc bật sáng màu đỏ. Có $k$ ô phân biệt $(r_1,c_1),(r_2,c_2),\dots ,(r_k,c_k)$ của giàn đèn, mỗi ô có một công tắc điều khiển. Khi tác động vào công tắc của ô $(r_t,c_t)$ thì những đèn nằm trong các ô thuộc hình chữ nhật có ô trái trên là $(r_t,c_t)$ và ô phải dưới là $(x_t,y_t)$ sẽ đổi trạng thái $(t=1,2,\dots ,k)$. Cụ thể, các đèn nằm trong các ô $(u,v)$ mà $r_t\le u\le x_t$ và $c_t\le v\le y_t$ sẽ thay đổi theo quy tắc: nếu đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái bật sáng màu xanh, nếu đang ở trạng thái bật sáng màu xanh sẽ chuyển sang trạng thái bật sáng màu đỏ, còn nếu đèn đang ở trạng thái bật sáng màu đỏ sẽ chuyển sang trạng thái tắt. Mỗi công tắc có thể tác động nhiều lần.

Yêu cầu: Cho thông tin trạng thái ban đầu các đèn trên giàn và các công tắc. Hãy tìm cách đưa tất cả các đèn về cùng một trạng thái bật sáng màu xanh hoặc bật sáng màu đỏ với số lần tác động là ít nhất.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $m$, $n$, $k$ $(k\le m\times n)$;
• Dòng thứ $i$ trong số $m$ dòng tiếp theo chứa $n$ số nguyên nhận giá trị $0$, $1$ hoặc $2$. Số thứ $j$ $(j=1,2,\dots ,n)$ mô tả trạng thái đèn ở ô $(i,j)$ là tắt, bật sáng màu xanh hoặc bật sáng màu đỏ tương ứng với các giá trị $0$, $1$ hoặc $2$;
• Dòng thứ $t$ trong số $k$ dòng tiếp theo chứa bốn số nguyên dương $r_t,c_t,x_t,y_t$ ($1\le r_t\le x_t\le m$ và $1\le c_t\le y_t\le n$).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra duy nhất một số nguyên là số lần tác động ít nhất để các đèn về cùng một trạng thái sáng màu xanh hoặc sáng màu đỏ, nếu không tồn tại cách tác động thì in ra số $-1$.

Ràng buộc

• $m\times n\le {10}^5$; $1\le k\le m\times n$;
• Các ô $(r_t,c_t)$ đôi một phân biệt; $1\le r_t\le x_t\le m$, $1\le c_t\le y_t\le n$.

Subtasks

• Subtask 1 ($40\%$ số test, $40\%$ số điểm): $m=1$, $n\le 10$;
• Subtask 2 ($40\%$ số test, $40\%$ số điểm): $m\times n\le {10}^3$;
• Subtask 3 ($20\%$ số test, $20\%$ số điểm): $m\times n\le {10}^5$.

Ví dụ