FuriosaAI develops AI semiconductors for data centers and high-performance edge computing. RNGD is FuriosaAI's second-generation AI accelerator based on a proprietary architecture called TCP(Tensor Contraction Processor), and provides an SDK compatible with major frameworks such as PyTorch.

For RNGD's AI model to carry out an inference task, the model first needs to be compiled into a sequence of RNGD operations. Let's assume the following situation, which is a simplification of the actual compilation process.

The basic unit of time for an RNGD operation is a cycle, and the model's execution needs to be completed within $H$ cycles. Let the $H$ cycles be labeled cycle $1$, cycle $2$, $\cdots$, cycle $H$ sequentially.

There are $N$ operations in the compiled AI model. The execution of the $i$-th operation starts at cycle $A_i$ and ends at cycle $B_i$. Note that there may be operations whose cycles overlap.

While executing the compiled model, RNGD has been requested to execute one additional operation. The additional operation must not have overlapping cycles with any of the $N$ other operations and must be executed within the $H$ cycles. Specifically,

• Let $T$ be the number of cycles the additional operation takes to complete. In other words, if the additional operation begins executing at cycle $S$, it terminates at cycle $S+T-1$.
• While the additional operation is being executed, no other operations should be executed.
• $1\leq S\leq S+T-1 \leq H$ should hold.

The value of $T$ may differ based on the type of operation to be added. To test various cases, we will consider $Q$ different values of $T$. Given $T_i$, denoting the number of cycles required for the additional operation at the $i$-th case, write a program that calculates the number of possible starting cycles $S$ quickly.

Note that each case is handled independently. In other words, each of the additional operations is only effective for its corresponding case.

Input

The first line of input contains two space-separated integers $N$, denoting the number of operations of the AI model, and $H$, denoting the total number of cycles. ($0 \leq N \leq 200000$; $1 \leq H \leq 10^9$)

The $i$-th of the following $N$ lines contains two space-separated integers $A_i$ and $B_i$, denoting the beginning and ending cycles of the $i$-th operation. ($1 \leq A_i \leq B_i \leq H$)

The next line contains $Q$, denoting the number of cases to be tested. ($1 \leq Q \leq 200000$)

Each of the following $Q$ lines contains $T_i$, denoting the number of cycles required for the additional operation. ($1 \leq T_i \leq H$)

Output

Print $Q$ lines in total; the answer for each case in a single line.

Examples

Input 1

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

Output 1

11
5
2

Input 2

0 4
2
1
2

Output 2

4
3