由於對 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$ 行中的第 $i$ 行包含一個整數 $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$。