경비원

지난 몇 주 동안 Binary Casino는 주변 카지노를 노리는 지역 범죄의 표적이 되었다. Binary Casino에는 감시 카메라가 설치되어 있지만, 카지노 안을 순찰하는 사람이 거의 없어 도둑들은 대개 손쉽게 빠져나간다.

금요일 수익금 전부를 도난당한 뒤, Binary Casino의 지배인은 참지 못하고 경비원을 대거 고용해 카지노의 보안을 강화하기로 했다. 그러나 카지노의 누구도 보안을 최대화하도록 경비원을 카지노 전체에 배치하는 계획을 세우지 못했다. 그래서 경비원들은 체계 없이 카지노 곳곳에 흩어져 있다. 다행히도 이들의 위치는 2차원 평면의 정수 좌표로 나타낼 수 있다.

경비원이 고르게 배치되지 않았기 때문에, 강도 사건이 신고되면 보안 감독관이 사건 현장에 가장 가까운 경비원이 누구인지 판단하기가 매우 어렵다. 카지노의 공간이 끝없이 이어지는 슬롯 머신 통로로 이루어져 있어서 일은 더욱 어렵다. 이 제약 때문에 각 경비원은 한 위치에서 다른 위치로 여러 단계를 거쳐 이동해야 한다. 각 단계에서 경비원은 자신의 좌표 각각을 1, 0 또는 -1만큼 바꿀 수 있다. 두 위치 사이의 거리는 경비원이 한 위치에서 다른 위치로 가기 위해 수행해야 하는 최소 단계 수와 같다.

경비원의 위치들과 보안 사건들의 위치가 주어질 때, 각 사건마다 경비원까지의 최소 거리를 계산하는 것이 과제이다. 이를 통해 보안 감독관은 적절한 경비원에게 경보를 보낼 수 있고 카지노의 보안이 크게 향상될 것이다.

첫째 줄에는 두 정수 N과 Q (1 ≤ N, Q ≤ 3 · 10^5)가 주어진다. N은 경비원의 수, Q는 보안 사건의 수이다. 이어서 N개의 줄이 주어진다. 각 줄에는 2차원 평면에서 경비원의 좌표를 나타내는 두 정수 X와 Y (0 ≤ X, Y ≤ 5000)가 주어진다. 다음으로 Q개의 줄이 주어진다. 각 줄에는 보안 사건의 좌표를 나타내는 두 정수 A와 B (0 ≤ A, B ≤ 5000)가 주어진다.

Q개의 보안 사건 각각에 대해, 경비원까지의 최소 거리를 단계 수로 나타낸 값을 한 줄에 하나씩 출력한다.