Zdezorientowany układem budynków MIT, Busy Beaver postanowił zaprojektować prostszy układ – Majestic Interconnected Toroid Institute of Technology (MITIT)...

Istnieje $N$ głównych budynków o numerach $1,\dots,N$ rozmieszczonych na okręgu o obwodzie $C$. $i$-ty budynek znajduje się w punkcie $L_i$ ($0 \le L_i < C$) wzdłuż okręgu i ma wysokość $H_i$. Istnieje jeszcze jeden budynek, centrum studenckie, znajdujące się w środku okręgu, którego wysokość nie została jeszcze ustalona.

Busy Beaver chce połączyć $N+1$ budynków za pomocą prostych tuneli w taki sposób, aby z każdego budynku można było dotrzeć do każdego innego budynku przy użyciu tych tuneli. Tunel można modelować jako odcinek (w płaszczyźnie dwuwymiarowej) łączący dwa budynki. Wszystkie te tunele będą znajdować się na tej samej wysokości, więc odpowiadające im odcinki nie mogą się przecinać (z wyjątkiem punktów końcowych). Z pewnych powodów koszt budowy tunelu między dwoma budynkami o wysokościach $h_1$ i $h_2$ jest równy $|h_1-h_2|$.

Busy Beaver ma $Q$ pytań $M_1,\dots,M_Q$, w których zastanawia się: jaki jest minimalny możliwy koszt połączenia wszystkich budynków, jeśli centrum studenckie ma wysokość $M_i$?

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $T$ ($1 \le T \le 500$). Następnie następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera trzy liczby całkowite $N$, $Q$ oraz $C$ ($1 \le N \le 500$, $1 \le Q \le 10^6$, $1 \le C \le 10^9$).

$i$-ta z kolejnych $N$ linii zawiera dwie liczby całkowite $L_i$ oraz $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$).

$i$-ta z kolejnych $Q$ linii zawiera pojedynczą liczbę całkowitą $M_i$ ($1 \le M_i \le 10^9$).

Wartości $L_i$ są parami różne i nie istnieją dwa budynki położone diametralnie przeciwnie (takie $i$ oraz $j$, że $L_i = L_j+C/2$).

Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $500$.

Gwarantuje się, że suma $Q$ we wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Wypisz $Q$ linii: minimalny koszt połączenia wszystkich budynków, gdy centrum studenckie ma odpowiednio wysokość $M_1,\dots,M_Q$.

Podzadania

Niech $\sum N$ oznacza sumę $N$ we wszystkich przypadkach testowych, a $\sum Q$ oznacza sumę $Q$ we wszystkich przypadkach testowych.

• ($15$ punktów) $\sum N,\sum Q \le 80$ oraz $0 \le L_i < C/2$ dla wszystkich $i$.
• ($15$ punktów) $\sum N,\sum Q \le 80$.
• ($15$ punktów) $\sum N \le 80$ oraz $0 \le L_i < C/2$ dla wszystkich $i$.
• ($10$ punktów) $\sum N \le 80$.
• ($15$ punktów) $\sum Q \le 500$ oraz $0 \le L_i < C/2$ dla wszystkich $i$.
• ($10$ punktów) $\sum Q \le 500$.
• ($10$ punktów) $0 \le L_i < C/2$ dla wszystkich $i$.
• ($10$ punktów) Brak dodatkowych ograniczeń.

Przykład

Przykład 1

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

Wyjście 1

6
10
5
7
998244352

Uwagi

Jeden z optymalnych sposobów połączenia budynków dla pytań z pierwszego przypadku testowego przedstawiono poniżej:

Dla drugiego przypadku testowego koszt połączenia centrum studenckiego z jedynym innym budynkiem wynosi $|1-998244353| = 998244352$.