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차원 평면상의) 선분으로 모델링할 수 있습니다. 모든 터널은 같은 높이에 있으므로, 터널에 해당하는 선분들은 (끝점을 제외하고는) 서로 교차해서는 안 됩니다. 높이가 $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$개의 줄 중 $i$번째 줄에는 두 정수 $L_i$와 $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$)가 주어집니다.

다음 $Q$개의 줄 중 $i$번째 줄에는 정수 $M_i$ ($1 \le M_i \le 10^9$)가 주어집니다.

$L_i$는 서로 다르며, 지름의 양 끝에 위치한 두 건물(즉, $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

참고

첫 번째 테스트 케이스의 질문들에 대해 건물을 연결하는 최적의 방법 중 하나는 다음과 같습니다:

두 번째 테스트 케이스의 경우, 학생 회관과 유일한 다른 건물을 연결하는 비용은 $|1-998244353| = 998244352$입니다.