원룸 구하기

올해 대학에 입학한 에띠는 대학 근처 대학로에 원룸을 구하기로 하였다. 무엇보다 원룸의 위치를 중요하게 생각하는 에띠는 생활에 필수적인 편의점, 마트, 빨래방, PC방 등 $K$ 종류의 가게가 가장 가까운 곳에 살고 싶어한다. 각 가게의 종류는 $1$부터 $K$ 사이의 정수로 표현할 수 있다.

대학로는 길게 뻗은 직선 형태의 도로이며, 각 가게의 위치는 이 직선 위의 정수로 주어진다. 두 지점 사이의 거리는 위치의 차이이다.

에띠는 대학로에 있는 총 $N$ 곳의 가게의 위치를 알아내었고, 입주 가능한 원룸의 위치 $M$ 곳의 위치도 알아내었다. 에띠는 자신의 요구를 합리적으로 계산하기 위해서, 각 원룸 위치의 필수 생활 거리를 다음과 같이 정의하였다.

위치 $x$의 필수 생활 거리는 $K$ 종류의 가게 모두와 $x$를 포함하는 가장 짧은 구간의 길이이다.

예를 들어, $N=4$, $K=2$라고 하자. $1$번 종류의 가게가 좌표 $1$, $7$에 있고, $2$번 종류 가게가 좌표 $2, 5$에 있다고 하자.

• 만약 $x=3$이라고 하면, $1$번 종류 가게가 좌표 $1$, $2$번 종류 가게가 좌표 $2$에 있으므로 구간 $[1, 3]$이 조건을 만족한다. 따라서 $x=3$에서 필수 생활 거리는 $3-1=2$이다.
• 만약 $x=4$라고 하면, 비슷한 과정을 통해서 구간 $[1,4]$와 구간 $[4,7]$이 모두 조건을 만족하며, 어느 쪽이든 $4-1=7-4=3$이므로 $x=4$에서 필수 생활 거리는 $3$이다.

$N$ 개의 가게의 위치와 그 종류, 그리고 $M$ 개의 원룸의 위치가 주어질 때, 각 원룸의 위치에서 필수 생활 거리를 구하라.

입력 형식

첫 줄에 가게의 수를 나타내는 정수 $N$, 가게의 종류를 나타내는 정수 $K$, 원룸의 수를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. ($1 \le N, K, M \le 500\,000$)

다음 $N$ 개의 줄은 가게에 대한 정보를 나타낸다. 각 줄에는 두 정수 $p$와 $t$가 공백으로 구분되어 주어진다. 이는 좌표 $p$에 종류 $t$인 가게가 있다는 뜻이다. ($-1\,000\,000\,000 \le p \le 1\,000\,000\,000;$ $1 \le t \le K$)

다음 $M$ 개의 줄에 걸쳐, 각 원룸에 대한 정보를 나타내는 정수 $x$가 주어진다. 이중 $i$ 번째 줄에 주어지는 수 $x$는 $i$ 번째 원룸의 좌표를 의미한다. ($-1\,000\,000\,000 \le x \le 1\,000\,000\,000$)

$K$ 종류의 가게가 적어도 하나가 존재하도록 입력이 주어지며, 한 위치에 가게가 여러 개 있을 수 있고, 가게가 있는 위치에 원룸이 있을 수 있다.

출력 형식

$M$ 개의 줄에 걸쳐, $i$ 번째 줄에 $i$ 번째 원룸의 필수 생활 거리를 출력한다.

예제

4 2 3
1 1
2 2
5 2
7 1
3
4
9

2
3
4

예제 설명

예제는 본문에서 주어진 것에 원룸의 위치가 $9$에 있는 경우가 추가되었다. 원룸의 위치가 $3$, $4$인 경우는 본문에서 설명하였으며, 각각 필수 생활 거리가 $2$, $3$이다. 원룸의 위치가 $9$에 있는 경우, 이 원룸과 두 가지 종류의 가게를 모두 포함하는 가장 짧은 구간은 $[5, 9]$이고, 필수 생활 거리는 $9-5=4$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설