题目描述

比特集合是一种抽象数据类型(Abstract Data Type) ，其包含一个集合S，并支持如下几种操作：

INS M : 将元素 M 插入到集合S中；

DEL M : 将集合S中所有等于 M 的元素删除；

ADD M : 将集合S中的所有元素都增加数值M ；

QBIT k : 查询集合中有多少个元素满足其二进制的第 $k$ 位为 1 。

初始时，集合S为空集。请实现一个比特集合，并对于所有的QBIT操作输出相应的答案。

输入格式

输入第一行包含一个正整数 $N$，表示操作的数目。

接下来 $N$ 行，每行为一个操作，格式见问题描述。

输出格式

对于每一个QBIT操作，输出一行，表示相应的答案。

8 
INS 1 
QBIT 0
ADD 1 
QBIT 0 
QBIT 1 
DEL 2 
INS 1 
QBIT 1

1
0
1 
0

数据范围与约定

数据规模和约定

时间限制2s。

对于30%的数据，$1 ≤ N ≤ 10000$。

对于100%的数据，$1 ≤ N ≤ 500000$；QBIT操作中的 $k$ 满足, $0 ≤ k < 16$。INS/DEL操作中，满足$0 ≤ M ≤ 10^9$；ADD操作中, 满足 $0 ≤ M ≤ 1000$。

注意集合S可以包含多个重复元素。