• Source: Đề thi chính thức - Trường THPT Nguyễn Thị Minh Khai (Hà Nội).

John là một người rất mê đồ ngọt. Anh đang có ~n~ lọ thủy tinh trống. Để giảm lượng kẹo tiêu thụ, mỗi ngày anh sẽ bỏ vào lọ thứ ~i~, ~x~ viên kẹo và anh ấy làm vậy trong ~m~ ngày. Sau mỗi một ngày, John lại thắc mắc lọ thủy tinh có nhiều kẹo nhất là lọ nào trong số các lọ kẹo từ ~l~ đến ~r~. Các bạn hãy giúp John với!

Yêu cầu: Cho biết số kẹo bỏ vào các lọ trong ~m~ ngày. Sau mỗi ngày em hãy giúp John tìm ra lọ có nhiều kẹo nhất trong số các lọ từ ~l~ đến ~r~ và in ra số kẹo đó.

Input Specification

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm các số nguyên ~i~ ~(1 \le i \le n)~, ~x~ ~(1 \le x \le 10^4)~, ~l~ và ~r~ ~(1 \le l \le r \le n)~.

Output Specification

• In ra kết quả trên ~m~ dòng, mỗi dòng gồm một số nguyên là số kẹo nhiều nhất trong các lọ từ ~l_k~ đến ~r_k~ sau ngày thứ ~k~ ~(1 \le k \le m)~.

Sample Case(s)

Input #1:

4 3
1 10 2 3
1 5 1 3
2 4 3 3

Output #1:

0
15
0

Explanation:

• Số kẹo trong các lọ sau ngày ~1~ là ~10, 0, 0, 0~.
• Số kẹo trong các lọ sau ngày ~2~ là ~15, 0, 0, 0~.
• Số kẹo trong các lọ sau ngày ~3~ là ~15, 4, 0, 0~.