Сегодня сова Соня выучила длинные числа и сразу же позвала в гости своих друзей, чтобы продемонстрировать им свои навыки. У Сони есть мультимножество с числами, изначально пустое. Друзья сделают t запросов, каждый одного из трёх видов:
- + ai — добавить целое неотрицательное число ai в мультимножество. Обратите внимание, что, поскольку у Сони мультимножество, в нём может содержаться несколько одинаковых чисел.
- - ai — удалить целое неотрицательное число ai из мультимножества. Гарантируется, что такое число есть в мультимножестве. Если в мультимножестве было несколько экземпляров числа ai, то при выполнении данной операции удаляется только один из них.
- ? s — ответить, сколько чисел в мультимножестве (включая повторы) подходит под шаблон s, состоящий из 0 и 1. В шаблоне 0 соответствует чётным цифрам, а 1 — нечётным. Число x подходит под шаблон s, если чётность i-й справа цифры числа, записанного в десятичной системе, подходит под i-ю справа цифру шаблона. При этом если шаблон короче соответствующего числа, то он дополняется нулями слева. Аналогично, если десятичная запись числа короче шаблона, то оно также дополняется нулями слева.
Например, под шаблон s = 010 подходят числа 92, 2212, 50 и 414, но не подходят числа 3, 110, 25 и 1030.
Выходные данные
Для каждого запроса третьего типа выведите количество подходящих чисел в мультимножестве. Каждое число учитывается количество раз, равное количеству вхождений в мультимножество в данный момент времени.
Примечание
Рассмотрим, какие числа подходят под операции третьего типа, пронумерованные в порядке их появления во входным данных:
- 1 и 241.
- 361.
- 101 и 361.
- 361.
- 4000.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12
+ 1
+ 241
? 1
+ 361
- 241
? 0101
+ 101
? 101
- 101
? 101
+ 4000
? 0
|
2
1
2
1
1
|
|
2
|
4
+ 200
+ 200
- 200
? 0
|
1
|