Biến đổi khí hậu

Để nghiên cứu về tác động của biến đổi khí hậu, An tiến hành một thí nghiệm với kịch bản như sau: An chọn một số vị trí trên bản đồ và đánh số từ 1 cho đến hết. Ban đầu, độ cao so với mực nước biển của tất cả các vị trí là 0. An sẽ thực hiện n tác động biến đổi khí hậu được đánh số từ 1 đến n. Tác động thứ i ($1 \le i \le n$) sẽ làm thay đổi độ cao của các vị trí có số hiệu từ $l_i$ đến $r_i$ lần lượt theo quy tắc: vị trí $l_i$ sẽ tăng độ cao thêm $x_i$, vị trí $l_i + 1$ sẽ giảm bớt độ cao $x_i$, vị trí $l_i + 2$ sẽ tăng độ cao thêm $x_i$ và tiếp tục cho đến vị trí $r_i$.

Yêu cầu: Hãy giúp An xác định độ cao của m vị trí $p_1, p_2, \dots, p_m$ sau khi thực hiện n tác động.

Vào từ tệp văn bản CAU2.INP gồm:

• Dòng thứ nhất chứa hai số nguyên dương m và n ($m \le 10^3$, $n \le 10^3$);
• Trong m dòng tiếp theo, dòng thứ i chứa số nguyên dương $p_i$ ($p_i \le 10^9$, $1 \le i \le m$);
• Trong n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương $l_i$, $r_i$ và $x_i$ ($l_i \le r_i \le 10^9$, $x_i \le 10^3$, $1 \le i \le n$).

Ghi ra tệp văn bản CAU2.OUT gồm m dòng, dòng thứ i ghi độ cao của vị trí $p_i$ ($1 \le i \le m$) tìm được.

• $m \le 10^3$, $n \le 10^3$;
• $p_i \le 10^9$;
• $l_i \le r_i \le 10^9$, $x_i \le 10^3$.