Na vstupe sú dva zoznamy reťazcov — prvý zoznam nazveme slovník.
Nech $b = b_1 b_2 b_3 \dots b_k$ je reťazec z druhého zoznamu, kde $b_1 \dots b_k$ sú znaky tohto reťazca. Pre každé $i$ od $1$ po $k$ zistite počet reťazcov $a$ zo slovníka, pre ktoré platí, že $b_1 = a_1, b_2 = a_2 \dots b_i = a_i$. Pre každý začiatok reťazca $b$ z druhého zoznamu teda vypočítajte počet reťazcov zo slovníka, ktoré majú rovnaký začiatok.
Toto vypočítajte pre každý reťazec z druhého zoznamu.
V prvom riadku je číslo $1 \leq n \leq 10^5$ — počet reťazcov v slovníku.
Nasleduje $n$ riadkov, v každom je jeden reťazec patriaci do slovníka. Tieto reťazce nemusia byť nutne rôzne.
Nasleduje číslo $q$ ($1 \leq q \leq 10^5$) — počet reťazcov v druhom zozname.
Nasleduje $q$ riadkov, v každom z nich je jeden reťazec patriaci do druhého zoznamu.
Všetky reťazce pozostávajú z malých písmen anglickej abecedy a súčet dĺžok reťazcov v každom zo zoznamov nepresiahne $3\cdot 10^5$.
Pre každý reťazec $b$ z druhého zoznamu vypíšte na jeden riadok počet reťazcov zo slovníka, ktoré majú rovnaký začiatok ako $b$ dĺžky 1, dĺžky 2 až dĺžky reťazca $b$. Za posledným číslom na každom riadku nevypisujte medzeru.
3
aaaa
abaa
aabb
5
aaaa
aaba
trebatrie
alebohash
aaaahoj
3 2 1 1
3 2 1 0
0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
3 2 1 1 0 0 0