Array and Operations

You have an array $a$ with $n$ integers. There are three types of operations:

• "1 $l$ $r$ $x$": for each $i$ in $\[l, r]$, change $a\_i$ to $a\_i + x$;
• "2 $l$ $r$": for each $i$ in $\[l, r]$, change $a\_i$ to $\lfloor \sqrt{a\_i} \rfloor$;
• "3 $l$ $r$": sum up $a\_i$ for all $i$ in $\[l, r]$ and print the answer.

Your goal is to process the operations and print the answers of all type 3 operations.

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$). The second line contains $n$ integers $a\_1, \ldots, a\_n$. Then $q$ lines follow, each line describes an operation.

It is guaranteed that $1 \le a\_i, x \le 10^5$, $1 \le l \le r \le n$.

For each operation of type 3, print a single line containing the required sum.