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.

Dữ liệu:

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

• Dòng thứ 2 chứa \(n\) số nguyên \(p_1,p_2,…,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≤10^{18})\)

Kết quả:

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

Ràng buộc:

• 50% số test có \(n, m≤5000; p_i,t_i≤10^9\)

Sample Input

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

Sample Output

2
0
1