Confundido por la disposición de los edificios del MIT, Busy Beaver decidió diseñar un plano más simple: el Majestic Interconnected Toroid Institute of Technology (MITIT)...

Hay $N$ edificios principales numerados $1, \dots, N$ dispuestos en un círculo con circunferencia $C$. El edificio $i$-ésimo se encuentra en la posición $L_i$ ($0 \le L_i < C$) a lo largo del círculo y tiene una altura de $H_i$. Hay un edificio más, el centro estudiantil, ubicado en el centro del círculo, cuya altura aún no se ha decidido.

Busy Beaver quiere conectar los $N+1$ edificios con algunos túneles rectos de tal manera que cualquier edificio pueda llegar a cualquier otro edificio usando estos túneles. Un túnel puede modelarse como un segmento de línea (en un plano bidimensional) que conecta dos de los edificios. Todos estos túneles estarán a la misma elevación, por lo que sus segmentos de línea correspondientes no deben intersectarse (excepto en los puntos finales). Por alguna razón, el costo de construir un túnel entre dos edificios con alturas $h_1$ y $h_2$ es igual a $|h_1 - h_2|$.

Busy Beaver tiene $Q$ preguntas $M_1, \dots, M_Q$, donde se pregunta: ¿Cuál es el costo mínimo posible para conectar todos los edificios si el centro estudiantil tiene una altura de $M_i$?

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 500$). A continuación, se presenta la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene tres enteros, $N$, $Q$ y $C$ ($1 \le N \le 500$, $1 \le Q \le 10^6$, $1 \le C \le 10^9$).

La $i$-ésima de las siguientes $N$ líneas contiene dos enteros $L_i$ y $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$).

La $i$-ésima de las siguientes $Q$ líneas contiene un único entero $M_i$ ($1 \le M_i \le 10^9$).

Los $L_i$ son distintos entre sí y no existen dos edificios diametralmente opuestos ($i$ y $j$ tales que $L_i = L_j + C/2$).

Se garantiza que la suma de $N$ en todos los casos de prueba no excede $500$.

Se garantiza que la suma de $Q$ en todos los casos de prueba no excede $10^6$.

Salida

Imprima $Q$ líneas: el costo mínimo para conectar todos los edificios cuando el centro estudiantil tiene una altura de $M_1, \dots, M_Q$ respectivamente.

Puntuación

Sea $\sum N$ la suma de $N$ en todos los casos de prueba y $\sum Q$ la suma de $Q$ en todos los casos de prueba.

• (15 puntos) $\sum N, \sum Q \le 80$ y $0 \le L_i < C/2$ para todo $i$.
• (15 puntos) $\sum N, \sum Q \le 80$.
• (15 puntos) $\sum N \le 80$ y $0 \le L_i < C/2$ para todo $i$.
• (10 puntos) $\sum N \le 80$.
• (15 puntos) $\sum Q \le 500$ y $0 \le L_i < C/2$ para todo $i$.
• (10 puntos) $\sum Q \le 500$.
• (10 puntos) $0 \le L_i < C/2$ para todo $i$.
• (10 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

6
10
5
7
998244352

Nota

Una forma óptima de conectar los edificios para las preguntas en el primer caso de prueba se muestra a continuación:

Para el segundo caso de prueba, el costo para conectar el centro estudiantil con el único otro edificio es $|1 - 998244353| = 998244352$.