Дезоксирибонуклеїнова кислота#6089
Наука рухається вперед, і біологія не є винятком. Декодування ДНК стало одним з переломних моментів в історії біології. Один з студентів старшого курсу біологічного факультету, Джордж, вирішив зробити свій внесок у цю захоплюючу науку. Джордж планує розробити базу даних для зберігання генетичних кодів ДНК. Вам доручено реалізувати програму, яка додає коди до бази даних і повертає кількість кодів, для яких даний код є префіксом.
Код довжиною є префіксом коду довжиною , якщо N < M і перші символів коду дорівнюють коду . Для зручності ДНК код представлений непорожнім рядком символів 'a', 'b', 'c', 'd'. База даних Джорджа повинна коректно обробляти дубльовані ДНК коди.
Перший рядок вхідних даних містить ціле число – кількість операцій з базою даних. Наступні рядків містять по одній операції кожен. Операція вставки складається з символу "+" за яким слідує ДНК код, який потрібно додати до бази даних, операція запиту складається з символу "?" за яким слідує ДНК код, для якого потрібно знайти кількість кодів з бази даних, що мають цей код як префікс.
Для кожного рядка на вході, який починається з символу "?", потрібно надрукувати результат у окремому рядку на виході.
Обмеження
Загальна довжина кодів у базі даних Джорджа не перевищує .
Приклад 1