長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられます。次のクエリを実行するプログラムを作成してください:

• 0 l r x: すべての $l \le i \le r$ について、$A_i$ を $\max(A_i, x)$ に代入する。
• 1 l r: $\max\left(0, \max_{l \le u \le v \le r} \left(\sum_{i=u}^{v} A_i\right)\right)$ を出力する。

入力

最初の行には、数列の長さ $N$ とクエリの個数 $Q$ を表す2つの整数が含まれます。

2行目には、$N$ 個の整数 $A_1, A_2, \ldots, A_N$ が与えられます。これらは数列 $A$ の初期値です。

続く $Q$ 行には、それぞれ上記の形式のクエリが記述されます。

出力

1 l r の形式のクエリごとに、答えを1行に出力してください。

入出力例

入力 1

14 14
-3 2 1 -2 3 -4 3 -5 -1 -2 3 -5 1 5
1 3 9
0 1 14 -4
1 1 14
0 3 11 -1
1 2 8
0 3 10 -1
1 4 7
0 6 9 2
1 1 14
0 10 10 7
1 1 14
0 6 9 4
0 1 5 2
1 1 14

出力 1

3
6
7
5
18
26
39