Coffee Central#2285

Coffee Central

15 seconds

256 megabytes

Easy

Is it just a fad, or is it here to stay? You're not sure, but the steadily increasing number of coffee shops opening in your hometown has certainly become quite a draw. Apparently, people have become so addicted to coffee that apartments close to many coffee shops will fetch higher rents.

This has come to the attention of a local real-estate company. They are interested in identifying the most valuable locations in the city in terms of proximity to many coffee shops. You have been given a map of the city with all coffee shops marked. Assuming that the average person is willing to walk only a fixed number of blocks for their morning coffee, you need to find the location from which one can reach the largest number of coffee shops.

As you probably know, your hometown is built on a rectangular grid, with blocks aligned with the north-south and east-west axes. Since walking is only allowed along the streets, the distance between intersections $(a, b)$ and $(c, d)$ is $∣ a - c ∣ + ∣ b - d ∣$ |a - c| + |b - d|.

Input

The input contains several test cases. Each test describes a city. The first line of each test case contains four integers $d x$ , $d y$ , $n$ and $q$ . These specify the grid dimensions $d x \times d y$ dx \times dy ( $1 \leq d x, d y \leq 1000$ 1 \le dx, dy \le 1000), the number of coffee shops $n$ ( $0 \leq n \leq 5 \cdot 1 0^{5}$ 0 \le n \le 5 \cdot 10^5) and the number of queries $q$ ( $1 \leq q \leq 20$ 1 \le q \le 20). Each of the next $n$ lines contains two integers $x_{i}$ x_i and $y_{i}$ y_i ( $1 \leq x_{i} \leq d x$ 1 \le x_i \le dx, $1 \leq y_{i} \leq d y$ 1 \le y_i \le dy), specifying the coordinates of the $i$ -th coffee shop. There is at most one coffee shop per intersection. Each of the next $q$ lines contains a single integer $m$ ( $0 \leq m \leq 1 0^{6}$ 0 \le m \le 10^6), the maximal distance a person is willing to walk for coffee.

The last test case is followed by a line containing four zeros.

Output

For each test case, print its number. For each query, print a line with the maximum number of coffee shops reachable within distance $m$ and the coordinates of the optimal location. For example, in the sample, $3$ coffee shops are within distance $1$ of the optimal location $(3, 4)$ , $4$ shops are within distance $2$ of the optimal location $(2, 2)$ , and $5$ shops are within distance $4$ of the optimal location $(3, 1)$ . If there are multiple optimal locations, choose the southernmost one (smallest positive $y$ -coordinate). If there is still a tie, choose the westernmost one (smallest positive $x$ -coordinate).

Follow the format of the sample output.

Examples

Example 1