## Problem D. Depression ≡

• problems
 Author: A. Klenin Time limit: 2 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

The height map of some square country is represented with a matrix of N × N integers. Each integer reflects average height of the corresponding area. We will denote the height value at location (x, y) as h[x, y].

A location (x, y) is named depression if for all x′ = x − W… x + W, y′ = y − W… y + W location (x′, y′) is also inside of the map and h[x, y] ≤ h[x′,y′].

Your program must find coordinates of all depressions of the given height map.

### Input file format

Input file contains integers N W, followed by N × N integers — location heights, row-by-row.

### Output file format

Output file must contain an integer M — number of possible depressions, followed by M pairs of integers xi yi, where xi — the column of the i-th depression, yi — the row of the i-th depression. Numbering starts from 1.

Depressions must be ordered by y, then by x.

### Constraints

3 ≤ N ≤ 500

1 ≤ W

2 × W < N

1 ≤ h[x, y] ≤ 1000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 1
2 2 2 3 4
2 5 2 1 4
2 2 2 3 4
3 3 3 1 4
4 4 4 4 4

3
4 2
2 3
4 4

2
5 2
3 3 3 3 1
3 4 4 3 1
3 4 4 3 1
3 3 3 3 1
1 1 1 1 1
0

0.080s 0.010s 13