Sequence and Queries 28

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program that performs the following queries.

• 1 L R X: for every $L \le i \le R$, apply $A_i = A_i + X$.
• 2 L R: for every $L \le i \le R$, apply $A_i = \lfloor \sqrt{A_i} \rfloor$.
• 3 L R: print $A_L + A_{L+1} + \cdots + A_R$.

The first line gives the size of the sequence, $N$. ($1 \le N \le 100{,}000$)

The second line gives $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 100{,}000$)

The third line gives the number of queries, $M$. ($1 \le M \le 100{,}000$)

Each of the next $M$ lines contains one query. ($1 \le L \le R \le N$, $1 \le X \le 100{,}000$) At least one query of type 3 is given.

For each query of type 3, print its result on its own line.