Bảng số 2

Cho bảng số \(A\) và \(B\) có cùng kích thước \(n \times n\), các hàng đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột đánh số từ \(1\) đến \(n\) từ trái sang phải. Cả hai bảng cùng thỏa mãn điều kiện: mỗi phần tử của bảng chỉ nhận một trong ba loại giá trị \(1,-1,0\), đồng thời trên mỗi một hàng cũng như mỗi một cột của bảng luôn có đúng một số \(1\) và một số \(-1\). Xét hai loại phép biến đổi:

• \(1\)) Tráo đổi chỗ hai hàng của bảng \(A\).
• \(2\)) Tráo đổi chỗ hai cột của bảng \(A\).

Yêu cầu: Hãy tìm cách biến đổi bảng \(A\) để nhận được bảng \(B\) với số phép biến đổi không quá \(10^{6}\).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• \(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ố \(B\), nếu có ghi số nguyên \(k\) là số phép biến đổi.
• \(k\) dòng sau, mỗi dòng chứa ba số nguyên \(t, x, y\) có ý nghĩa, nếu \(t=1\) tức là đổi chỗ hai hàng \(x\) và hàng \(y\), nếu \(t=2\) tức là đổi chỗ hai cột \(x\) và cột \(y\).

Example

2
1 -1
-1 1
-1 1
1 -1

1
2 1 2

Scoring

• Có \(40 \%\) số test của bài có \(n \leq 5\).
• Có \(30 \%\) số test khác của bài có \(n \leq 10\).
• Có \(30 \%\) số test còn lại của bài có \(n \leq 100\).