Description

Given a sequence $f$, the following operations are supported.

Let the current length of the sequence be $n$.

Input Format

The first line contains two positive integers $n$ and $Q$, representing the initial length of the sequence and the number of operations.

The second line contains $n$ non-negative integers, representing the initial sequence.

The next $Q$ lines each contain one query as described above.

Output Format

For each type $4$ operation, output one line with the answer.

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

Constraints

Let the current sequence length be $t$.

For $100\%$ of the testdata: $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$.

Notes

This problem is worth $130$ points in total.

Translated from COCI2010-2011 CONTEST #7 T6 UPIT.

Translated by ChatGPT 5