Dezoksiribonuklein turşusu
Elm daim inkişaf edir və biologiya da bu prosesdən kənarda qalmır. DNT-nin strukturunun deşifrə edilməsi biologiya tarixində dönüş nöqtələrindən biri olmuşdur. 10-cu sinifdə oxuyan Qriçko bu maraqlı elmə öz töhfəsini vermək qərarına gəlib. O, DNT-nin genetik kodları üçün bir məlumat bazası hazırlamağı planlaşdırır. Sizin vəzifəniz verilənlər bazasına kodlar əlavə edən və verilmiş kodun prefiks olduğu kodların sayını hesablayan bir proqramı həyata keçirməkdir.
Xatırladaq ki, A uzunluğunda kod B uzunluğunda kodun prefiksidir, əgər N və kod B-nin ilk N simvolları kod A-ya bərabərdirsə. İşin rahatlığı üçün DNT kodu ‘a’, ‘b’, ‘c’, ‘d’ simvollarından ibarət boş olmayan bir sıra ilə təmsil olunur. Qriçkonun məlumat bazası eyni DNT kodları ilə düzgün işləməlidir.
Giriş verilənləri
Birinci sətir T təbii ədədini ehtiva edir - verilənlər bazası ilə əməliyyatların sayı. Növbəti T sətir hər biri bir əməliyyatı ehtiva edir. Elementin əlavə edilməsi əməliyyatı «+» işarəsindən və verilənlər bazasına əlavə edilməli olan DNT kodundan ibarətdir, verilənlər bazasına sorğu isə «?» işarəsindən və verilənlər bazasında neçə kod üçün verilmiş kodun prefiks olduğunu müəyyən etmək üçün DNT kodundan ibarətdir.
Qriçkonun məlumat bazasındakı kodların ümumi uzunluğu 1000000-i keçmir.
Çıxış verilənləri
«?» işarəsi ilə başlayan giriş məlumatlarının hər bir sətiri üçün cavabı ayrıca sətirdə çıxarın.