Дезоксирибонуклеиновая кислота
Наука не стоит на месте, а постоянно розвивается и биология не исключние. Розшифровка структуры ДНК стала одним из поворотных моментов в истории биологии. Один из учников 10 биологического класса – Григорий решил сделать и свой вклад в эту интересную науку. Григорий планирует разработать базу данных для генетических кодов ДНК. Вам поручено реализувать программу, которая добавляет коды в базу данных и подсчитывает количество кодов для которых заданный код является префиксом.
Напомним, что код А длины N является префиксом кода B длины M, если N и первые N символов кода B равны коду А. Для удобства работы код ДНК представлено непустой строкой из символов ‘a’, ‘b’, ‘c’, ‘d’. База данных Григория должна корректно работать с одинаковыми кодами ДНК.
Входные данные
Первая строка содержит натуральное число T – количество операций с базой данных. Следующие T строк содержат по одной операции. Операция добавления элемента состоит из знака «+» и записанного за ним кода ДНК котрый нужно добавить в базу, а запрос к базе данных состоит из знака «?» и записанного за ним кода ДНК для которого нужно определить для скольких кодов в базе данных данный код является префиксом.
Суммарная длина кодов в базе данных Григория не превышает 1000000.
Выходные данные
Для каждой строки входных данных начинающегося знаком «?» вывести ответ в отдельной строке.