Gió mạnh trên sa mạc làm độ cao của một triền cát dài thay đổi liên tục. Triền cát được chia thành các khoảng liên tiếp và đánh số từ ~1~ đến ~10^9~. Ban đầu, mọi khoảng đều có độ cao ~0~.

Có ~n~ cơn gió mạnh. Cơn gió thứ ~i~ tác động lên các khoảng từ ~l_i~ đến ~r_i~ với cường độ giật ~x_i~ và làm thay đổi độ cao như sau:

• khoảng ~l_i~ tăng thêm ~x_i~
• khoảng ~l_i+1~ giảm đi ~x_i~
• khoảng ~l_i+2~ tăng thêm ~x_i~
• … cứ luân phiên ~+x_i, -x_i, +x_i, -x_i~ cho đến ~r_i~.

Sau tất cả các cơn gió, cần trả lời độ cao hiện tại tại ~m~ vị trí được hỏi.

Yêu cầu

Với ~n~ thao tác gió dạng trên và ~m~ truy vấn vị trí ~q_j~, hãy xác định độ cao cuối cùng tại mỗi ~q_j~.

Dữ liệu

• Dòng đầu chứa ~2~ số nguyên ~n~ và ~m~ (~1 \le n, m \le 1000~).
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~l_i, r_i, x_i~ (~1 \le l_i \le r_i \le 10^9~, ~1 \le x_i \le 10^3~).
• Trong ~m~ dòng sau nữa, dòng thứ ~j~ chứa một số nguyên ~q_j~ (~1 \le q_j \le 10^9~).

Kết quả

Ghi ra ~m~ dòng, dòng thứ ~j~ là độ cao tại vị trí ~q_j~ sau khi đã áp dụng toàn bộ ~n~ cơn gió.

Ví dụ

Ví dụ 1

Input

2 6
1 6 7
3 7 2
1
2
3
6
7
8

Output

7
-7
9
-9
2
0

Giải thích

Ví dụ 1

• Gió 1: tác động ~[1,6]~, ~x=7~ → các vị trí ~1..6~ lần lượt: ~+7, -7, +7, -7, +7, -7~.
• Gió 2: tác động ~[3,7]~, ~x=2~ → các vị trí ~3..7~ lần lượt: ~+2, -2, +2, -2, +2~.

Cộng dồn:

• ~q=1~: chỉ có gió 1 → ~7~
• ~q=2~: chỉ có gió 1 → ~-7~
• ~q=3~: ~(+7) + (+2) = 9~
• ~q=6~: ~(-7) + (-2) = -9~
• ~q=7~: chỉ có gió 2 (tại ~7~ là dấu ~+~) → ~2~
• ~q=8~: không bị gió nào tác động → ~0~

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, m \le 1000~
• ~1 \le l_i \le r_i \le 10^9~
• ~1 \le x_i \le 10^3~
• ~1 \le q_j \le 10^9~