Perdu dans le plan des bâtiments du MIT, Busy Beaver a décidé de concevoir un plan plus simple : le Majestic Interconnected Toroid Institute of Technology (MITIT)...

Il y a $N$ bâtiments principaux numérotés $1, \dots, N$ disposés sur un cercle de circonférence $C$. Le $i$-ième bâtiment est situé à la position $L_i$ ($0 \le L_i < C$) le long du cercle et a une hauteur $H_i$. Il existe un bâtiment supplémentaire, le centre étudiant, situé au centre du cercle, dont la hauteur n'est pas encore décidée.

Busy Beaver souhaite relier les $N+1$ bâtiments avec des tunnels rectilignes de telle sorte que n'importe quel bâtiment puisse atteindre n'importe quel autre bâtiment en utilisant ces tunnels. Un tunnel peut être modélisé comme un segment de droite (dans un plan à 2 dimensions) reliant deux bâtiments. Tous ces tunnels seront à la même altitude, donc leurs segments de droite correspondants ne doivent pas s'intersecter (sauf aux extrémités). Pour une raison quelconque, le coût de construction d'un tunnel entre deux bâtiments de hauteurs $h_1$ et $h_2$ est égal à $|h_1-h_2|$.

Busy Beaver a $Q$ questions $M_1, \dots, M_Q$, où il se demande : quel est le coût minimal possible pour relier tous les bâtiments si le centre étudiant a une hauteur de $M_i$ ?

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 500$). La description des cas de test suit.

La première ligne de chaque cas de test contient trois entiers, $N$, $Q$ et $C$ ($1 \le N \le 500$, $1 \le Q \le 10^6$, $1 \le C \le 10^9$).

La $i$-ième des $N$ lignes suivantes contient deux entiers $L_i$ et $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$).

La $i$-ième des $Q$ lignes suivantes contient un seul entier $M_i$ ($1 \le M_i \le 10^9$).

Les $L_i$ sont distincts deux à deux et il n'existe pas deux bâtiments diamétralement opposés ($i$ et $j$ tels que $L_i = L_j+C/2$).

Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas $500$.

Il est garanti que la somme de $Q$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Affichez $Q$ lignes : le coût minimal pour relier tous les bâtiments lorsque le centre étudiant a une hauteur de $M_1, \dots, M_Q$ respectivement.

Sous-tâches

Soit $\sum N$ la somme de $N$ sur tous les cas de test et $\sum Q$ la somme de $Q$ sur tous les cas de test.

• ($15$ points) $\sum N, \sum Q \le 80$ et $0 \le L_i < C/2$ pour tout $i$.
• ($15$ points) $\sum N, \sum Q \le 80$.
• ($15$ points) $\sum N \le 80$ et $0 \le L_i < C/2$ pour tout $i$.
• ($10$ points) $\sum N \le 80$.
• ($15$ points) $\sum Q \le 500$ et $0 \le L_i < C/2$ pour tout $i$.
• ($10$ points) $\sum Q \le 500$.
• ($10$ points) $0 \le L_i < C/2$ pour tout $i$.
• ($10$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

6
10
5
7
998244352

Remarque

Une manière optimale de relier les bâtiments pour les questions du premier cas de test est illustrée ci-dessous :

Pour le second cas de test, le coût pour relier le centre étudiant avec le seul autre bâtiment est $|1-998244353| = 998244352$.