Matrix#400

Matrix

2 secondes
1 024 mégaoctets
Very hard

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:

Input

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.

Output

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).

Examples

Example 1

Loading
Loading

Scoring

  1. ( points) n,m \le 20;

  2. ( points) n,m \le 100;

  3. ( points) a_{i,j} \le 1;

  4. ( points) n,m \le 1\,000;

  5. ( points) no additional restrictions.