Dũng rất thích sưu tầm heo đất và nuôi chúng. Để có đủ tiền để đi tham quan các địa điểm du lịch nỗi tiếng của Ninh Bình trong đợt thi DH và ĐBBB 2017, Dũng sưu tầm được \(N\) con heo đất và đánh số từ 1 đến \(N\), ban đầu chúng đều rỗng. Mỗi ngày cậu ta chọn ra 1 cặp (\(L, R\)) và bỏ vào mỗi heo đất trong đoạn có chỉ số từ \(L\) đến \(R\) 1 đồng tiền. Cậu ta thực hiện như vậy trong \(M\) ngày.

Yêu cầu: Sau \(M\) ngày, Dũng muốn biết có bao nhiêu hộp đựng tiền có ít nhất \(x\) đồng tiền trong đó và cậu ta có \(Q\) truy vấn như vậy.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) (\(N\): số hộp tiền, \(M\): số ngày mà Dũng thực hiện);
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(L\) và \(R\);
• Dòng thứ \(M + 2\) chứa một số nguyên \(Q\) là số lượng truy vấn;
• \(Q\) dòng tiếp theo chứa một số nguyên dương \(x\) (\(x ≤ M\)) của từng truy vấn.

Kết quả:

• Ghi ra gồm \(Q\) dòng, mỗi dòng chứa số nguyên là kết quả của truy vấn tương ứng.

Input

7 4
1 3
2 5
1 2
5 6
4
1
7
4
2

Output

6
0
0
4

Ràng buộc

• Có 30% số test ứng với 30% số điểm có \(N,M,Q\le10^2\)
• Có 30% số test ứng với 30% số điểm có \(N,M,Q\le10^4\)
• Có 40% số test ứng với 40% số điểm có \(N,M,Q\le10^5\)

Cho ba số nguyên \(a\), \(b\) và \(m = 10^9 + 7\). Hãy tính:

• \((a + b) \ \% \ m\),
• \((a - b) \ \% \ m\),
• \((a \times b) \ \% \ m\),
• \((a \ / \ b) \ \% \ m\).

Trong đó \(\%\) là phép chia lấy phần dư.

Input

• Chứa hai số nguyên \(a\) và \(b\) \((0 \leq a < m, 1 \leq b < m)\).

Output

• Gồm bốn dòng, mỗi dòng gồm một số nguyên là đáp án cho từng phép toán.

Example

6 3

9
3
18
2

123456789 987654321

111111103
135802475
259106859
203935601

Bạn được cho 1 danh sách \(A\) gồm \(n\) số nguyên và một số nguyên \(m\). Bạn được quyền thực hiện các thao tác thỏa mãn điều kiện sau:

• Không được thay đổi thứ tự các phần tử của danh sách này.
• Bạn phải chèn thêm một trong hai dấu \(\{+,-\}\) vào giữa các phần tử của tập hợp.
• Có \(n-1\) khoảng giữa các phần tử mà bạn có thể chèn dấu vào.

Ví dụ, với \(a=[3,4,5]\) bạn có thể thêm vào các dấu biến nó trở thành biểu thứ \(3+4-5\). Giá trị của biểu thức này là \(2\).

Hãy liệt kê hết các cách chèn dấu mà giá trị của biểu thức được tạo ra là \(m\).

Input

• Dòng thứ nhất chứa hai số nguyên \(n\), \(m\) \((1 \leq n < 22, |m| \leq 5 * 10^9)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(|A_i| \leq 10^9\))

Output

• In ra nhiều dòng, mỗi dòng là một biểu thức hợp lệ. Các biểu thức in tăng dần theo thứ tự từ điển. Xem ví dụ để in đáp án được chính xác.

Example

5 0
0 -4 -1 0 -3 

0+4-1+0-3
0+4-1-0-3
0-4+1+0+3
0-4+1-0+3