D. DS Team Selection 2
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Before participating in IOI 2023, you need to solve the following practice problem.

You have a sequence $$$a$$$ of length $$$n$$$. You need to perform $$$q$$$ queries.

  1. Given $$$v$$$, change all $$$a_i$$$ to $$$\min(a_i, v)$$$.
  2. Change all $$$a_i$$$ to $$$a_i + i$$$.
  3. Given $$$l, r$$$, print the sum $$$\sum_{i=l}^r a_i$$$.

You may not go to IOI 2023, but the problem is still interesting to solve. Therefore, Little Cyan Fish asks you to solve it!

Input

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2 \times 10^5$$$).

The next line of the input contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$0 \leq a_i \leq 10^{12}$$$).

The next $$$q$$$ lines of the input describes all the queries in the following format:

  • $$$1$$$ $$$v$$$ ($$$0 \leq v \leq 10^{12}$$$): Change all $$$a_i$$$ to $$$\min(a_i, v)$$$.
  • $$$2$$$: Change all $$$a_i$$$ to $$$a_i + i$$$.
  • $$$3$$$ $$$l$$$ $$$r$$$ ($$$1 \leq l \leq r \leq n$$$): Print the sum $$$\sum_{i=l}^r a_i$$$.
Output

For each query of type $$$3$$$, output a single line contains a single integer, indicating the answer.

Example
Input
13 11
6 14 14 6 3 6 4 13 10 3 12 5 11
1 2
2
2
2
1 11
3 4 6
2
1 6
2
1 9
3 2 13
Output
33
107