e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

I Cup Alexandria 2010

Дезоксирыбонуклеиновая кислота

Наука не стоит на месте, а постоянно розвивается и биология не исключние. Розшифровка структуры ДНК стала одним из поворотных моментов в истории биологии. Один из учников 10 биологического класса – Григорий решил сделать и свой вклад в эту интересную науку. Григорий планирует разработать базу данных для генетических кодов ДНК. Вам поручено реализувать программу, которая добавляет коды в базу данных и подсчитывает количество кодов для которых заданный код является префиксом.

Напомним, что код А длины N является префиксом кода B длины M, если N и первые N символов кода B равны коду А. Для удобства работы код ДНК представлено непустой строкой из символов ‘a’, ‘b’, ‘c’, ‘d’. База данных Григория должна корректно работать с одинаковыми кодами ДНК.

Входные данные

Первая строка содержит натуральное число T – количество операций с базой данных. Следующие T строк содержат по одной операции. Операция добавления элемента состоит из знака «+» и записанного за ним кода ДНК котрый нужно добавить в базу, а запрос к базе данных состоит из знака «?» и записанного за ним кода ДНК для которого нужно определить для скольких кодов в базе данных данный код является префиксом.

Суммарная длина кодов в базе данных Григория не превышает 1000000.

Выходные данные

Для каждой строки входных данных начинающегося знаком «?» вывести ответ в отдельной строке.

Time limit 1 second
Memory limit 64 MiB
Input example #1
4
+abcd
?abc
+abc
?ab
Output example #1
1
2