시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 25 19 10 83.333%

문제

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.

예제 입력 1

5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5

예제 출력 1

5
6