Vì cảm thấy bối rối trước cách bố trí tòa nhà của MIT, Busy Beaver quyết định thiết kế một sơ đồ đơn giản hơn — Viện Công nghệ Hình xuyến Liên kết Majestic (MITIT)...

Có $N$ tòa nhà chính được đánh số từ $1, \dots, N$ nằm trên một đường tròn có chu vi $C$. Tòa nhà thứ $i$ nằm tại vị trí $L_i$ ($0 \le L_i < C$) dọc theo đường tròn và có chiều cao là $H_i$. Có thêm một tòa nhà nữa là trung tâm sinh viên, nằm tại tâm của đường tròn mà chiều cao vẫn chưa được quyết định.

Busy Beaver muốn kết nối $N+1$ tòa nhà bằng một số đường hầm thẳng sao cho bất kỳ tòa nhà nào cũng có thể đi đến bất kỳ tòa nhà nào khác thông qua các đường hầm này. Một đường hầm có thể được mô hình hóa thành một đoạn thẳng (trong mặt phẳng 2 chiều) nối hai tòa nhà. Tất cả các đường hầm này sẽ nằm ở cùng một độ cao, vì vậy các đoạn thẳng tương ứng của chúng không được cắt nhau (trừ các điểm đầu mút). Vì một lý do nào đó, chi phí xây dựng một đường hầm giữa hai tòa nhà có chiều cao $h_1$ và $h_2$ bằng $|h_1-h_2|$.

Busy Beaver có $Q$ câu hỏi $M_1, \dots, M_Q$, trong đó anh ấy tự hỏi: Chi phí tối thiểu để kết nối tất cả các tòa nhà là bao nhiêu nếu trung tâm sinh viên có chiều cao là $M_i$?

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $T$ ($1 \le T \le 500$). Tiếp theo là mô tả của các trường hợp thử nghiệm.

Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa ba số nguyên $N$, $Q$ và $C$ ($1 \le N \le 500$, $1 \le Q \le 10^6$, $1 \le C \le 10^9$).

Dòng thứ $i$ trong $N$ dòng tiếp theo chứa hai số nguyên $L_i$ và $H_i$ ($0 \le L_i < C$, $1 \le H_i \le 10^9$).

Dòng thứ $i$ trong $Q$ dòng tiếp theo chứa một số nguyên duy nhất $M_i$ ($1 \le M_i \le 10^9$).

Các $L_i$ đôi một khác nhau và không tồn tại hai tòa nhà đối xứng qua tâm (tức là không có $i$ và $j$ sao cho $L_i = L_j+C/2$).

Đảm bảo rằng tổng $N$ trên tất cả các trường hợp thử nghiệm không vượt quá $500$.

Đảm bảo rằng tổng $Q$ trên tất cả các trường hợp thử nghiệm không vượt quá $10^6$.

Dữ liệu ra

Xuất ra $Q$ dòng: chi phí tối thiểu để kết nối tất cả các tòa nhà khi trung tâm sinh viên có chiều cao lần lượt là $M_1, \dots, M_Q$.

Chấm điểm

Gọi $\sum N$ là tổng $N$ trên tất cả các trường hợp thử nghiệm và $\sum Q$ là tổng $Q$ trên tất cả các trường hợp thử nghiệm.

• ($15$ điểm) $\sum N, \sum Q \le 80$ và $0 \le L_i < C/2$ với mọi $i$.
• ($15$ điểm) $\sum N, \sum Q \le 80$.
• ($15$ điểm) $\sum N \le 80$ và $0 \le L_i < C/2$ với mọi $i$.
• ($10$ điểm) $\sum N \le 80$.
• ($15$ điểm) $\sum Q \le 500$ và $0 \le L_i < C/2$ với mọi $i$.
• ($10$ điểm) $\sum Q \le 500$.
• ($10$ điểm) $0 \le L_i < C/2$ với mọi $i$.
• ($10$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
10
5
7
998244352

Ghi chú

Một cách tối ưu để kết nối các tòa nhà cho các câu hỏi trong trường hợp thử nghiệm đầu tiên được thể hiện như sau:

Đối với trường hợp thử nghiệm thứ hai, chi phí để kết nối trung tâm sinh viên với tòa nhà duy nhất còn lại là $|1 - 998244353| = 998244352$.