A few days ago, I was solving a contest, where I found a problem, that I couldn't solve there.

You have got an array, size of *N* < = 10^{5}, and you are recieving up to M<=10^5 queries of the three types:

1 l r d -- increase every element at the segment [l;r] by t, i.e. *X* + = *t*

2 l r -- square root every element at the segment and round all of them down, *X* = [*sqrt*(*X*)]

3 l r -- get the sum at the segment

I tried several approaches, but none worked. If someone has some good idea, give me a clue.

p.s. messing around with the CF post editor :(

Edit: Sorry, forgot to mention: each *X* < = 10^{5}