English · Original
Chinese · Translation
Formal · Original
Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her _t_ queries, each of one of the following type:
1. + _a__i_ — add non-negative integer _a__i_ to the multiset. Note, that she has a multiset, thus there may be many occurrences of the same integer.
2. - _a__i_ — delete a single occurrence of non-negative integer _a__i_ from the multiset. It's guaranteed, that there is at least one _a__i_ in the multiset.
3. ? _s_ — count the number of integers in the multiset (with repetitions) that match some pattern _s_ consisting of 0 and 1. In the pattern, 0 stands for the even digits, while 1 stands for the odd. Integer _x_ matches the pattern _s_, if the parity of the _i_\-th from the right digit in decimal notation matches the _i_\-th from the right digit of the pattern. If the pattern is shorter than this integer, it's supplemented with 0\-s from the left. Similarly, if the integer is shorter than the pattern its decimal notation is supplemented with the 0\-s from the left.
For example, if the pattern is _s_ = 010, than integers 92, 2212, 50 and 414 match the pattern, while integers 3, 110, 25 and 1030 do not.
## Input
The first line of the input contains an integer _t_ (1 ≤ _t_ ≤ 100 000) — the number of operation Sonya has to perform.
Next _t_ lines provide the descriptions of the queries in order they appear in the input file. The _i_\-th row starts with a character _c__i_ — the type of the corresponding operation. If _c__i_ is equal to '_+_' or '_\-_' then it's followed by a space and an integer _a__i_ (0 ≤ _a__i_ < 1018) given without leading zeroes (unless it's _0_). If _c__i_ equals '_?_' then it's followed by a space and a sequence of zeroes and onse, giving the pattern of length no more than 18.
It's guaranteed that there will be at least one query of type '_?_'.
It's guaranteed that any time some integer is removed from the multiset, there will be at least one occurrence of this integer in it.
## Output
For each query of the third type print the number of integers matching the given pattern. Each integer is counted as many times, as it appears in the multiset at this moment of time.
[samples]
## Note
Consider the integers matching the patterns from the queries of the third type. Queries are numbered in the order they appear in the input.
1. 1 and 241.
2. 361.
3. 101 and 361.
4. 361.
5. 4000.
今天，Sonya 学习了长整数，并邀请她所有的朋友一起分享乐趣。Sonya 有一个初始为空的多重集，用于存储整数。朋友们给她提供了 #cf_span[t] 个查询，每个查询属于以下类型之一：
例如，如果模式是 #cf_span[s = 010]，那么整数 #cf_span[92]、#cf_span[2212]、#cf_span[50] 和 #cf_span[414] 与该模式匹配，而整数 #cf_span[3]、#cf_span[110]、#cf_span[25] 和 #cf_span[1030] 则不匹配。
输入的第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 100 000]) —— 表示 Sonya 需要执行的操作数量。
接下来的 #cf_span[t] 行按输入顺序提供了查询的描述。第 #cf_span[i] 行以一个字符 #cf_span[ci] 开头 —— 表示对应操作的类型。如果 #cf_span[ci] 等于 '_+_' 或 '_-_'，则其后跟一个空格和一个整数 #cf_span[ai] (#cf_span[0 ≤ ai < 1018])，该整数不带前导零（除非是 _0_）。如果 #cf_span[ci] 等于 '_?_'，则其后跟一个空格和一个由零和一组成的序列，该模式长度不超过 #cf_span[18]。
保证至少存在一个类型为 '_?_' 的查询。
保证在任何时刻从多重集中移除某个整数时，该整数在多重集中至少存在一次。
对于每个第三类查询，输出与给定模式匹配的整数个数。每个整数根据其在当前时刻多重集中的出现次数被计数多次。
考虑第三类查询中模式匹配的整数。查询按其在输入中出现的顺序编号。
## Input
输入的第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 100 000]) —— 表示 Sonya 需要执行的操作数量。接下来的 #cf_span[t] 行按输入顺序提供了查询的描述。第 #cf_span[i] 行以一个字符 #cf_span[ci] 开头 —— 表示对应操作的类型。如果 #cf_span[ci] 等于 '_+_' 或 '_-_'，则其后跟一个空格和一个整数 #cf_span[ai] (#cf_span[0 ≤ ai < 1018])，该整数不带前导零（除非是 _0_）。如果 #cf_span[ci] 等于 '_?_'，则其后跟一个空格和一个由零和一组成的序列，该模式长度不超过 #cf_span[18]。保证至少存在一个类型为 '_?_' 的查询。保证在任何时刻从多重集中移除某个整数时，该整数在多重集中至少存在一次。
## Output
对于每个第三类查询，输出与给定模式匹配的整数个数。每个整数根据其在当前时刻多重集中的出现次数被计数多次。
[samples]
## Note
考虑第三类查询中模式匹配的整数。查询按其在输入中出现的顺序编号。 #cf_span[1] 和 #cf_span[241]。 #cf_span[361]。 #cf_span[101] 和 #cf_span[361]。 #cf_span[361]。 #cf_span[4000]。
Let $ t \in \mathbb{N} $, $ 1 \leq t \leq 100{,}000 $, be the number of operations.
Let $ M $ be a multiset of non-negative integers, initially empty.
Each operation is one of the following three types:
1. **Insertion** ($ + $): Given an integer $ a \in \mathbb{Z} $, $ 0 \leq a < 10^{18} $, add one occurrence of $ a $ to $ M $.
2. **Deletion** ($ - $): Given an integer $ a \in \mathbb{Z} $, $ 0 \leq a < 10^{18} $, remove one occurrence of $ a $ from $ M $ (guaranteed to exist).
3. **Query** ($ ? $): Given a binary string $ p \in \{0,1\}^* $, $ 1 \leq |p| \leq 18 $, compute:
$$
\left| \left\{ a \in M \,\middle|\, \text{the decimal representation of } a \text{ matches pattern } p \right\} \right|
$$
where "matches pattern $ p $" means: the string formed by the decimal digits of $ a $, when stripped of leading zeros (except for the number 0 itself), has length equal to $ |p| $, and for each position $ i \in \{1, \dots, |p|\} $, the $ i $-th digit of $ a $ is even if $ p_i = 0 $, and odd if $ p_i = 1 $.
For each query of type $ ? $, output the count of integers in $ M $ matching the given pattern $ p $, accounting for multiplicity.
API Response (JSON)
{
"problem": {
"name": "C. Sonya and Queries",
"description": {
"content": "Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her _t_ queries, each of one of the following ty",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF714C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her _t_ queries, each of one of the following ty...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "今天，Sonya 学习了长整数，并邀请她所有的朋友一起分享乐趣。Sonya 有一个初始为空的多重集，用于存储整数。朋友们给她提供了 #cf_span[t] 个查询，每个查询属于以下类型之一：\n\n例如，如果模式是 #cf_span[s = 010]，那么整数 #cf_span[92]、#cf_span[2212]、#cf_span[50] 和 #cf_span[414] 与该模式匹配，而整数 #cf...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ t \\in \\mathbb{N} $, $ 1 \\leq t \\leq 100{,}000 $, be the number of operations.\n\nLet $ M $ be a multiset of non-negative integers, initially empty.\n\nEach operation is one of the following three ty...",
"is_translate": false,
"language": "Formal"
}
]
}