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?