今天Sonya学习了长整数,并邀请所有朋友一起分享乐趣。 Sonya 最初有一个空的整数多重集。朋友们向她提出了 t 个查询,每个查询都属于以下类型之一:
1. + ai — 将非负整数 ai 添加到多重集。请注意,她有一个多重集,因此同一整数可能会多次出现。
2. - ai — 从多重集中删除单个出现的非负整数 ai。可以保证多重集中至少有一个人工智能。
3. ? s - 计算多重集中(有重复)中与某些由 0 和 1 组成的模式 s 匹配的整数的数量。在该模式中,0 代表偶数,而 1 代表奇数。如果十进制右数第 i 个数字的奇偶校验与模式右数第 i 个匹配,则整数 x 与模式 s 匹配。如果模式短于该整数,则会从左侧补充 0。同样,如果整数比模式短,则其十进制表示法会从左侧补充 0。
例如,如果模式为 s = 010,则整数 92、2212、50 和 414 与该模式匹配,而整数 3、110、25 和 1030 则不匹配。
输入
输入的第一行包含一个整数 t (1 ≤ t ≤ 100 000) — Sonya 必须执行的操作数。
接下来的 t 行按照查询在输入文件中出现的顺序提供查询的描述。第 i 行以字符 ci 开头——对应操作的类型。如果 ci 等于“+”或“-”,则其后跟一个空格和一个不带前导零的整数 ai (0 ≤ ai < 1018)(除非它是 0)。如果 ci 等于 '?'然后后面跟着一个空格以及一系列 0 和 1,给出长度不超过 18 的模式。
保证至少有一个“?”类型的查询。
保证任何时候从多重集中删除某个整数时,该整数都会在其中至少出现一次。
输出
对于第三种类型的每个查询,打印与给定模式匹配的整数的数量。每个整数都会被计算多次,就像它此时出现在多重集中一样。
示例
输入 #1
12 + 1 + 241 ? 1 + 361 - 241 ? 0101 + 101 ? 101 - 101 ? 101 + 4000 ? 0
输出 #1
2 1 2 1 1
输入 #2
4 + 200 + 200 - 200 ? 0
输出 #2
1
注意
考虑与第三种类型的查询中的模式相匹配的整数。查询按照它们在输入中出现的顺序进行编号。
1. 1 和 241。
2. 361.
3. 101 和 361。
4. 361.
5. 4000.