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