Problem Statement

You are given an array $A=(A_0,A_1,...,A_{N-1})$ of length $N$. Here, each $A_i$ is an integer greater than or equal to $0$.

Process a total of $Q$ queries of the following $3$ types. Here, $\text{isqrt}(x)$ is the function that returns the integer part of $\sqrt{x}$, that is, $\text{isqrt}(x) := \left\lfloor \sqrt{x}\right\rfloor$.

• 0 l r : Output $\ A_l+A_{l+1}+...+A_{r-1}$.
• 1 l r x : Assign $x$ to $\ A_l,A_{l+1},...,A_{r-1}$.
• 2 l r : Apply $\text{isqrt}$ to all of $\ A_l,A_{l+1},...,A_{r-1}$. That is, for every $i$ satisfying $l \le i < r$, replace $A_i$ with $\text{isqrt}(A_i)$.

Constraints

• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $0 \le A_i \le 10^9$
• $0 \le l \le r \le N$
• $0 \le x\le 10^9$
• All input values are integers.

Input

$N$ $Q$
$A_0$ $A_1$ ... $A_{N-1}$
$\text{query}_1$
$\text{query}_2$
...
$\text{query}_Q$

Here, $\text{query}_i$ represents the $i$-th query and is given in one of the following formats.

$0 ~ l ~ r$

$1 ~ l ~ r ~ x$

$2 ~ l ~ r$

Output

Let $k$ be the number of queries of the first type. Output $k$ lines. On the $i$-th line, output the answer to the $i$-th query of the first type.

Sample

6 4
1 2 3 4 5 6
0 1 4
1 0 3 10
2 1 3
0 1 4

9
10