Trong dịp lễ giáng sinh, siêu thị ABC có chính sách giảm giá ~n~ mặt hàng. Các mặt hàng được trưng bày theo thứ tự từ trái qua phải với mức giá ưu đãi là ~p_i~, với số lượng không giới hạn với mỗi loại mặt hàng. Có ~m~ khách hàng thân thiết vô cùng yêu thích chương trình giảm giá này, người thứ ~i~ mang tới số tiền là ~t_i~ và sẽ đi từ vị trí ~l_i~ tới vị trí ~r_i~. Tại mỗi vị trí, người này sẽ cố gắng mua nhiều nhất số hàng có thể tới khi không còn đủ tiền mua.

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

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n, m~ ~(n, m \le 2 \cdot 10^5)~

• Dòng thứ ~2~ chứa ~n~ số nguyên ~p_1, p_2, \dots, p_n~ là giá tiền của ~n~ mặt hàng theo thứ tự.

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~t_i, l_i, r_i~ xác định số tiền và khoảng di chuyển của người thứ ~i~. ~(p_i, t_j \le 10^{18})~

Output

~m~ số nguyên tương ứng số tiền còn lại của ~m~ người theo thứ tự trong input.

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