Cho một dãy số nguyên gồm ~n~ số ~a_1, a_2, \ldots, a_n~.

Gọi ~C(x)~ là số cách chọn hai số ~a_i~, ~a_j~ (~1 \le i < j \le n~), sao cho ~a_i + a_j = x~.

Ta có đa tập hợp (multiset) ~S~ ban đầu rỗng. Ta cần thực hiện ~q~ truy vấn, mỗi truy vấn thuộc một trong các dạng sau:

• add ~x~: Thêm phần tử ~x~ (~|x| \le 10^9~) vào ~S~.

• del ~x~: Xóa phần tử ~x~ (~|x| \le 10^9~) khỏi ~S~ (nếu trong ~S~ gồm nhiều phần tử ~x~, ta chỉ xóa một phần tử ~x~ ra khỏi ~S~). Dữ liệu đảm bảo tồn tại ~x~ trong ~S~ khi thực hiện thao tác xoá.

• ask ~l~ ~r~: Tính giá trị của ~F(l, r)~ (~-10^9 \le l \le r \le 10^9~), với $$F(l, r) = \sum_{l \le x \le r, x \in S} C(x)$$

• roll ~t~: Quay lại thời điểm trước khi thực hiện truy vấn thứ ~t~ (~1 \le t < i~), với ~i~ là thời điểm của truy vấn hiện tại.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n~, ~q~ (~1 \le n, q \le 10^5~).

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^5~).

~q~ dòng tiếp theo gồm ~q~ truy vấn có dạng trên.

Output

Với mỗi truy vấn ask, in ra một số nguyên trên một dòng.

Scoring

Sample Input 1

6 6
1 1 3 2 5 6
add 3
del 3
roll 2
add 5
ask 3 5
ask 5 10

Sample Output 1

3
1