33576번 - 자습실과 쿼리

자습실에서 공부를 하던 $Q$명의 학생들은 공부가 너무나도 지루한 나머지 탈출을 결심한다.

학생들이 공부하고 있는 자습실은 가장 왼쪽부터 순서대로 $1, 2, \cdots, N$번 구역으로 구성된 $1$차원 구조이고, $1$번 구역이나 $N$번 구역에 도달하면 자습실에서 탈출할 수 있다. 자습실 곳곳에는 $M$개의 벽이 있는데, $i$번째 벽은 $D_i$의 내구도를 가지며 $W_i$ 구역에 있다.

학생들은 각자 본인이 공부하던 구역에서 출발해 왼쪽 또는 오른쪽으로 한 칸씩 이동할 수 있으며, 만약 이동하려는 구역에 내구도가 $1$ 이상 남아있는 벽이 있다면 그 구역으로 이동할 수 없다. 학생들은 인접한 구역에 있는 벽을 망치로 내려칠 수 있다. 망치로 벽을 내려치면 벽의 내구도가 $1$만큼 감소하며, 내구도가 $0$이 된 벽은 영원히 파괴되어 벽이 있던 구역으로 이동할 수 있게 된다. 하나의 벽을 동시에 여러 사람이 부수면 파편으로 인해 위험할 수 있으므로 학생들은 한 명씩 차례대로 탈출하기로 했다. $i+1$번 친구는 $i$번 친구가 탈출을 완료한 이후에만 행동할 수 있다. $(1 \leq i < Q)$

각 학생은 다음 조건에 따라 탈출한다.

• 최소한의 망치질로 탈출하는 방법으로 탈출한다.
• 만약 최소한의 망치질로 탈출하는 방법이 여러 가지일 경우 이동 거리가 최소인 방법으로 탈출한다.
• 만약 최소한의 망치질과 최소한의 이동 거리로 탈출하는 방법이 여러 가지인 경우 $1$번 구역으로 탈출한다.

$i$번 학생은 $P_i$번 구역에서 공부하고 있다. $1$번 학생부터 $Q$번 학생까지 차례대로 탈출할 때 각 학생이 몇 번의 망치질을 했는지 출력하시오.

첫 번째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분하여 주어진다. $(3 \le N \le 10^5; 0 \le M < N; 1 \le Q \le 10^5)$

다음 $M$개의 줄 중 $i$번째 줄에는 두 정수 $W_i$와 $D_i$가 공백으로 구분하여 주어진다. $(1 \le W_1, W_2, \cdots, W_M \le N; 1 \le D_1, D_2, \cdots, D_M \le 10^5)$

다음 $Q$개의 줄 중 $i$번째 줄에는 정수 $P_i$가 주어진다. $(1 \le P_1, P_2, \cdots, P_Q \le N)$

모든 입력에서 벽은 서로 겹치지 않는다. 학생들이 공부하고 있는 구역에 벽이 있는 입력은 주어지지 않는다.

첫 번째 줄부터 $Q$개의 줄에 걸쳐 $1$번 학생부터 $Q$번 학생까지 탈출하기 위해 망치질한 횟수를 한 줄에 하나씩 순서대로 출력한다.