由于对 MIT 的建筑布局感到困惑，Busy Beaver 决定设计一种更简单的布局——Majestic Interconnected Toroid Institute of Technology (MITIT)...

有 $N$ 座主建筑，编号为 $1, \dots, N$，它们排列在一个周长为 $C$ 的圆上。第 $i$ 座建筑位于圆上位置 $L_i$ ($0 \le L_i < C$) 处，高度为 $H_i$。此外还有一座位于圆心的学生活动中心，其高度尚未确定。

Busy Beaver 想要用一些直线隧道连接这 $N+1$ 座建筑，使得任意两座建筑之间都可以通过这些隧道互相到达。隧道可以建模为连接两座建筑的线段（在二维平面上）。所有隧道处于同一高度，因此它们对应的线段不能相交（端点除外）。出于某种原因，在高度为 $h_1$ 和 $h_2$ 的两座建筑之间建造隧道的成本等于 $|h_1-h_2|$。

Busy Beaver 有 $Q$ 个询问 $M_1, \dots, M_Q$，他想知道：如果学生活动中心的高度为 $M_i$，连接所有建筑的最小总成本是多少？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数量 $T$ ($1 \le T \le 500$)。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $N$、$Q$ 和 $C$ ($1 \le N \le 500$, $1 \le Q \le 10^6$, $1 \le C \le 10^9$)。

接下来的 $N$ 行中，第 $i$ 行包含两个整数 $L_i$ 和 $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$)。

接下来的 $Q$ 行中，每行包含一个整数 $M_i$ ($1 \le M_i \le 10^9$)。

$L_i$ 两两不同，且不存在两座建筑处于直径相对的位置（即不存在 $i, j$ 使得 $L_i = L_j+C/2$）。

保证所有测试用例的 $N$ 之和不超过 $500$。

保证所有测试用例的 $Q$ 之和不超过 $10^6$。

输出格式

输出 $Q$ 行：分别对应学生活动中心高度为 $M_1, \dots, M_Q$ 时连接所有建筑的最小成本。

子任务

令 $\sum N$ 表示所有测试用例中 $N$ 的总和，$\sum Q$ 表示所有测试用例中 $Q$ 的总和。

• ($15$ 分) $\sum N, \sum Q \le 80$ 且对于所有 $i$ 均有 $0 \le L_i < C/2$。
• ($15$ 分) $\sum N, \sum Q \le 80$。
• ($15$ 分) $\sum N \le 80$ 且对于所有 $i$ 均有 $0 \le L_i < C/2$。
• ($10$ 分) $\sum N \le 80$。
• ($15$ 分) $\sum Q \le 500$ 且对于所有 $i$ 均有 $0 \le L_i < C/2$。
• ($10$ 分) $\sum Q \le 500$。
• ($10$ 分) 对于所有 $i$ 均有 $0 \le L_i < C/2$。
• ($10$ 分) 无附加限制。

样例

输入 1

2
4 4 5
0 3
1 1
2 4
4 1
5
9
2
6
1 1 1000000000
998244353 998244353
1

输出 1

6
10
5
7
998244352

说明

第一个测试用例中，针对各询问连接建筑的一种最优方式如下图所示：

对于第二个测试用例，将学生活动中心与仅有的一座建筑连接的成本为 $|1-998244353| = 998244352$。