This is an approximate problem.

Dexter has started learning matrix multiplication recently. His teacher gives him a task to perform.

She gives him two N x N matrices, A and B, containing integers. In a single operation he can swap $A_{i,j}$ and $B_{i,j}$, where $1 \le i \le N$ and $1 \le j \le N$.

He is allowed to perform up to K such operations on the matrices A and B in some particular order. After performing these operations, he finds the product of the two matrices, i.e., $C=A*B$. Now, he finds the sum of values at all the cells of C. His target is to maximize the value of this sum.

Suppose he performed $T(0<=T<=K)$ such operations, then he should output the value of T. And then T lines describing each operation in the order he performed them.

Input Format

The first line of input contains two space separated integers N and K, denoting the width of the two square matrices A and B and the number of operations allowed, respectively.

Next N lines contain N integers per line, denoting the values in the matrix A. The $j^{th}$ integer in the $(i+1)^{th}$ line denotes the value $A_{i,j}$.

Next N lines contain N integers per line, denoting the values in the matrix B. The $j^{th}$ integer in the $(i+N+1)^{th}$ line denotes the value $B_{i,j}$.

Output Format

The first line of input contains a single integer, T, the number of operations performed by Dexter. Next T lines contain two space separated integers per line,$i,j$ denoting that $A_{i,j}$ and $B_{i,j}$ had been swapped by Dexter in that operation.

Constraints

$1 \le N \le 100$
$1 \le K \le 50$
5 x $10^5 \le A_{i,j} , B_{i,j} \le 5$ x $10^5$, where $1 \le i \le N$ and $1 \le j \le N$.

Tests

Contest test set contains 50 tests.

Tests 1-5: $1 \le N \le 3, 1 \le K \le 10$

Tests 6-12: $1 \le N \le 3, 1 \le K \le 10$, contain only 0s and 1s.

Tests 13-17: $1 \le N \le 10, 1 \le K \le 50$

Tests 18-24: $1 \le N \le 10, 1 \le K \le 50$, contain only 0s and 1s

Tests 25-39: $70 \le N \le 100, 1 \le K \le 50$,

Tests 40-50: $70 \le N \le 100, 1 \le K \le 50$, contain only 0s and 1s

The solutions will be run on additional 50 tests after the contest ends.