Lüğətdə axtarış

Verilmiş s_1, s_2, ..., s_n dəstəsi n sözlük sətirindən ibarətdir. Bundan əlavə, q_1, q_2, ..., q_m dəstəsi m sorğu sətirindən ibarətdir.

Hər bir q_i sətirinə görə, sözlükdə neçə sətirin q_i prefiksi ilə başladığını tapın. Daha dəqiq desək, hər bir i indeksi üçün, q_i prefiksi olan s_t sətirlərinin sayını müəyyənləşdirin.

Giriş verilənləri

Birinci sətir iki tam ədəd n və m (1 ≤ n, m ≤ 10^5) ehtiva edir. Sonrakı n sətirin hər biri boş olmayan s_i sətirini ehtiva edir. Daha sonra gələn m sətirin hər biri boş olmayan q_i sətirini ehtiva edir. Diqqət yetirin ki, dəstdəki sətirlər təkrarlana bilər.

Çıxış verilənləri

m tam ədəd çıxarın: i-ci ədəd q_i sətiri üçün cavabı göstərməlidir.

Nümunələr