#2568. 比特集合

内存限制:128 MiB 时间限制:10 Sec

题目描述

  比特集合是一种抽象数据类型(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可以包含多个重复元素。