Cập nhật cấp số cộng trên đoạn

Cho mảng $A[1..n]$ khởi tạo toàn $0$. Bạn cần thực hiện $q$ thao tác cập nhật. Mỗi thao tác được mô tả bởi bốn số nguyên $l,r,a,d$: với mỗi chỉ số $i$ thỏa $l\le i\le r$, cộng giá trị $a+(i-l)·d$ vào $A[i]$. Nói cách khác, ta cộng vào đoạn $A[l..r]$ một cấp số cộng có số hạng đầu $a$, công sai $d$, và độ dài $r-l+1$.

Sau khi xử lý xong tất cả các thao tác, in ra giá trị cuối cùng của mảng $A$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Mỗi dòng trong $q$ dòng tiếp theo chứa bốn số nguyên $l,r,a,d$ mô tả một thao tác cập nhật.

Dữ liệu ra

In ra $n$ số nguyên $A[1],A[2],\dots ,A[n]$ trên một dòng, các số cách nhau bởi dấu cách.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le q\le 2·{10}^5$
• $1\le l\le r\le n$
• $-{10}^9\le a,d\le {10}^9$
• Giá trị cuối cùng của mỗi phần tử nằm trong kiểu số nguyên 64-bit có dấu.

Ví dụ

Ghi chú

Giải pháp ngây thơ duyệt từng phần tử trong $[l,r]$ cho mỗi thao tác có độ phức tạp $O(n·q)$ trong trường hợp xấu nhất, sẽ không kịp thời gian. Hãy nghĩ tới việc tổng quát hóa mảng hiệu cho các cập nhật cấp số cộng.