Coffee Shops

A neighborhood has many coffee shops. The neighborhood is a square grid: every street runs north-south or east-west, so the intersections form lattice points.

The distance between two intersections $(a, b)$ and $(c, d)$ is the Manhattan distance $|a - c| + |b - d|$, which equals the number of blocks you must walk to go from one to the other.

Given the positions of all coffee shops and a walking limit of $m$ blocks, write a program that finds the intersection from which the number of coffee shops within $m$ blocks is as large as possible. A candidate intersection is any lattice point inside the city, i.e. an $(x, y)$ with $1 \le x \le dx$ and $1 \le y \le dy$.

The input consists of several test cases. Each test case describes one city.

The first line of each test case contains four integers $dx$, $dy$, $n$, and $q$. The city has size $dx \times dy$ ($1 \le dx, dy \le 1000$), it contains $n$ coffee shops ($0 \le n \le 5 \cdot 10^5$), and there are $q$ queries ($1 \le q \le 20$).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i \le dx$, $1 \le y_i \le dy$), the position of the $i$-th coffee shop. At most one coffee shop sits at any intersection.

Each of the next $q$ lines contains one integer $m$ ($0 \le m \le 10^6$), the maximum number of blocks that may be walked.

The last line of the input contains four zeros, which marks the end of the input.

For each test case, first print the test case number in the form Case k: (where $k$ starts at $1$). Then, for each query, print one line: for that query's $m$, print the maximum number of coffee shops that lie within $m$ blocks of some intersection, followed by the position of an intersection that achieves that maximum, in the form count (x,y).

If several intersections achieve the maximum, print the southernmost one (the smallest $y$); if there is still a tie, print the westernmost one (the smallest $x$).