Để nghiên cứu tác động của biến đổi khí hậu, An chọn một số vị trí trên bản đồ và đánh số từ 1 trở đi. Ban đầu, độ cao so với mực nước biển của tất cả các vị trí bằng 0. An sẽ thực hiện n tác động (đánh số từ 1 đến n). Tác động thứ i (1 ≤ i ≤ n) làm thay đổi độ cao của các vị trí từ L_i đến R_i theo quy tắc xen kẽ: vị trí L_i tăng thêm X_i, vị trí L_i+1 giảm X_i, vị trí L_i+2 tăng X_i, … cho đến R_i.

Yêu cầu: Xác định độ cao tại m vị trí p₁, p₂, …, p_m sau khi thực hiện n tác động.

Input

Dòng 1: hai số nguyên dương m và n (m ≤ 10³, n ≤ 10³).

Dòng 2: m số nguyên dương, số thứ i là p_i (p_i ≤ 10⁹, 1 ≤ i ≤ m).

Trong n dòng tiếp theo: dòng thứ i chứa ba số nguyên dương L_i, R_i, X_i (L_i ≤ R_i ≤ 10⁹, X_i ≤ 10³, 1 ≤ i ≤ n).

Output

Gồm m dòng, dòng thứ i ghi độ cao tại vị trí p_i (1 ≤ i ≤ m).

Ví dụ

Input

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

Output

7
9
-9
2
0

Dòng 1: 5 2
m = 5: Chúng ta cần tính độ cao tại 5 vị trí.
n = 2: Sẽ có 2 tác động xảy ra.
Dòng 2: 1 3 6 7 8
Đây là 5 vị trí (p) mà chúng ta cần tìm độ cao cuối cùng.
Dòng 3: 1 6 7 (Tác động 1)
L₁ = 1, R₁ = 6, X₁ = 7.
Tác động này ảnh hưởng đến các vị trí từ 1 đến 6. Cụ thể:
Vị trí 1: tăng 7
Vị trí 2: giảm 7
Vị trí 3: tăng 7
Vị trí 4: giảm 7
Vị trí 5: tăng 7
Vị trí 6: giảm 7
Dòng 4: 3 7 2 (Tác động 2)
L₂ = 3, R₂ = 7, X₂ = 2.
Tác động này ảnh hưởng đến các vị trí từ 3 đến 7. Cụ thể:
Vị trí 3: tăng 2
Vị trí 4: giảm 2
Vị trí 5: tăng 2
Vị trí 6: giảm 2
Vị trí 7: tăng 2
1. Tại vị trí p = 1:
Tác động 1 (1 6 7): Vị trí 1 nằm trong đoạn [1, 6]. Khoảng cách từ L₁ là 1 - 1 = 0 (chẵn) -> tăng 7.
Tác động 2 (3 7 2): Vị trí 1 không nằm trong đoạn [3, 7] -> không ảnh hưởng.
Kết quả: 0 + 7 = 7.
2. Tại vị trí p = 3:
Tác động 1 (1 6 7): Vị trí 3 nằm trong đoạn [1, 6]. Khoảng cách từ L₁ là 3 - 1 = 2 (chẵn) -> tăng 7.
Tác động 2 (3 7 2): Vị trí 3 nằm trong đoạn [3, 7]. Khoảng cách từ L₂ là 3 - 3 = 0 (chẵn) -> tăng 2.
Kết quả: 0 + 7 + 2 = 9.
3. Tại vị trí p = 6:
Tác động 1 (1 6 7): Vị trí 6 nằm trong đoạn [1, 6]. Khoảng cách từ L₁ là 6 - 1 = 5 (lẻ) -> giảm 7.
Tác động 2 (3 7 2): Vị trí 6 nằm trong đoạn [3, 7]. Khoảng cách từ L₂ là 6 - 3 = 3 (lẻ) -> giảm 2.
Kết quả: 0 - 7 - 2 = -9.
4. Tại vị trí p = 7:
Tác động 1 (1 6 7): Vị trí 7 không nằm trong đoạn [1, 6] -> không ảnh hưởng.
Tác động 2 (3 7 2): Vị trí 7 nằm trong đoạn [3, 7]. Khoảng cách từ L₂ là 7 - 3 = 4 (chẵn) -> tăng 2.
Kết quả: 0 + 2 = 2.
5. Tại vị trí p = 8:
Tác động 1 (1 6 7): Vị trí 8 không nằm trong đoạn [1, 6] -> không ảnh hưởng.
Tác động 2 (3 7 2): Vị trí 8 không nằm trong đoạn [3, 7] -> không ảnh hưởng.
Kết quả: 0 + 0 = 0.