맨해튼 택시

면접 대비

시간 제한2초메모리 제한512 MB

요약

기다리는 교차로 좌표와 최대 100대의 택시 좌표가 주어질 때, 맨해튼 거리가 가장 짧은 택시의 좌표를 출력한다.

난이도: 쉬움10점 중 2점
유형: 구현, 완전 탐색, 수학, 배열
정답자: 아직 제출이 없습니다

문제

뉴욕 맨해튼섬의 도로는 격자 모양이라서, 택시는 동, 서, 남, 북 네 방향으로만 달린다. 한 교차로에서 다른 교차로까지의 이런 거리를 택시 거리 또는 맨해튼 거리라고 부른다. 이 거리 개념은 19세기 독일의 헤르만 민코프스키가 처음 다뤘다.

맨해튼이 1km x 1km 블록으로 이루어진 100km x 100km 격자라고 하자. 어떤 사람이 교차로 $(0, 0)$ 에서 택시를 기다리고 택시 한 대가 교차로 $(100, 100)$ 에 있다면, 둘 사이의 맨해튼 거리는 200km다. 반대로 사람이 $(100, 100)$ 에서 기다리고 택시가 $(0, 0)$ 에 있어도 맨해튼 거리는 그대로 200km다.

맨해튼에는 택시가 여러 대 다닌다. 기다리는 교차로에서 가장 가까운 택시의 위치를 출력하라.

입력

첫째 줄에 택시를 기다리는 교차로의 좌표 $x$ 와 $y$ 가 공백으로 구분되어 주어진다. 둘째 줄에 맨해튼에서 운행 중인 택시의 수 $N$ 이 주어진다. $1 \le N \le 100$ 이다. 이어지는 $N$ 개의 줄에 택시 한 대가 서 있는 교차로의 좌표 $x$ 와 $y$ 가 공백으로 구분되어 주어진다.

모든 좌표는 0 이상 100 이하의 정수다. 택시는 항상 교차로에 서 있고, 한 교차로에 택시가 두 대 이상 있지는 않다. 기다리는 교차로에서 가장 가까운 택시는 정확히 한 대다.

출력

가장 가까운 택시의 좌표 $x$ 와 $y$ 를 공백으로 구분해 한 줄에 출력한다.

예제2

예제 1
입력
```
1 1
3
0 5
2 2
4 3
```
예상 출력
```
2 2
```
예제 2
입력
```
41 77
3
19 81
51 92
30 65
```
예상 출력
```
30 65
```