Description

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

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

Input Format

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

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

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

Output Format

对于每一个 $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

Hint

数据规模及约定

设当前数列长 $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。