401373: GYM100425 B Passport Control

No one is safe from losing his passport. But even if the passport is lost, it is still not the end of the world. To replace it, you just need to present another picture ID and wait for a few weeks. But what should one do if the passport is suddenly lost during a vacation in an exotic country?

The migration service of a certain insular country keeps track of every single tourist entering the country. Each tourist is assigned a sequence of K fields which all together create a tourist ID. When a tourist crosses the border, the fields are filled according to the data in the passport. The tourist ID is a complex concept to handle for migration officers, so one can not be sure which fields will contain one's name or surname, or whether they will be present in it at all. It may even happen that migration officers fill some fields with arbitrary strings by mistake. The only thing known for sure is that none of the fields are empty and all fields contain only lowercase English letters.

A certain tourist tries to find his tourist ID by issuing queries to the migration service database using a query form. Each query consists of K strings. The answer for the query is the list of all tourist IDs in the database for which each of the K strings is a prefix of the corresponding field of that tourist ID.

Initially, all K strings of the query form are empty. To make the next query, the tourist modifies the previous one in one of the two following ways:

1. <i> + <c>: add character <c> to the end of string number <i>,
2. <i> -: remove the last character of string number <i>.

For each of the Q queries, you need to calculate how many tourist IDs match this query.

The first line of the input holds an integer number N (1 ≤ N ≤ 100 000) which is the number of tourist IDs in the database and an integer number K (1 ≤ K ≤ 3) which is the number of fields in each tourist ID.

Then follow N tourist IDs. Each tourist ID is given on K consecutive lines, each of which contains the respective field of the tourist ID. It is guaranteed that the lines are non-empty and contain only lowercase English letters. The total length of all given strings does not exceed 100 000.

The next line holds a single integer Q (1 ≤ Q ≤ 100 000) which is the number of queries. Each of the next Q lines describes a modification to the query form. Each modification has one of the two possible forms: either "<i> + <c>" or "<i> -". It is guaranteed that before each modification of the second type, the respective field is not empty.

For each query, print the number of matching tourist IDs in the database on a separate line.

5 2
abacaba
ccad
abadaba
cbad
abbbaaa
cbab
bbbba
ccc
abacabs
fuuuu
15
1 + a
2 + c
2 + c
1 + b
2 -
2 + b
1 + a
2 -
2 -
1 -
1 -
1 -
1 + c
1 -
1 + b

4
3
1
1
3
2
1
2
3
4
4
5
0
5
1