Apology

There is no guarantee that solutions in languages such as Python will pass.

Problem Statement

You are given a sequence $A = \{ a_1, a_2, ... , a_N \} \ $ with $N$ elements.

A total of $Q$ queries of the following 2 types are given. Process them in order.

• set $i \ x$

  • Change the value of $a_i$ to $x$.



• max $l_1 \ l_2 \ r_1 \ r_2$

  • Output the value of $\displaystyle \text{range_max}(l_1, l_2, r_1, r_2) \ = \max_{(l_1 \ \le \ l \ \le \ l_2) \ \land \ (r_1 \ \le \ r \ \le \ r_2) \ \land \ (l \ \le \ r)} \sum_{k = l}^{r} a_k \ $.

Input

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

The first line contains the integer $N$, the length of the sequence, and the integer $Q$, the number of queries, in this order, separated by a space.

The second line contains $N$ space-separated integers, the $i$-th $(1 \le i \le N)$ of which represents the initial value of $a_i$.

The $i$-th $(1 \le i \le Q)$ of the following $Q$ lines contains the $i$-th query.

Each query is given in one of the following formats:

• set $i \ x$

• max $l_1 \ l_2 \ r_1 \ r_2$

That is, each query has one of the formats above.

The input consists of $Q + 2$ lines in total and satisfies the following constraints.

• All input values are integers.
• $1 \le N, Q \le 10^5$
• $-10^9 \le a_i \le 10^9 \ \ (1 \le i \le N)$
• set query
  • $1 \le i \le N$
  • $-10^9 \le x \le 10^9$
• max query
  • $1 \le l_1, l_2, r_1, r_2 \le N$
  • $(l_1 \le l_2) \ \land \ (r_1 \le r_2) \ \land \ (l_1 \le r_2)$
    • ($\iff (l_1 \le l \le l_2) \ \land \ (r_1 \le r \le r_2) \ \land \ (l \le r) \ $ is satisfied by at least 1 pair $(l, r)$)
• There is at least 1 max query.

Output

For each max query, output the value of $\text{range_max}(l_1, l_2, r_1, r_2) \ $, separated by newlines.

Sample

5 6
1 2 -3 -4 5
max 1 2 4 5
max 1 3 2 5
max 3 4 1 5
max 1 5 3 4
set 1 -10
max 1 5 1 1

1
3
1
0
-10

3 5
1000000000 1000000000 1000000000
max 1 3 1 3
set 1 -1000000000
set 2 -1000000000
set 3 -1000000000
max 1 1 3 3

3000000000
-3000000000