Запутавшись в планировке зданий MIT, Busy Beaver решил спроектировать более простую схему — Majestic Interconnected Toroid Institute of Technology (MITIT)...

Имеется $N$ основных зданий, пронумерованных от $1$ до $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$ строк содержат по два целых числа $L_i$ и $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$).

Следующие $Q$ строк содержат по одному целому числу $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$ и $0 \le L_i < C/2$ для всех $i$.
• ($15$ баллов) $\sum N, \sum Q \le 80$.
• ($15$ баллов) $\sum N \le 80$ и $0 \le L_i < C/2$ для всех $i$.
• ($10$ баллов) $\sum N \le 80$.
• ($15$ баллов) $\sum Q \le 500$ и $0 \le L_i < C/2$ для всех $i$.
• ($10$ баллов) $\sum Q \le 500$.
• ($10$ баллов) $0 \le L_i < C/2$ для всех $i$.
• ($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$.