레이팅 미적용한때의 유행일까, 아니면 계속될까? 확실하진 않지만, 당신의 고향에 꾸준히 늘어나는 커피숍은 확실히 큰 인기를 끌게 되었다. 사람들이 커피에 너무 중독된 나머지, 많은 커피숍과 가까운 아파트는 실제로 더 높은 임대료를 받는다고 한다. 이는 지역 부동산(re\(al-es\)tate) 회사의 관심을 끌었다. 이들은 많은 커피숍과의 근접성 측면에서 도시에서 가장 가치 있는 위치를 찾고 싶어 한다. 이들은 커피숍 위치가 표시된 도시 지도를 주었다. 보통 사람이 아침 커피를 위해 정해진 수의 블록만 걸을 의향이 있다고 가정할 때, 가장 많은 커피숍에 도달할 수 있는 위치를 찾아야 한다. 아마 알고 있겠지만, 당신의 고향은 남북(nor\(th-so\)uth)과 동서(ea\(st-we\)st) 축에 맞춰 블록이 정렬된 정사각 격자 구조로 지어져 있다. 거리를 따라 걸어야 하므로 교차로 (a, b)와 (c, d) 사이의 거리는 |\(a - c\)| + |\(b - d\)|이다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 하나의 도시를 설명한다. 각 테스트 케이스의 첫 줄에는 네 정수 \(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\)개의 줄에는 각각 두 정수 \(xi\)와 \(yi\) (\(1 \le xi \le dx\), \(1 \le yi \le dy\))가 주어지며, 이는 \(i^{th}\)번째 커피숍의 위치를 나타낸다. 한 교차로에는 커피숍이 최대 하나 있다. 다음 \(q\)개의 줄에는 각각 정수 \(m\) (\(0 \le m \le 10^{6}\)) 하나가 주어지며, 이는 사람이 커피 한 잔을 위해 걸을 수 있는 최대 거리이다. 마지막 테스트 케이스 다음에는 0 네 개가 있는 줄이 주어진다.
입력의 각 테스트 케이스마다 케이스 번호를 출력한다. 그런 다음 테스트 케이스의 질의마다 한 줄씩 출력한다. 각 줄에는 주어진 질의 거리 \(m\) 안에서 도달할 수 있는 커피숍의 최대 개수와 최적 위치를 출력한다. 예를 들어 샘플 출력은 최적 위치 (3, 4)에서 질의 거리 1 안에 커피숍 3개, 최적 위치 (2, 2)에서 질의 거리 2 안에 4개, 최적 위치 (3, 1)에서 질의 거리 4 안에 5개가 있음을 보여 준다. 최적 위치가 여러 개이면 가장 남쪽 위치(양의 정수 y 좌표(\(y-co\)ordinate)가 최소)를 선택한다. 그래도 같으면 가장 서쪽 위치(양의 정수 x 좌표(\(x-co\)ordinate)가 최소)를 선택한다. 샘플 출력의 형식을 따른다.
4 4 5 3
1 1
1 2
3 3
4 4
2 4
1
2
4
0 0 0 0
ICPC 2011 World Finals Problem E: Coffee Central
Case 1:
3 (3,4)
4 (2,2)
5 (3,1)