커피 전문점

어떤 동네에 커피 전문점이 여러 곳 있다. 이 동네는 정사각형 격자 모양이고, 모든 길은 남북 방향 또는 동서 방향으로 나 있어 교차로들이 격자점을 이룬다.

두 교차로 $(a, b)$와 $(c, d)$ 사이의 거리는 맨해튼 거리 $|a - c| + |b - d|$이며, 이는 한 교차로에서 다른 교차로로 오갈 때 지나야 하는 블록의 수와 같다.

모든 커피 전문점의 위치가 주어지고 걸어서 갈 수 있는 블록 수의 상한 $m$이 정해질 때, 어떤 교차로로부터 $m$블록 이내에 있는 커피 전문점의 개수가 가장 많아지는 교차로를 찾는 프로그램을 작성하시오. 후보가 되는 교차로는 도시 안의 격자점, 즉 $1 \le x \le dx$이고 $1 \le y \le dy$인 $(x, y)$이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 하나의 도시를 나타낸다.

각 테스트 케이스의 첫째 줄에는 네 정수 $dx$, $dy$, $n$, $q$가 주어진다. 도시의 크기는 $dx \times dy$ ($1 \le dx, dy \le 1000$)이고, 도시에 있는 커피 전문점의 수는 $n$ ($0 \le n \le 5 \cdot 10^5$), 질의의 수는 $q$ ($1 \le q \le 20$)이다.

이어지는 $n$개의 줄에는 두 정수 $x_i$와 $y_i$ ($1 \le x_i \le dx$, $1 \le y_i \le dy$)가 주어지며, 이는 $i$번째 커피 전문점의 위치를 나타낸다. 한 교차로에 있는 커피 전문점은 최대 한 개이다.

그 다음 $q$개의 줄에는 정수 $m$이 한 줄에 하나씩 주어진다. $m$ ($0 \le m \le 10^6$)은 걸어서 갈 수 있는 블록 수의 최대값이다.

입력의 마지막 줄에는 정수 $0$이 네 개 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다 먼저 Case k: 형식으로 테스트 케이스 번호 $k$를 출력한다($k$는 $1$부터 시작한다). 그 다음 각 질의마다 한 줄씩 출력하는데, 그 질의의 $m$에 대해 어떤 교차로로부터 $m$블록 이내에 있는 커피 전문점의 최대 개수와 그 개수를 달성하는 교차로의 위치를 개수 (x,y) 형식으로 출력한다.

최대 개수를 달성하는 교차로가 여러 개라면 가장 남쪽에 있는 것(즉 $y$좌표가 가장 작은 것)을 출력하고, 그래도 여러 개라면 가장 서쪽에 있는 것(즉 $x$좌표가 가장 작은 것)을 출력한다.