Problem E
Ski

It’s the holidays! There is a famous ski slope you would like to try this year.

The slope, which runs $N$ meters long from west to east, has its height measured at 1-meter intervals from its beginning at the west, producing $N + 1$ height measurements $H(i)$, where $0 \le i \le N$. It is divided into $N$ segments numbered from $0$ to $N - 1$ such that the west and east endpoints of segment $i$ have heights $H(i)$ and $H(i + 1)$ respectively. Each segment is 1 meter long. It is still snowing, so these heights are measured often and can change.

To minimize the risk of accidents, you are only allowed to ski towards the east on this slope. For transport, there is a ski lift that stops at all $N + 1$ segment endpoints along the slope and allows you to go in either direction. Going eastward is free, but the resort charges for going west since climbing requires energy. When passing segment $i$ while going west on the ski lift, you must pay $H(i) + H(i + 1)$ dollars.

You have a certain budget $K$ for your ski trip, which limits how far you can go along the ski slope. Fortunately, you can book a cabin at $X$ meters from the beginning of the slope so you don’t have to take the ski lift all the way back to the beginning, only back to your cabin.

You decide that you only want to do one non-stop ski run, but it has to be as fun as possible. Each segment $i$ of the slope has a fun factor $(H(i) - H(i + 1))^2$ if $H(i) \ge H(i + 1)$ and $-(H(i) - H(i + 1))^2$ otherwise. The fun factor of your ski run is the sum of the fun factors of the segments you skied. You start at the beginning of the slope, so you can take the lift eastward to any point on the slope and ski eastward from there, but after that you must return to your cabin via the ski lift.

What is the fun factor of the best possible ski run given your budget $K$ and your cabin at position $X$?

Input

• The first line contains two integers, $N$ and $Q$. $N$ is the length of the ski slope and $Q$ is the number of queries.

• The second line contains $N + 1$ integers. The $i$-th integer is $H(i)$, the height of the slope at the position $i$ meters east of the beginning.

• The next $Q$ lines contain one query each. Each query begins with an integer $T \in \{ 0, 1\} $.

  • If $T = 0$, two integers $i$ ($0 \le i \le N$) and $V$ follow. The height of the ski slope at $i$ meters east of the beginning ($H(i)$) has changed to $V$.

  • If $T = 1$, two integers $X$ ($0 \le X \le N$) and $K$ ($0 \le K \le 10^{12}$) follow.

For all testcases, $1 \le N, Q \le 500\, 000$ and $0 \le H(i) \le 10^6$ at all times for $0 \le i \le N$.

Output

For each query that begins with $T = 1$, output the fun factor of the best possible ski run if you book your cabin at $X$ meters east of the beginning and have a budget of $K$ dollars.

Visualizations

Figure 1: Queries in Sample Input 1

Figure 2: Queries in Sample Input 2

Figure 3: Queries in Sample Input 3

10 1
1 5 7 9 6 8 5 7 4 6 3
1 2 100

24

10 5
9 6 8 5 1 2 4 1 5 4 6
1 2 30
0 6 3
1 2 30
0 7 0
1 2 30

30
30
37

10 3
3 8 4 5 2 7 0 9 7 5 0
1 0 60
0 6 9
1 0 60

49
24