search

Pojărel are o listă de N fişiere, fiecare având numele format doar din litere mici ale alfabetului latin. El vrea să implementeze un motor de căutare care să funcţioneze în timp real, adică imediat ce utilizatorul inserează sau şterge o literă din câmpul de căutare, să i se returneze numărul de fişiere care corespund şirului introdus la momentul respectiv. Un fişier corespunde căutarii dacă numele acestuia conţine şirul căutat ca subşir. Mai precis, caracterele din câmpul de căutare trebuie să apară în numele fişierului în aceeaşi ordine, însă nu neapărat pe poziţii consecutive.

Cerinţă

Fiind dată lista care conţine numele fişierelor, determinaţi numărul de fişiere care va fi returnat după fiecare introducere sau ştergere a unui caracter din câmpul de căutare.

Date de intrare

Fişierul de intrare search.in conţine pe prima linie două numere naturale N şi M, reprezentând numărul de fişiere, respectiv numărul de operaţii care se fac asupra câmpului de căutare. Pe următoarele N linii se găsesc cele N nume de fişiere, formate doar din litere mici ale alfabetului latin. Urmează apoi M linii care descriu operaţiile în ordinea în care sunt efectuate. Astfel, pe fiecare linie i se afla un singur caracter care descrie operaţia i. Acest caracter este fie o literă, ceea ce înseamnă că s-a introdus litera respectivă în câmpul de căutare, fie caracterul -, ceea ce înseamnă că s-a şters ultima literă din câmpul de căutare.

Date de ieşire

Fişierul de ieşire search.out va conţine M linii. Pe linia i (1 ≤ i ≤ M) se va afişa numărul de fişiere returnate de motorul de căutare după efectuarea primelor i operaţii.

Restricţii

• 1 ≤ N ≤ 100;
• 1 ≤ M ≤ 200 000;
• lungimea oricărui nume de fişier este maxim 5 000;
• două sau mai multe fişiere pot avea acelaşi nume;
• prima litera introdusă nu va fi ştearsă niciodată.

Exemplu

search.in

4 5
palalila
alabala
olimpiada
iasi
a
a
l
-
b

search.out

4
3
2
3
1

Explicaţii

• prima dată se introduce litera a, care se găseşte în toate cele 4 nume de fişiere
• după a doua operaţie câmpul va avea valoarea aa şi vor fi găsite primele 3 fişiere
• după a treia operaţie câmpul va avea valoarea aal şi vor fi găsite fişierele palalila şi alabala
• după a patra operaţie câmpul va avea din nou valoarea aa şi vor fi găsite primele 3 fişiere
• după a cincea operaţie câmpul va avea valoarea aab şi va fi găsit doar fişierul alabala