Inspections

Benson the Rabbit now has to build a plane!

Benson the Rabbit runs a factory with $n$ machines numbered from 1 to $n$. Each machine runs for one day, and only one machine can run at a time. Benson has $m$ tasks numbered from 1 to $m$. Task $i$ is given by two positive integers $l_i$ and $r_i$, where $l_i \le r_i$.

To complete task $i$, Benson must run machines $l_i, l_i+1, \dots, r_i$ in that order. When a machine finishes, the next machine starts immediately. When task $i$ is complete, Benson immediately starts task $i+1$, and so on until task $m$ is complete.

To follow safety regulations, the factory has a safety value $s$. If a machine has not been run in the past $s$ or more days, it must be inspected before it can run. A machine does not need to be inspected the first time it is run.

Benson has $q$ candidate safety values $s_1, s_2, \dots, s_q$. For each $s_j$, compute the number of inspections needed if the safety value is $s_j$.

The first line contains three space-separated integers $n$, $m$, and $q$. The next $m$ lines each contain two space-separated integers $l_i$ and $r_i$, describing task $i$. The last line contains $q$ space-separated integers $s_1, s_2, \dots, s_q$.

Output one line with $q$ space-separated integers. The $j$-th integer is the number of inspections needed when the safety value is $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}$