Shopping dịp lễ Giáng sinh

Vào dịp lễ Giáng sinh, siêu thị Winmart tổ chức chương trình khuyến mãi vô cùng hấp dẫn dành cho \(n\) mặt hàng hot nhất mùa. Các mặt hàng này được xếp từ trái sang phải theo thứ tự với mức giá đặc biệt ưu đãi là \(p_i\) cho mỗi sản phẩm. Số lượng mỗi mặt hàng là không giới hạn, sẵn sàng đáp ứng mọi nhu cầu của các khách hàng thân thiết.

Chương trình khuyến mãi đã thu hút rất nhiều sự chú ý, đặc biệt là từ \(m\) khách hàng VIP --- những người không chỉ yêu thích mua sắm mà còn có niềm đam mê săn khuyến mãi. Mỗi khách hàng \(i\) đã chuẩn bị cho mình một số tiền là \(t_i\) và sẽ bắt đầu hành trình mua sắm của mình từ vị trí \(l_i\) đến \(r_i\) trên kệ hàng.

Trong hành trình này, mỗi khách hàng sẽ "săn" nhiều nhất có thể các món hàng trong phạm vi đã định cho đến khi số tiền không đủ để mua thêm. Họ không ngại chi tiêu, nhưng cũng muốn tiết kiệm một khoản để tiếp tục hành trình mua sắm các sản phẩm khác trong tương lai. Tại mỗi vị trí lần lượt từ \(l\) đến \(r\), họ sẽ cố gắng mua hết tất cả các sản phẩm có thể sau đó mới chuyển đến kệ hàng tiếp theo.

Yêu cầu: Hãy giúp siêu thị Winmart tính toán số tiền còn lại của từng khách hàng VIP sau khi họ đã thoả mãn sở thích mua sắm của mình.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) \((n, m \leq 2 \times 10^5)\) --- số lượng mặt hàng và số lượng khách hàng VIP.
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\) \((1 \leq p_i \leq 10^9)\) --- giá tiền của từng mặt hàng theo thứ tự từ trái sang phải. Các sản phẩm này được chọn lọc kỹ lưỡng, đa dạng từ đồ gia dụng, thời trang, đến các thiết bị công nghệ cao cấp.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(t_i, l_i, r_i\) \((1 \leq l_i \leq r_i \leq n, 1 \leq t_i \leq 10^{18})\) --- số tiền ban đầu của khách hàng \(i\) và phạm vi kệ hàng mà họ sẽ khám phá.

Output

Ghi ra file \(m\) số nguyên, mỗi số thể hiện số tiền còn lại của khách hàng tương ứng sau khi đã hoàn thành hành trình mua sắm của mình.

Example

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

2
0
1

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n, m \leq 5000\).
• Có \(15\%\) số test tương ứng với \(15\%\) số điểm có \(p_{i} \leq p_{i + 1}\) với \(i = 1..n - 1\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(p_{i} \geq p_{i + 1}\) với \(i = 1..n - 1\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.