謝罪

Python 等の言語で通る保証はないです。

問題文

要素数 $N$ の数列 $A = \{ a_1, a_2, ... , a_N \} \ $ が与えられます。

以下の 2 種類のクエリが合計 $Q$ 個与えられるので、それらを順番に処理してください。

• set $i \ x$

  • $a_i$ の値を $x$ に変更する



• max $l_1 \ l_2 \ r_1 \ r_2$

  • $\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 \ $ の値を出力する

入力

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

1 行目に数列の長さを表す整数 $N$ とクエリの数を表す整数 $Q$ がこの順で半角スペース区切りで与えられます。

2 行目には $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1 \le i \le N)$ の整数は、初期の $a_i$ の値を表します。

続く $Q$ 行のうちの $i$ 行目 $(1 \le i \le Q)$ には、$i$ 番目のクエリが与えられます。

各クエリは

• set $i \ x$

• max $l_1 \ l_2 \ r_1 \ r_2$

のいずれかの形式で与えられます。

入力は全部で $Q + 2$ 行となり、以下の制約を満たします。

• 入力は全て整数
• $1 \le N, Q \le 10^5$
• $-10^9 \le a_i \le 10^9 \ \ (1 \le i \le N)$
• set クエリ
  • $1 \le i \le N$
  • $-10^9 \le x \le 10^9$
• max クエリ
  • $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) \ $ を満たすような $(l, r)$ が 1 つ以上存在する）
• max クエリ は 1 つ以上存在する

出力

各 max クエリに対して、$\text{range_max}(l_1, l_2, r_1, r_2) \ $ の値を改行区切りで出力してください。

サンプル

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