19472번 - 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.

제한

힌트