給你一個長度為$N$的序列$a_1, a_2, ..., a_n$，以及$Q$個操作，操作有以下幾種：

1. 把一個區間$[l, r]$的每個數字都加上$x$。

2. 問你一個區間$[l, r]$的最大值。

輸入說明

第一行包含兩個正整數 $N$、$Q$，分別表示序列長度為 $N$ 以及有 $Q$ 筆操作。

第二行包含 $N$ 個正整數，依序表示 $a_1$ 到 $a_N$。

接下來的$Q$ 行，每行為下列兩種操作之一：

$1\ l\ r\ x$：把$[l, r]$加上$x$。

$2\ l\ r$：詢問$[l, r]$的最大值。

對於 $40\%$ 的測試資料，$N,Q \le 2000$

對於 $100\%$ 的測試資料，$1 \le N,Q \le 10^5$、$1 \le a_i \le 10^9$、$1 \le x \le 10^4$、$1 \le l \le r \le N$

輸出說明

對於每個詢問，輸出一個整數，表示該區間的最大值。

範例輸入

6 3
8 7 1 2 2 8
2 3 6
1 2 5 7
2 3 6

範例輸出

8
9