Diamonds - Problem

A geological survey has produced a map showing diamonds buried deep underground, as illustrated below.

The bold dots in the figure mark the locations of diamonds. We now want to excavate the ground to mine them.

The excavation region must always be a square whose two diagonals are parallel to the coordinate axes.

We will call this a D-square.

With the available budget and excavation technology, we can excavate a D-square region with diagonal length $K$ only once.

Therefore, we want the chosen D-square excavation region to contain as many diamonds as possible.

Let the bottom-left corner of the map be the origin $(0,0)$.

Each diamond is located at integer coordinates.

Every vertex of the D-square must have integer coordinates,

and its center, the intersection of the two diagonals, must lie on the map, including its boundary.

A diamond on an edge of the D-square is also considered to be inside it.

For example, in the figure below with $K=4$, the left D-square contains 5 diamonds and the right D-square contains 3 diamonds.

Write a program that, given the geological survey map, finds a D-square containing the greatest number of diamonds.

The first line contains four integers $N$, $M$, $T$, and $K$, separated by spaces.

$N$ is the width of the map and $M$ is its height ($1\le N,M\le1{,}000{,}000$).

$T$ is the number of diamonds, and $K$ is the size of the D-square (its diagonal length).

$T$ is an integer from $1$ to $100$, and $K$ is an even integer from $2$ to $10{,}000{,}000$.

Each of the next $T$ lines contains two integers $A$ and $B$, separated by a space.

Here, $(A,B)$ is the location of a diamond ($0\le A\le N$, $0\le B\le M$).

All diamond coordinates in the input are distinct.

On the first line, output two integers $X$ and $Y$, separated by a space, representing the center $(X,Y)$ of the D-square.

On the second line, output the number of diamonds contained in this D-square.

If there are several answers, output any one of them.

5 4
5

QOJ.ac