问题文

高桥君擅长使用目标检索（grep）。然而，尽管有许多人擅长目标检索（grep），但它不能成为一个特技。因此，高桥君正在阅读grep命令的手册，以学习并掌握一项新技能。

grep搜索命令有两个选项：-B和-A。当使用以下命令时：

grep -B x -A y "needle" kakikomi.txt

不仅会显示在文件kakikomi.txt中匹配模式"needle"的行，还会显示这些行之前的x行和之后的y行。如果行数不足以满足x,y的要求，则显示所有可用的行。

如果同一行号出现多次，则这些行将被合并，每行只会出现一次。输出示例中对此行为有详细说明。

现在，假设我们对文件kakikomi.txt执行了grep命令，并已知命中行的编号列表$L_1,L_2,...,L_n$。同时，给出了$m$个查询，每个查询都指定了$x,y$。对于每个查询，请回答执行带有-B x -A y选项的grep命令后显示的行数。

输入

输入通过标准输入提供，具有以下格式：$all$ $N$ $M$ $L_{1}$ $L_{2}$ : $L_{N}$ $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ : $x_{M}$ $y_{M}$

1. 第1行包含3个整数：$all$表示文件kakikomi.txt的行数（$1≦all≦10^9$），$N$表示命中行数（$1≦N≦\min(all,10^5)$），$M$表示查询的$x,y$数目（$1≦M≦10^5$）。
2. 第2行到第$N+1$行的$N$行提供了命中行的行号$L_i$（$1≦L_{i}≦all$）。

• 保证$L_i < L_{i+1}$。

4. 第$N+2$行到第$N+M+1$行的$M$行提供了每个$L_i$对应的查询整数$x_i, y_i$（$0≦x_i, y_i≦10^9$）。

输出

对于每个查询$x, y$，在一行中输出显示的行数。
最后输出一个换行符。

输入示例 1

7 2 3
2
4
1 1
3 0
3 4

输出示例 1

5
4
7

• 命中的行是第2行和第4行。
• 当$x = 1, y = 1$时，每个命中范围是第1行到第3行和第3行到第5行，所以总共显示了5行。
• 当$x = 3, y = 0$时，每个命中范围是第1行到第2行和第1行到第4行，所以总共显示了4行。
• 当$x = 3, y = 4$时，每个命中范围是第1行到第6行和第1行到第7行，所以总共显示了7行。

输入示例 2

100 5 5
3
18
24
57
90
1 8
27 0
15 16
22 3
2 2

输出示例 2

46
80
98
79
25