35283번 - 히스토그램에서의 거리와 가장 가까운 점

좌표평면 위에 너비가 $N$인 히스토그램이 있다. 히스토그램의 가장 왼쪽 막대의 왼쪽 아래 꼭짓점은 좌표평면의 점 $(0.5, 0.5)$에 위치해 있다. 히스토그램의 왼쪽에서 $i$번째 막대는 너비가 $1$이고, 높이는 $a_i$이다. ($1 \le i \le N$)

유효 격자는 히스토그램의 내부에 위치해 있으며 각 좌표가 모두 정수인 점의 집합이다. 이때 유효 격자에 포함된 점을 격자점이라 부른다.

구체적으로, 유효 격자는 아래의 집합 $V$와 같이 정의된다.

$$V = \{ (x, y) \mid 1 \le x \le N, \, 1 \le y \le a_x, \, (x, y) \in \mathbb{Z}^2 \}$$

두 격자점 $u, v$ 사이의 거리 $D(u, v)$는 "$u$에서 시작하여 상하좌우로 인접한 격자점만을 방문하여 $v$에 도달하는 최단 경로에 포함된 격자점의 개수"로 정의된다. 시작점과 도착점도 개수에 포함한다.

$K$개의 격자점으로 이루어진 집합 $P = \{p_1, p_2, \dots, p_K\}$가 주어진다. 유효 격자에 포함된 $Q$개의 쿼리 점 $q_1, q_2, \dots, q_Q$가 주어질 때, 각 쿼리 점 $q_j$ ($1 \le j \le Q$)에 대해 집합 $P$에 있는 점들 중 가장 가까운 거리를 구하는 프로그램을 작성하시오. 즉, 각 $q_j$에 대해 다음 값을 구해야 한다.

$$\min_{1 \le i \le K} D(p_i, q_j)$$

첫 번째 줄에 히스토그램의 너비 $N$, 집합 $P$의 크기 $K$, 쿼리 점의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N,Q,K\leq 100\,000$; $N$, $Q$, $K$는 정수)

두 번째 줄에 각 히스토그램 막대의 높이를 나타내는 $N$개의 정수 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다. ($1 \leq a_i \leq 10^9$)

세 번째 줄부터 $K$개의 줄에 걸쳐, $i+2$번째 줄에 $p_i$의 $x$좌표와 $y$좌표가 공백으로 구분되어 순서대로 주어진다.

그다음 줄부터 $Q$개의 줄에 걸쳐, $i+K+2$번째 줄에 $q_i$의 $x$좌표와 $y$좌표가 공백으로 구분되어 순서대로 주어진다.

주어지는 모든 $x$좌표는 $0$보다 크고 $N$보다 작거나 같은 정수이고, 모든 $y$좌표는 $0$보다 크고 $a_x$보다 작거나 같은 정수이다.

$Q$개의 줄에 걸쳐, $j$번째 줄에 $\min_{1 \le i \le K} D(p_i, q_j)$을 출력한다.

주어지는 좌표는 같을 수도 있음에 유의하라.