题目背景

翻译自 CSES-1735 题。

题目描述

你的任务是维护一个包含 $n$ 个值的数组，并高效地处理以下几种类型的查询：

1. 将区间 $[a,b]$ 中的每个值增加 $x$。
2. 将区间 $[a,b]$ 中的每个值设置为 $x$。
3. 计算区间 $[a,b]$ 中的值的和。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组的大小和查询的数量。

第二行包含 $n$ 个整数 $t_1,t_2,…,t_n$：表示数组的初始内容。

接下来有 $q$ 行，每行描述一个查询。查询的格式有三种：

• 1 a b x：表示将区间 $[a,b]$ 中的每个值增加 $x$。
• 2 a b x：表示将区间 $[a,b]$ 中的每个值设置为 $x$。
• 3 a b：表示计算区间 $[a,b]$ 中的值的和。

输出格式

对于每个类型为 3 的查询，输出该区间内值的和。

样例

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

7
11
15

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$1 \leq t_i,x \leq 10^6$；

$1 \leq a \leq b \leq n$。