Cho bảng số \(A\) và \(B\) có cùng 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)\) và chỉ chứa hai loại giá trị \(0\) hoặc \(1\). Xét hai loại phép biến đổi:

1. Tráo đổi chỗ hai cột kề nhau của bảng \(A\), cụ thể: Thao tác \(1\) \(c\) sẽ đổi chỗ cột \(c\) và cột \(c + 1\) cho nhau.
2. Đảo giá trị trên một hàng của bảng \(A\), cụ thể: Thao tác \(2\) \(r\) sẽ đổi giá trị của các ô \((r, k)\) từ \(0\) thành \(1\) hoặc từ \(1\) thành \(0\) (với mọi \(1 \leq k \leq n)\).

*Yêu cầu*: Hãy tìm ít thao tác biến đổi bảng \(A\) để nhận được bảng \(C\) mà bảng \(C\) sai khác với bảng \(B\) không quá một ô.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((1 \leq n \leq 100)\).
• \(n\) dòng sau, mỗi dòng chứa \(n\) số nguyên mô tả bảng \(A\).
• \(n\) dòng sau, mỗi dòng chứa \(n\) số nguyên mô tả bảng \(B\).

Output

• Ghi số \(-1\) nếu không tồn tại cách biển đổi bảng \(A\) để nhận được bảng số \(C\) mà bảng \(C\) sai khác với bảng \(B\) không quá một ô.
• Ngược lại ghi số nguyên \(s\) là số thao tác ít nhất cần thực hiện. Tiếp theo là \(s\) dòng sau, mỗi dòng chứa hai số nguyên \(t, x\) có ý nghĩa, nếu \(t = 1\) tức là đổi chỗ hai cột \(x\) và cột \(x + 1\), nếu \(t = 2\) tức là đổi giá trị hàng \(x\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 4\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 20\).
• Subtask \(4\) (\(25\%\) số điểm): không có rằng buộc gì thêm.

Example

2
0 0
0 0
0 1
1 0

-1

3
0 1 0
0 1 0
0 1 0
1 1 1
0 0 1
0 0 1

2
1 2
2 1