You are given a matrix of size n \times m consisting of elements a_{i,j}.
We call a triangle on the matrix of size starting at point a set of points that can be reached from in no more than steps going either up or right.
You are asked to find for each (k \le x \le n, 1 \le y \le m-k+1) the following values:
The maximal value in the triangle of size starting at point ;
The number of occurrences of the maximal value in that triangle.
The first line contains three integers , , and (1 \le n,m \le 2\,000, 1 \le k \le \min(n,m)) — dimensions of the matrix and the size of the triangle.
The following lines contain integers a_{i,j} (0 \le a_{i,j} \le 10^6) — description of the matrix.
Print two matrices of size (n-k+1)\times(m-k+1).
The first matrix in position should contain the maximal value of a triangle of size starting at (i+k-1;j).
The second matrix in position should contain the number of occurrences of the maximal value in the triangle of size starting at (i+k-1;j).
Example 1
( points) n,m \le 20;
( points) n,m \le 100;
( points) a_{i,j} \le 1;
( points) n,m \le 1\,000;
( points) no additional restrictions.