In a quiet corner of the city, there is a retirement home whose residents love to spend their time watching the lawn in front of the building. The lawn is divided into $N$ segments, and each segment has a grass height of $a_i$ millimeters, for $1 \le i \le N$.

Due to their age and eyesight, the residents do not see perfectly. When a resident with diopter $k$ observes the lawn, they cannot distinguish individual segments within $k$ consecutive parts of the lawn. More formally, a resident with diopter $k$ at position $i$ sees a grass height of $\max(a_i, a_{i+1}, \dots, a_{i+k-1})$ millimeters, for all $1 \le i \le N - k + 1$, while they do not observe the other positions.

Additionally, from time to time, the grass on a certain segment may grow by one millimeter, which changes the appearance of the entire lawn and, consequently, the heights that the residents see.

You need to process $Q$ queries of the following types:

• $? k$ — A resident with diopter $k$ observes the lawn. Determine the sum of all heights they see.
• $+ i$ — The grass on the $i$-th segment grows by one millimeter.

Input

The first line contains natural numbers $N$ and $Q$ — the number of lawn segments and the number of queries.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$ — the initial grass heights.

The next $Q$ lines each contain one query described as:

• $? k$ ($1 \le k \le N$)
• $+ i$ ($1 \le i \le N$)

Output

For each query of type $? k$, print one integer in a separate line — the sum of all heights observed by a resident with diopter $k$.

Subtasks

In all subtasks, $1 \le N \le 500\,000$ and $0 \le Q \le 500\,000$. Additionally, for all $1 \le i \le N$, $1 \le a_i \le 10^9$.

Examples

Input 1

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

Output 1

27
24
26

Input 2

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

Output 2

20
18
24