Trên bàn có ~n~ chiếc đĩa được đánh số từ ~1~ đến ~n~. Ban đầu, đĩa thứ ~i~ chứa ~i~ viên kẹo. Trong ~m~ ngày tiếp theo, mỗi ngày có một bạn học sinh đến và thay đổi lại các viên kẹo ở một số đĩa. Ngày thứ ~j~, bạn học sinh thực hiện việc điều chỉnh như sau: bạn lấy bớt một vài viên kẹo hoặc thêm vào một vài viên kẹo mà bạn mang theo. Các bạn học sinh thống nhất với nhau rằng sau khi thay đổi, tất cả các đĩa từ ~l_j~ đến ~r_j~ đều có cùng số viên kẹo là ~c_j~. Bạn học sinh ~j~ chỉ thay đổi số kẹo trong các đĩa từ ~l_j~ đến ~r_j~, những đĩa còn lại bạn ấy không thay đổi.

Nếu tổng số kẹo hiện có trên các đĩa từ ~l_j~ đến ~r_j~ thừa hoặc thiếu so với số kẹo cần thiết để mỗi đĩa trong đoạn có đúng ~c_j~ viên, thì bạn học sinh sẽ: Lấy đi đúng số kẹo thừa, hoặc bổ sung đúng số kẹo còn thiếu.

Sau mỗi ngày, thầy Kiên muốn biết số lượng kẹo đã thay đổi so với ngày hôm trước sau khi bạn học sinh hôm đó đã lấy đi hay thêm vào. Hãy lập trình giúp thầy Kiên tính toán giá trị trên.

Dữ liệu vào

Đọc từ tệp văn bản XEPKEO.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n,m \le 10^5)~.

• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~l_j, r_j, c_j~ ~(1 \le l_j \le r_j \le n,\ 1 \le c_j \le 10^6)~.

Dữ liệu ra

Ghi ra tệp văn bản XEPKEO.OUT gồm ~m~ dòng.

Dòng thứ ~j~ ghi số lượng kẹo đã thay đổi sau khi bạn học sinh ~j~ thực hiện việc thêm vào hoặc lấy đi so với ngày trước đó.

Ví dụ

Giới hạn

• Subtask 1 (20%): ~n \le 1000,\ m \le 1000~.

• Subtask 2 (20%): ~c_j = c_1~ với mọi j ~(1 \le j \le m)~.

• Subtask 3 (20%): ~n \le 10000,\ m \le 1000~.

• Subtask 4 (20%): Không có ràng buộc gì thêm.