Cộng Điểm, Hỏi Tiền Tố

Có một mảng $a$ gồm $n$ phần tử, được đánh chỉ số từ $0$ đến $n-1$. Ban đầu, mọi phần tử đều bằng $0$.

Bạn cần xử lý lần lượt $q$ thao tác thuộc một trong hai dạng:

• $+idelta$: cộng delta vào $a_i$;
• ? i: tính tổng của $i$ phần tử đầu tiên, tức $a_0+a_1+\cdots +a_{i-1}$.

Với $i=0$, tổng cần tính là tổng của đoạn rỗng và bằng $0$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Mỗi trong $q$ dòng tiếp theo mô tả một thao tác theo một trong hai dạng trên.

Output

• Với mỗi thao tác ? i, in tổng tương ứng trên một dòng.

Constraints

• $1\le n\le 5\cdot 10^6$.
• $0\le q\le 5\cdot 10^6$.
• Trong thao tác $+idelta$: $0\le i<n$ và - $10^9\le \text{delta}\le 10^9$.
• Trong thao tác ? i: $0\le i\le n$.
• Mọi tổng đều nằm trong miền của số nguyên có dấu $64$-bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 8
? 0
+ 1 4
+ 3 -2
? 2
+ 0 7
? 1
? 4
? 5

0
4
7
9
9