MITの建物の配置に混乱したBusy Beaverは、より単純な配置であるMajestic Interconnected Toroid Institute of Technology (MITIT) を設計することにしました。

円周 $C$ の円上に、$1, \dots, N$ と番号付けられた $N$ 個の主要な建物があります。$i$ 番目の建物は円周上の位置 $L_i$ ($0 \le L_i < C$) にあり、高さ $H_i$ を持っています。円の中心にはもう一つ、学生センターという建物があり、その高さはまだ決まっていません。

Busy Beaverは、$N+1$ 個の建物をいくつかの直線状のトンネルで接続し、どの建物からでもトンネルを使って他のすべての建物に到達できるようにしたいと考えています。トンネルは、2つの建物を結ぶ（2次元平面上の）線分としてモデル化できます。これらのトンネルはすべて同じ高さにあるため、対応する線分は（端点を除いて）交差してはなりません。ある理由により、高さ $h_1$ と $h_2$ の2つの建物の間にトンネルを建設するコストは $|h_1-h_2|$ となります。

Busy Beaverは $Q$ 個の質問 $M_1, \dots, M_Q$ を持っており、学生センターの高さが $M_i$ である場合、すべての建物を接続するための最小コストはいくらになるかを知りたがっています。

入力

各テストケースには複数のテストが含まれます。最初の行にはテストケースの数 $T$ ($1 \le T \le 500$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、3つの整数 $N, Q, C$ ($1 \le N \le 500, 1 \le Q \le 10^6, 1 \le C \le 10^9$) が含まれます。

続く $N$ 行の各行には、2つの整数 $L_i$ と $H_i$ ($0 \le L_i < C, 1 \le H_i \le 10^9$) が含まれます。

続く $Q$ 行の各行には、1つの整数 $M_i$ ($1 \le M_i \le 10^9$) が含まれます。

$L_i$ はすべて異なり、直径方向に対向する2つの建物（$L_i = L_j+C/2$ となるような $i, j$）は存在しません。

すべてのテストケースにおける $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

注記

最初のテストケースの質問に対する建物を接続する最適な方法の一つは、以下の通りです。

2番目のテストケースでは、学生センターと唯一の他の建物を接続するコストは $|1-998244353| = 998244352$ となります。