Problem D. Depression

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′ = xW… x+W, y′ = yW… 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.041s 0.008s 15