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.