Let array a1,...,an, (1<=n<=10^6)

3 kinds of quarries, m in total (1<=m<=10^6)

1 l r k: add k to al,...,ar 2 l r k: change ai (l<=i<=r) in to max(ai,k) 3 l r: print max(al,...,ar)

I think it could be done it at mlogn by segment tree. How can I?