Benson's Aircraft Factory

Benson the rabbit is building an airplane! In his factory there are n machines numbered from 1 to n. Each machine works exactly one day and only one machine can work each day.

Benson needs to manufacture m parts, numbered from 1 to m. The i-th part is represented by two integers \(l_i\) and \(r_i\) with \(l_i \le r_i\). To produce the i-th part, Benson runs the machines in order: \(l_i, l_i+1, \ldots, r_i\). When one machine finishes its work, the next one immediately starts. Similarly, the parts are processed one after the other without any gap between parts.

To ensure machine safety, the factory has a check threshold \(s\). If a machine has not been activated for s or more consecutive days prior to a start (note that the very first start of any machine does not require a safety check), then a safety check must be performed immediately before it is started.

Benson has q queries \(s_1, s_2, \ldots, s_q\). For each check threshold \(s_j\), calculate the total number of safety checks performed during the entire manufacturing process.

Note: For each machine, consider the days on which it operates. If a machine operates on day \(d\) and then later on day \(d'\), then it will need a check before the later start if and only if \(d' - d - 1 \ge s_j\). The answer for each query is the sum, over all machines, of the number of times a safety check is required.

The day on which a machine operates for a given part is computed as follows. Define a base day for each part. For part \(i\), let base_i be \(1+\sum_{t=1}^{i-1}(r_t-l_t+1)\). Then if machine \(j\) is used in part \(i\) (i.e. \(l_i \le j \le r_i\)), it operates on day \(\text{base}_{i} + (j-l_i)\).

inputFormat

The first line contains three integers \(n, m, q\) representing the number of machines, the number of parts, and the number of queries.

The following m lines each contain two integers \(l_i\) and \(r_i\) (with \(1 \le l_i \le r_i \le n\)) for \(i=1,2,\ldots,m\).

The last line contains q integers \(s_1, s_2, \ldots, s_q\).

outputFormat

Output q integers. The \(j\)-th integer is the total number of safety checks required for the threshold \(s_j\). The answers can be printed in one line separated by spaces.

sample

5 3 3
1 3
2 5
3 4
0 1 2

4 4 2