Săn xe ưu đãi

Nhân dịp đầu năm, showroom xe hơi XYZ tổ chức chương trình bán xe giảm giá cực lớn. Các mẫu xe được xếp theo thứ tự từ 1 đến \(n\), với mỗi mẫu xe có mức giá \(p_i\) (đơn vị triệu đồng).

Có \(m\) khách hàng lần lượt đến tham dự. Khách hàng thứ \(i\) mang theo số tiền \(t_i\) (triệu đồng), và quyết định chỉ tham khảo các mẫu xe từ vị trí \(l_i\) đến \(r_i\).

Tại mỗi mẫu xe, khách hàng sẽ mua được nhiều chiếc nhất có thể nếu còn đủ tiền, rồi mới tiếp tục sang mẫu xe kế tiếp trong khoảng được chọn. Việc mua xe diễn ra tuần tự từ trái sang phải.

Nhiệm vụ của bạn là xác định, sau chuyến săn xe, mỗi khách hàng còn lại bao nhiêu tiền.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \leq n, m \leq 2 \times 10^5\)) --- số lượng mẫu xe và số lượng khách hàng.
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \ldots, p_n\) (\(1 \leq p_i \leq 10^{18}\)) --- giá của từng mẫu xe (triệu đồng).
• \(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 mang theo và khoảng mẫu xe khách hàng chọn.

Output

• Gồm \(m\) dòng, mỗi dòng ghi số tiền còn lại của từng khách hàng sau khi mua xe, theo đúng thứ tự trong input.

Example

5 3
500 300 200 400 600
800 5 5
1070 1 4
700 3 5

200
70
100

Scoring

• \(50\%\) số test có \(n, m \leq 5000\), \(p_i, t_i \leq 10^9\).
• \(50\%\) số test có \(n, m \leq 2 \times 10^5\), \(p_i, t_i \leq 10^{18}\).