在城市安静的一角，有一座退休老人公寓，住户们喜欢花时间观察楼前的草坪。草坪被划分为 $N$ 个区段，每个区段的草高为 $a_i$ 毫米，$1 \le i \le N$。

由于年纪和视力的原因，老人们并不能看得非常清楚。当一位视力度数为 $k$ 的老人观察草坪时，他无法区分连续 $k$ 个区段内的单个区段。形式化地说，视力度数为 $k$ 的老人在位置 $i$ 处看到的草高为 $\max(a_i, a_{i+1}, \ldots, a_{i+k-1})$ 毫米，对所有 $1 \le i \le N-k+1$ 成立，其余位置他不会观察。

此外，时不时地，某个区段的草可能会长高一毫米，这会改变整个草坪的外观，从而影响老人们所看到的高度。

需要处理 $Q$ 个如下形式的询问：

• ? k —— 视力度数为 $k$ 的老人观察草坪。求他看到的所有高度之和。
• + i —— 第 $i$ 个区段的草长高一毫米。

输入格式

第一行包含两个正整数 $N$ 和 $Q$ —— 草坪区段的数量和询问的数量。

第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$ —— 草的初始高度。

接下来的 $Q$ 行中，每行包含一个询问，格式为：

• ? k（$1 \le k \le N$）
• + i（$1 \le i \le N$）

输出格式

对于每个 ? k 类型的询问，输出一行一个整数 —— 视力度数为 $k$ 的老人所看到的所有高度之和。

子任务

在所有子任务中，满足 $1 \le N \le 500\,000$ 且 $0 \le Q \le 500\,000$。此外，对所有 $1 \le i \le N$，有 $1 \le a_i \le 10^9$。

样例数据

输入

6 5
1 7 2 3 5 4
+ 1
? 2
? 3
+ 5
? 3

输出

27
24
26

输入

10 4
1 2 2 1 3 2 1 3 2 2
? 4
? 5
+ 5
? 4

输出

20
18
24