题目背景

Mirko 厌倦了为了各种任务去实现各种数据结构。所以，他决定写一个终极数据结构去操纵他最喜欢的数字序列。

快来帮助他吧！

Mirko 会给你他的数列，以及一系列你必须执行的操作。每个询问要么询问关于数列的信息，要么修改现有的数列。下面列出了所有可能的操作类型。

题目描述

给定一个数列 $f$ ，有以下操作。

设数列当前长度为 $n$。

查询种类|描述| :-:|:-:|:-: 1 A B X| $f_i=X(A \le i \le B)$ 2 A B X| $f_i+=(i-A+1) \times X(A \le i \le B)$ 3 C X| $f_{i+1}=f_i(C \le i \le n)$ $f_C=X$ 4 A B| 求$\sum^B_{i=A}f_i$

输入格式

第一行两个正整数 $n$ , $Q$，分别表示数列初始长度和操作数量。

第二行 $n$ 个非负整数表示初始数列。

接下来 $Q$ 行每行各包含一个如上询问。

输出格式

对于每一个 $4$ 号操作，输出一行答案。

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

4
0
25

1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4

17
27
100
37

提示

数据规模及约定

设当前数列长 $t$。

对于 $100\%$ 的数据 $1 \le n$ , $Q \le 1 \times 10^5$ , $f_i \le 1 \times 10^5$ , $1 \le X \le 100$ , $1 \le A \le B \le t$ , $1 \le C \le t + 1$。

说明

本题满分 $130$ 分。

译自 COCI2010-2011 CONTEST #7 T6 UPIT。