题目描述

专诸为了完成刺杀任务，天天在厨房练习藏剑于鱼肚的技巧，反复模拟刺杀动作。经过几个月的训练，他手法越来越熟练。

他记录了一个长度为 $n$ 的整数序列 $a_1 \sim a_n$，表示这一系列动作的初始熟练度。

在接下来的 $q$ 次训练调整中，每次操作可能是以下三种之一：

1. 1 l r x：将 $a_l \sim a_r$ 都加上 $x$；
2. 2 l r x：对于 $a_l \sim a_r$ 中的每个数，若它大于 $x$，则将其变成 $x$，否则不变；
3. 3 l r：询问 $\sum_{i=l}^{r} a_i$ 的值。

请处理所有操作，并输出每次类型 3 的询问结果。

输入格式

第一行两个整数 $n, q$（$1 \le n, q \le 10^4$）。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10$）。

接下来 $q$ 行，每行若干个整数，表示一个操作：

• 对于操作 1 和 2：输入格式为 op l r x
• 对于操作 3：输入格式为 op l r

其中满足 $1 \le l \le r \le n$，$1 \le x \le 10$。

输出格式

对于每个操作类型 3，输出一行一个整数，表示答案。

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

16

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

6
7