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.
[{"iden":"statement","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_span[3]、#cf_span[110]、#cf_span[25] 和 #cf_span[1030] 不匹配。\n\n输入的第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 100 000]）——表示 Sonya 需要执行的操作数量。\n\n接下来的 #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] 的模式。\n\n保证至少有一个类型为 '_?_' 的查询。\n\n保证在任何时刻从多重集中移除某个整数时，该整数在多重集中至少存在一次。\n\n对于每个第三类查询，请输出匹配给定模式的整数数量。每个整数根据其在当前多重集中的出现次数被计数。\n\n考虑第三类查询中匹配模式的整数。查询按其在输入中出现的顺序编号。"},{"iden":"input","content":"输入的第一行包含一个整数 #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] 的模式。保证至少有一个类型为 '_?_' 的查询。保证在任何时刻从多重集中移除某个整数时，该整数在多重集中至少存在一次。"},{"iden":"output","content":"对于每个第三类查询，请输出匹配给定模式的整数数量。每个整数根据其在当前多重集中的出现次数被计数。"},{"iden":"examples","content":"输入12+ 1+ 241? 1+ 361- 241? 0101+ 101? 101- 101? 101+ 4000? 0输出21211输入4+ 200+ 200- 200? 0输出1"},{"iden":"note","content":"考虑第三类查询中匹配模式的整数。查询按其在输入中出现的顺序编号。 #cf_span[1] 和 #cf_span[241]。 #cf_span[361]。 #cf_span[101] 和 #cf_span[361]。 #cf_span[361]。 #cf_span[4000]。 "}]
注意：在原始内容中，部分文本如 "zeroes and onse" 应为 "zeroes and ones"，但根据要求，**所有数学公式、Typst 命令、下划线强调和拼写错误必须原样保留**，因此此处未作修正。
Let $ T $ be the number of queries, $ T \in [1, 100000] $.
Let $ S $ be a multiset of non-negative integers, initially empty.
Each query is of one of three types:
1. **Insertion**: $ + \; a $, where $ a \in \mathbb{Z} $, $ 0 \leq a < 10^{18} $, given as a decimal string without leading zeros (except for $ a = 0 $).
→ Add one occurrence of $ a $ to $ S $.
2. **Deletion**: $ - \; a $, where $ a \in \mathbb{Z} $, $ 0 \leq a < 10^{18} $, given as a decimal string without leading zeros.
→ Remove one occurrence of $ a $ from $ S $ (guaranteed to exist).
3. **Pattern Query**: $ ? \; p $, where $ p \in \{0,1\}^* $, $ |p| \leq 18 $.
→ Count the number of integers $ x \in S $ such that the decimal representation of $ x $ matches pattern $ p $.
**Pattern Matching Definition**:
An integer $ x $, with decimal representation $ d(x) \in \{0,1,\dots,9\}^* $, matches pattern $ p \in \{0,1\}^* $ if and only if:
- $ |d(x)| = |p| $, and
- For all positions $ i \in [1, |p|] $:
$$
p_i =
\begin{cases}
0 & \text{if the } i\text{-th digit of } d(x) \text{ is even} \\
1 & \text{if the } i\text{-th digit of } d(x) \text{ is odd}
\end{cases}
$$
**Objective**:
For each query of type $ ? \; p $, output the count of integers in $ S $ matching $ p $, according to the above definition.
Let $ f: \mathbb{Z}_{\geq 0} \to \{0,1\}^* $ be the function mapping an integer $ x $ to its parity pattern:
$ f(x)_i = \begin{cases} 0 & \text{if } d(x)_i \in \{0,2,4,6,8\} \\ 1 & \text{if } d(x)_i \in \{1,3,5,7,9\} \end{cases} $
Then, for a query $ ? \; p $, the answer is:
$$
\left| \left\{ x \in S \mid f(x) = p \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "A. 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": "CF713A"
},
"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": "[{\"iden\":\"statement\",\"content\":\"今天，Sonya 学习了长整数，并邀请她所有朋友一起分享乐趣。Sonya 有一个初始为空的多重集，包含整数。朋友们给她 #cf_span[t] 个查询，每个查询属于以下类型之一：\\n\\n例如，如果模式是 #cf_span[s = 010]，那么整数 #cf_span[92]、#cf_span[2212]、#cf_span[50] 和 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ T $ be the number of queries, $ T \\in [1, 100000] $.\n\nLet $ S $ be a multiset of non-negative integers, initially empty.\n\nEach query is of one of three types:\n\n1. **Insertion**: $ + \\; a $, wher...",
"is_translate": false,
"language": "Formal"
}
]
}