5003 - 【模板】根号线段树

给定一个长度为n的序列a_1,a_2,\cdots,a_n，你需要维护m个操作，每个操作都是其中一个：

1. 将区间[l,r]每个数都加上k
2. 将区间[l,r]每个数都开平方根（向下取整）
3. 求出区间[l,r]内每个数之和

第一行包含两个整数n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含n个用空格分隔的整数，其中第i个数字表示a_i。

接下来m行，每行包含3或4个整数，表示一个操作，具体如下：

1. 1 l r k：将区间[l,r]内每个数加上 k。
2. 2 l r：将区间[l,r]每个数都改成开平方根（向下取整）。
3. 3 l r：输出区间[l,r]内每个数的和。

输出包含若干行整数，即为所有操作3的结果。

1\leq n,m\leq10^5,1\leq a_i,k\leq 10^5

没有部分分！