Onun ilk adı#11350
Krallıq ailəsində adlar çox önəmlidir! Siz, krallığın tarixçisi olaraq, krallıq xanımlarının adlarındakı qanunauyğunluqları araşdırmaqla vəzifələndirilmisiniz.
Cəmi krallıq xanımı var və onlar rahatlıq üçün -dən -ə qədər nömrələnib. Hər bir xanımın adı böyük hərflə başlayır və anasının adı ilə birləşir. İstisna olaraq, nömrəli xanım, krallıq ailəsinin qurucusu, adı yalnız bir böyük hərfdən ibarətdir.
Məsələn, ENERYS, AENERYS-in anası ola bilər (çünki AENERYS adı yalnız bir böyük hərf 'A' ilə başlayır və ENERYS ilə birləşir, bu da onun anasının adıdır). Eyni şəkildə, AENERYS, DAENERYS və YAENERYS-in anası ola bilər.
Sizə bütün krallıq xanımlarının təsviri verilib. Sizin vəzifəniz, bəzi maraqlı sətirlər üçün, -in adlarının prefiksi olduğu krallıq xanımlarının sayını müəyyən etməkdir. Məsələn, aşağıdakı 1-ci giriş nümunəsini nəzərdən keçirək, burada krallıq xətti qurucu S-dən AENERYS-ə qədər gedir (YS, RYS, ERYS, NERYS və ENERYS vasitəsilə), hər bir xanımın yalnız bir qızı var. Sonra AENERYS-in iki qızı var — DAENERYS və YAENERYS, sonuncunun bir qızı var, RYAENERYS.
Belə bir ailədə RY, iki xanımın adlarının prefiksidir: RYS və RYAENERYS. E, ERYS və ENERYS adlarının prefiksidir. N yalnız NERYS adının prefiksidir, S isə yalnız qurucu S adının prefiksidir. AY heç bir krallıq xanımının adının prefiksi deyil.
Birinci sətirdə iki tam ədəd və yazılıb, burada n~(1 \le n \le 10^6) — krallıq xanımlarının ümumi sayı, k~(1 \le k \le 10^6) — sorğu sətirlərinin sayı.
Sonra krallıq xanımlarını təsvir edən sətir gəlir. Bu sətirlərdən -ci, nömrəsi olan krallıq xanımını təsvir edir və böyük hərf c_i ('A' — 'Z') və tam ədəd p_i ehtiva edir, burada c_i — xanım -nin adının ilk hərfidir, p_i~(p_1 = 0 və 1 \le pi < i üçün i > 1) — onun anasının nömrəsidir (və ya İlk xanım üçün ). Bütün adlar unikaldır.
Qalan sətir, yalnız böyük hərflərdən ibarət olan bir sorğu sətiri ehtiva edir. Sorğu sətirlərinin uzunluqlarının cəmi 10^6-dan çox deyil.
sətir çıxarın, burada -ci sətir, -ci sorğu sətirinin adlarının prefiksi olduğu krallıq xanımlarının sayını ehtiva edir.
Nümunə 1