FuriosaAI 为数据中心和高性能边缘计算开发 AI 半导体。RNGD 是 FuriosaAI 基于名为 TCP（Tensor Contraction Processor，张量收缩处理器）的自主架构开发的第二代 AI 加速器，并提供与 PyTorch 等主流框架兼容的 SDK。

为了让 RNGD 的 AI 模型执行推理任务，首先需要将该模型编译为一系列 RNGD 操作。我们假设以下情况，这是对实际编译过程的简化。

RNGD 操作的基本时间单位是周期（cycle），模型的执行需要在 $H$ 个周期内完成。我们将这 $H$ 个周期依次标记为周期 $1$，周期 $2$，$\cdots$，周期 $H$。

在编译后的 AI 模型中共有 $N$ 个操作。第 $i$ 个操作的执行从周期 $A_i$ 开始，到周期 $B_i$ 结束。注意，某些操作的周期可能会有重叠。

在执行编译后的模型时，RNGD 被请求额外执行一个操作。该额外操作的周期不能与其它 $N$ 个操作中的任何一个重叠，且必须在这 $H$ 个周期内执行。具体而言：

• 设 $T$ 为该额外操作完成所需的周期数。换句话说，如果该额外操作从周期 $S$ 开始执行，它将在周期 $S+T-1$ 结束。
• 在执行该额外操作期间，不应执行任何其他操作。
• 必须满足 $1\leq S\leq S+T-1 \leq H$。

$T$ 的值可能会根据要添加的操作类型而有所不同。为了测试各种情况，我们将考虑 $Q$ 个不同的 $T$ 值。给定 $T_i$ 表示第 $i$ 种情况下额外操作所需的周期数，请编写一个程序，快速计算可能的起始周期 $S$ 的数量。

注意，每个情况都是独立处理的。换句话说，每个额外操作仅对其对应的情况有效。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $H$，分别表示 AI 模型的操作数和总周期数。($0 \leq N \leq 200000$；$1 \leq H \leq 10^9$)

接下来的 $N$ 行中，第 $i$ 行包含两个空格分隔的整数 $A_i$ 和 $B_i$，表示第 $i$ 个操作的开始和结束周期。($1 \leq A_i \leq B_i \leq H$)

下一行包含一个整数 $Q$，表示要测试的情况数量。($1 \leq Q \leq 200000$)

接下来的 $Q$ 行中，每行包含一个整数 $T_i$，表示额外操作所需的周期数。($1 \leq T_i \leq H$)

输出格式

共输出 $Q$ 行，每行输出对应情况的答案。

样例

输入样例 1

3 30
5 8
12 19
14 23
3
2
4
6

输出样例 1

11
5
2

输入样例 2

0 4
2
1
2

输出样例 2

4
3