#228. 基础数据结构练习题

sylvia 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。

在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。

给出一个长度为 $n$ 的数列 $A$，接下来有 $m$ 次操作，操作有三种：

1. 对于所有的 $i \in [l,r]$，将 $A_i$ 变成 $A_i+x$。
2. 对于所有的 $i \in [l,r]$，将 $A_i$ 变成 $\lfloor\sqrt{A_i}\rfloor$。
3. 对于所有的 $i \in [l,r]$，询问 $A_i$ 的和。

作为一个不怎么熟练的初学者，sylvia 想了好久都没做出来。而可怜酱又外出旅游去了，一时间联系不上。于是她决定向你寻求帮助：你能帮她解决这个问题吗。

输入格式

第一行两个数：$n, m$。

接下来一行 $n$ 个数 $A_i$。

接下来 $m$ 行中，第 $i$ 行第一个数 $t_i$ 表示操作类型：

• 若 $t_i = 1$，则接下来三个整数 $l_i, r_i, x_i$，表示操作一。
• 若 $t_i = 2$，则接下来三个整数 $l_i, r_i$，表示操作二。
• 若 $t_i = 3$，则接下来三个整数 $l_i, r_i$，表示操作三。

输出格式

对于每个询问操作，输出一行表示答案。

样例一

输入：

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

输出：

5
6

样例二

见样例数据下载。

限制与约定

(注：上表空白处表示规模或约定与同组上一行保持一致，此为 UOJ 原题页面的表格呈现方式)

对于所有数据，保证有 $1 \leq l_i \leq r_i \leq n$，$1 \leq A_i, x_i \leq 10^5$。