Tahp đang nghiên cứu một cách biểu diễn hoán vị^∗ bằng một dãy số nguyên. Cụ thể, xét một hoán vị ~p_1, p_2, \ldots, p_n~ của các số nguyên từ ~1~ đến ~n~. Với mỗi vị trí ~i~, Tahp định nghĩa một giá trị ~f_i~ như sau:

$$f_i = |\{j \mid 1 \le j < i,\ p_j < p_i\}|$$

Nói cách khác, ~f_i~ là số lượng phần tử đứng trước vị trí ~i~ trong hoán vị ~p~ nhưng có giá trị nhỏ hơn ~p_i~.

Ví dụ, nếu ~p = [2, 6, 4, 1, 5, 3]~, thì:

• ~f_1 = 0~, vì trước vị trí ~1~ không có phần tử nào.

• ~f_2 = 1~, vì trước ~p_2 = 6~ có một phần tử nhỏ hơn nó, đó là ~2~.

• ~f_3 = 1~, vì trước ~p_3 = 4~ có một phần tử nhỏ hơn nó, đó là ~2~.

• ~f_4 = 0~, vì trước ~p_4 = 1~ không có phần tử nào nhỏ hơn nó.

• ~f_5 = 3~, vì trước ~p_5 = 5~ có ba phần tử nhỏ hơn nó, đó là ~2, 4, 1~.

• ~f_6 = 2~, vì trước ~p_6 = 3~ có hai phần tử nhỏ hơn nó, đó là ~2, 1~.

Do đó, dãy ~f~ tương ứng với hoán vị trên là ~[0, 1, 1, 0, 3, 2]~.

Rõ ràng, với mọi hoán vị ~p~, dãy ~f~ thu được luôn thỏa mãn: ~0 \le f_i < i~. Điều thú vị là chiều ngược lại cũng đúng. Với mọi dãy số nguyên ~f_1, f_2, \ldots, f_n~ thỏa mãn ~0 \le f_i < i~, có thể chứng minh rằng tồn tại duy nhất một hoán vị ~p_1, p_2, \ldots, p_n~ sao cho dãy ~f~ được định nghĩa từ ~p~ theo công thức trên.

Trong bài toán này, bạn được cho dãy ~f~ ban đầu. Sau đó, dãy ~f~ sẽ thay đổi qua các thao tác cập nhật. Sau mỗi lần cập nhật, dữ liệu luôn đảm bảo rằng dãy ~f~ vẫn thỏa mãn ~0 \le f_i < i~, vì vậy hoán vị tương ứng với dãy ~f~ hiện tại luôn tồn tại và là duy nhất.

Bạn cần xử lý ~q~ thao tác. Mỗi thao tác thuộc một trong ba dạng sau:

• + i: tăng ~f_i~ lên ~1~.

• - i: giảm ~f_i~ đi ~1~.

• ? l r: xét hoán vị ~p~ duy nhất tương ứng với dãy ~f~ hiện tại, hãy in ra giá trị ~p_l + p_{l+1} + \cdots + p_r~.

∗ Một hoán vị độ dài ~n~ là một dãy gồm ~n~ số nguyên, trong đó mỗi số nguyên từ ~1~ đến ~n~ xuất hiện đúng một lần.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(2 \le n \le 5 \cdot 10^5;\ 1 \le q \le 5 \cdot 10^5)~  — độ dài dãy ~f~ và số lượng thao tác.

Dòng thứ hai chứa ~n~ số nguyên ~f_1, f_2, \ldots, f_n~ ~(0 \le f_i < i~ với mọi ~1 \le i \le n)~.

Mỗi dòng trong ~q~ dòng tiếp theo mô tả một thao tác thuộc một trong ba dạng sau:

• + i ~(1 \le i \le n)~: tăng ~f_i~ lên ~1~.

• - i ~(1 \le i \le n)~: giảm ~f_i~ đi ~1~.

• ? l r ~(1 \le l \le r \le n)~: yêu cầu tính tổng ~p_l + p_{l+1} + \cdots + p_r~, trong đó ~p~ là hoán vị duy nhất tương ứng với dãy ~f~ hiện tại.

Đảm bảo tại mọi thời điểm, dãy ~f~ vẫn thỏa mãn ~0 \le f_j < j~ với mọi ~1 \le j \le n~, và có ít nhất một thao tác truy vấn ?.

Output

Với mỗi thao tác dạng ? l r, in ra trên một dòng một số nguyên là giá trị ~p_l + p_{l+1} + \cdots + p_r~, trong đó ~p~ là hoán vị duy nhất tương ứng với dãy ~f~ hiện tại.

Scoring

Sample Input 1

6 10
0 1 1 0 3 2
? 2 5
+ 4
- 5
+ 3
- 2
? 1 4
+ 6
- 4
+ 5
? 2 5

Sample Output 1

16
14
14

Notes

Ban đầu, dãy ~f~ là ~[0, 1, 1, 0, 3, 2]~. Hoán vị tương ứng là ~p = [2, 6, 4, 1, 5, 3]~. Do đó, truy vấn ? 2 5 có đáp án ~p_2 + p_3 + p_4 + p_5 = 6 + 4 + 1 + 5 = 16~.

Sau các thao tác + 4, - 5, + 3, - 2, dãy ~f~ trở thành ~[0, 0, 2, 1, 2, 2]~. Hoán vị tương ứng lúc này là ~p = [5, 1, 6, 2, 4, 3]~. Vì vậy, truy vấn ? 1 4 có đáp án ~p_1 + p_2 + p_3 + p_4 = 5 + 1 + 6 + 2 = 14~.

Sau các thao tác + 6, - 4, + 5, dãy ~f~ trở thành ~[0, 0, 2, 0, 3, 3]~. Hoán vị tương ứng lúc này là ~p = [3, 2, 6, 1, 5, 4]~. Vì vậy, truy vấn cuối cùng ? 2 5 có đáp án ~p_2 + p_3 + p_4 + p_5 = 2 + 6 + 1 + 5 = 14~.