Олимпиадный тренинг

Задача 21889. Meganet search championship


Задача

Темы:
To hold the Meganet World Search Championship, the organizers need to restrict access to some addresses. The address in the Meganet network is a string consisting of the server name and the section name.

The server name is a string containing one to five parts, inclusive. Each part is a non-empty string consisting of lowercase Latin letters. The parts are separated by a dot. Examples of valid server names: "a", "ab.cd", "abacaba", "a.b.c.d.e".

The section name is a string that can be either empty or contain one to five parts, inclusive. Each part begins with the character "/" followed by one or more lowercase English letters. Examples of valid section names: "", "/a", "/aba", "/a/b/c/d/e". The address is formed by adding the section name to the end of the server name. For example, valid addresses are the strings: "a", "aba/d/f/g/h", "a.b", "aba.caba/def/g", "c.d.e.f.g/a/b /c/d/e».

To restrict access to some addresses of the Meganet network, the organizers of the championship have prepared several filters. The filter, like the address, consists of two parts: the server filter and the section filter.

The server filter consists of the server name, which can also be preceded by the string "*.". If a server filter is only a server name, then only the server with the exact same name matches the filter. If the server filter is the string «*.S», where S — the name of the server, then it matches the servers, by removing zero or more initial parts, on behalf of which the string S can be obtained.

Similarly, a section filter is a section name, optionally followed by the string "/*". The section filter, which is simply the name of the R section, matches only sections that exactly match R. If the section filter is the string "R/*", then it matches all sections whose names have zero or more trailing parts removed from their names. you can get the string R. An address matches the filter if its server name matches the server filter and its topic name matches the topic filter.

Examples of filters and their corresponding addresses are shown in the table below.
ab.c/d/e ab.c/d/e
*.a a             ax.a         efg.a
*.a/b/c a/b/c       x.a/b/c      e.fg.a/b/c
x.yz/a/* x.yz/a      x.yz/a/b/c    x.yz/a/xyz
*.a/* a             x.a                   e.fg.a
a/b/c    x.a/ddd/c           e.fg.a/b/c/g/haha/i
*.a/b/c/* a/b/c                           x.a/b/c                           e.fg.a/b/c
a/b/c/xxx                   e.fg.a/b/c/d/e/f
   

It is required to write a program that, given a set of filters and a list of addresses, determines for each address how many filters this address corresponds to.

Example:
Input:
20
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c

Output:
0
1
0
0


Output:
40
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d

Output:
0
4
3
0
2
1