배열과 연산

정수 $n$개로 이루어진 배열 $a$가 있다. 연산은 세 가지 종류가 있다.

• "1 $l$ $r$ $x$": $[l, r]$에 속한 각 $i$에 대해 $a_i$를 $a_i + x$로 바꾼다.
• "2 $l$ $r$": $[l, r]$에 속한 각 $i$에 대해 $a_i$를 $\lfloor \sqrt{a_i} \rfloor$로 바꾼다.
• "3 $l$ $r$": $[l, r]$에 속한 모든 $i$에 대해 $a_i$의 합을 구해 출력한다.

주어진 연산을 처리하면서 모든 3번 연산의 답을 출력한다.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. ($1 \le n, q \le 10^5$) 둘째 줄에 $n$개의 정수 $a_1, \ldots, a_n$이 주어진다. 이어서 $q$개의 줄에 걸쳐 각 줄에 연산이 하나씩 주어진다.

$1 \le a_i, x \le 10^5$, $1 \le l \le r \le n$이 보장된다.

3번 연산마다 구한 합을 한 줄에 하나씩 출력한다.