점검

벤슨 토끼는 이제 비행기를 만들어야 한다!

벤슨 토끼는 1부터 $n$까지 번호가 붙은 기계 $n$대가 있는 공장을 운영한다. 각 기계는 하루 동안 작동하며, 한 번에 한 기계만 작동할 수 있다. 벤슨에게는 1부터 $m$까지 번호가 붙은 작업 $m$개가 있다. 작업 $i$는 두 양의 정수 $l_i$와 $r_i$로 주어지며, $l_i \le r_i$이다.

작업 $i$를 완료하려면 기계 $l_i, l_i+1, \dots, r_i$를 이 순서대로 작동시켜야 한다. 기계 하나의 작동이 끝나면 다음 기계가 곧바로 시작된다. 작업 $i$가 완료되면 벤슨은 곧바로 작업 $i+1$을 시작하고, 작업 $m$이 완료될 때까지 이를 반복한다.

안전 규정을 지키기 위해 공장에는 안전값 $s$가 있다. 지난 $s$일 이상 작동하지 않은 기계는 작동시키기 전에 점검해야 한다. 기계를 처음 작동시킬 때는 점검이 필요 없다.

벤슨에게는 후보 안전값 $s_1, s_2, \dots, s_q$가 $q$개 있다. 각 $s_j$에 대해, 안전값이 $s_j$일 때 필요한 점검 횟수를 구하라.

첫째 줄에 세 정수 $n$, $m$, $q$가 공백으로 구분되어 주어진다. 이어지는 $m$개의 줄에는 작업 $i$를 나타내는 두 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어진다. 마지막 줄에는 $q$개의 안전값 $s_1, s_2, \dots, s_q$가 공백으로 구분되어 주어진다.

$q$개의 정수를 공백으로 구분하여 한 줄에 출력한다. $j$번째 정수는 안전값이 $s_j$일 때 필요한 점검 횟수이다.

• $1 \le n, m, q \le 200000$
• $1 \le l_i \le r_i \le n$
• $0 \le s_j \le 10^{12}$