#P18518. Circular Route

Circular Route

Circular Route

小青鱼是 Cup Universe 中 H 城的国王。H 城有一条长度为 (L) 的环形路线,沿路线逆时针依次有编号为 (0,1,\ldots,L-1) 的 (L) 个车站。从车站 (p) 逆时针前进一个单位距离,就到达车站 ((p+1)\bmod L)。

一辆公交车在时刻 (0) 从车站 (x) 出发,以恒定速度 (1) 沿路线逆时针行驶,不断绕圈。这辆车很小,任意时刻最多只能载一名乘客。

现在有 (n) 个人需要乘车。第 (i) 个人希望从车站 (s_i) 到达车站 (t_i)。公交车到达其出发站时,他可以上车;上车后必须一直留在车上,直到到达目的站才下车。他也可以选择这次不上车,等待公交车在以后的某一圈再次到达。上下车均瞬间完成,不需要额外时间。

从时刻 (0) 开始,最少经过多长时间,才能将所有人送到各自的目的地?

请回答 (q) 个询问,每个询问给出公交车不同的初始车站 (x)。每个询问彼此独立,均从所有乘客尚未出发的状态开始。

输入格式

一个输入文件包含多组测试数据。

第一行包含一个整数 (T)((1\le T\le10^5)),表示测试数据组数。

对于每组测试数据:

  • 第一行包含两个整数 (n,L),满足 (1\le n\le2\times10^5)、(2\le L\le10^9)。
  • 接下来 (n) 行,每行包含两个整数 (s_i,t_i),满足 (0\le s_i,t_i<L)、(s_i\ne t_i),表示第 (i) 个人的出发站和目的站。
  • 接下来一行包含一个整数 (q),满足 (1\le q\le10^6)。
  • 接下来 (q) 行,每行包含一个车站编号 (x_i),表示一次询问的初始位置。

保证一个输入文件中,所有测试数据的 (n) 之和不超过 (2\times10^5),所有 (q) 之和不超过 (10^6)。

不同的人可以有完全相同的出行需求,他们仍然是需要分别运送的不同乘客。

输出格式

对于每组测试数据,输出 (q) 行,第 (i) 行包含一个整数,表示第 (i) 个起点对应的最短时间。

样例

输入:

3
2 10
3 7
8 0
4
1
3
5
9
4 4
0 2
2 0
1 3
3 1
1
0
3 1000000000
0 999999999
0 999999999
0 999999999
1
1

输出:

9
7
12
11
9
3999999998