Bobo 有一个序列 $p_1, p_2, \dots, p_n$。初始时，$p_i = i$。

有一天，Bobo 想到了无限次操作。这些操作由 $m$ 对整数 $(a_1, b_1), (a_2, b_2), \dots, (a_m, b_m)$ 描述。第 $i$ 次操作是将第 $a_{(i - 1) \bmod m + 1}$ 个元素到第 $b_{(i - 1) \bmod m + 1}$ 个元素之间的部分进行反转。注意，序列 $q_1, q_2, \dots, q_n$ 在反转第 $x$ 个到第 $y$ 个元素后，会变为 $q_1, \dots, q_{x - 1}, q_y, q_{y - 1}, \dots, q_x, q_{y + 1}, \dots, q_n$。

Bobo 还有 $q$ 个询问 $k_1, k_2, \dots, k_q$。第 $i$ 个询问是问：如果他只执行前 $k_i$ 次操作，满足 $p_i = i$ 的 $i$ 的个数是多少。请回答这些询问。

输入格式

输入包含多组测试数据，并以文件结束符（EOF）结束。

每组测试数据的第一行包含三个整数 $n, m$ 和 $q$。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$。

最后的 $q$ 行中，第 $i$ 行包含一个整数 $k_i$。

输出格式

对于每组测试数据，输出 $q$ 个整数，表示对应的答案。

样例

样例输入 1

5 1 2
2 4
1
2
5 2 1
1 3
3 5
1000000000

样例输出 1

3
5
2

说明

对于第一个样例，序列在第一次操作后变为 $1, 4, 3, 2, 5$，在第二次操作后变为 $1, 2, 3, 4, 5$。因此，答案分别为 $3$ 和 $5$。

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 10$
• $1 \leq q \leq 10^5$
• $1 \leq a_i \leq b_i \leq n$
• $1 \leq k_i \leq 10^9$
• 测试数据组数不超过 $5$。