Ngày tết Nguyên Đán ai cũng đã có cho mình nhiều phong bao may mắn. Tũn và Tủm cũng vậy, mới mùng 1 tết mà chúng nó đã solo tiền lì xì với nhau để khẳng định độ “Rich Kid” của mình. Cả hai so xem đứa nào có nhiều tờ tiền khác loại hơn người đó sẽ chiến thắng , vì nhà rất giàu nên phong bao của Tũn toàn là chi phiếu nên nó đành ngậm ngùi chịu thua Tủm. Quá cay cú Tũn ta quyết định đứa ra một luật mới để cữu vãn cho danh hiệu “Rich Kid” của mình. Luật mới như sau :
+ Ban đầu Tũn có n phong bao , mỗi phong bao có giá trị là a[i] (1<=i<=n),
+ Vì mới là mùng 1 tết nên còn quá nhiều người lì, có q lượt lì xì mỗi lượt có dạng l và r và lx (có nghĩa là tăng tất cả các phong bao a[i] (l<=i<=r) lên một lượng lx,
+ Kết thúc tết ai có số lượng phong bao khác loại lớn hơn sẽ chiến thắng và phải công nhận đứa kia là “Rich Kid” ( hai phong bao gọi là khác nhau nếu giá trị của chúng khác nhau );
INPUT:
- Dòng đầu chứa số nguyên dương n và q (n, q<=10^5)
- Dòng tiếp theo chứa n số nguyên môt tả phong bao thứ chứa a[i] tiền (a[i]<=10^9);
- q dòng tiếp theo mỗi dòng chứa 3 số nguyên dương l, r và lx (lx<=10^9);
OUTPUT:
- Gồm một dòng duy nhất chứa số lượng phong bao khác nhau của Tũn.