Trong dịp lễ Giáng sinh, siêu thị ~ABC~ có chương trình giảm giá cho ~n~ mặt hàng. Các mặt hàng được trưng bày theo thứ tự từ trái sang phải, mặt hàng thứ ~i~ có mức giá ưu đãi là ~p_i~ và số lượng không giới hạn.

Có ~m~ khách hàng tham gia chương trình. Người thứ ~i~ mang theo số tiền ~t_i~ và đi lần lượt từ vị trí ~l_i~ đến vị trí ~r_i~. Tại mỗi vị trí, người này mua nhiều nhất số lượng mặt hàng có thể trước khi chuyển sang vị trí tiếp theo.

Yêu cầu: Hãy xác định số tiền còn lại của từng khách hàng sau khi mua hàng.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ ~(n,m \le 2 \times 10^5)~;

• Dòng thứ hai gồm ~n~ số nguyên ~p_1,p_2,\ldots,p_n~, là giá tiền của các mặt hàng theo thứ tự;

• Mỗi dòng trong ~m~ dòng tiếp theo gồm ba số nguyên ~t_i,l_i,r_i~, xác định số tiền và đoạn di chuyển của khách hàng thứ ~i~;

• Các giá trị thỏa mãn ~p_i,t_i \le 10^{18}~.

Output

Ghi ra ~m~ số nguyên tương ứng với số tiền còn lại của ~m~ khách hàng theo thứ tự trong dữ liệu vào.

Scoring

Sample Input 1

5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5

Sample Output 1

2
0
1