Problem Description

To host the Global Network Search Championship, the organizers need to restrict access to certain addresses. Each web address consists of a server name and a path name.

A server name consists of one to five parts. Each part is a non-empty string of lowercase letters, and parts are separated by dots. For example, a, ab.cd, abacaba, and a.b.c.d.e are all valid server names.

A path name is a string that may be empty, or consist of one to five parts. Each part starts with the character /, followed by one or more lowercase letters. For example, ``, /a, /aba, and /a/b/c/d/e are all valid path names.

A complete address is formed by concatenating the server name and the path name. For example, a, aba/d/f/g/h, a.b, aba.caba/def/g, and c.d.e.f.g/a/b/c/d/e are all valid addresses.

To restrict access, the organizers prepare multiple filters for each address. Like an address, a filter also consists of two parts: a server name and a path name.

A server filter is a server name, optionally preceded by *.. If a server filter is just a server name, it can only match addresses whose server name is exactly the same. If a server filter is *.<server name>, then it matches all addresses whose server name ends with that server name.

A path filter is a path name, optionally followed by /*. If a path filter is a single path name $R$, it can only match paths that are exactly the same. If a path filter is $R/*$, it matches all paths that have $R$ as a prefix.

An address matches a filter if its server name matches the filter’s server name, and its path name matches the filter’s path name.

Examples of filters and the addresses they match are shown in the table below.

Task: Write a program that, given the filters and the addresses, determines how many filters each address matches.

Input Format

The first line contains two integers: $n$ — the number of filters, and $p$ — the subtask ID ($0 \leq p \leq 3$).

The next $n$ lines each contain one filter, with the same server-name and path-name format as an address.

The next line contains an integer $k$ — the number of addresses.

The next $k$ lines each contain one address.

Output Format

The output should contain $k$ integers. Each integer is the number of filters matched by the corresponding address.

2 0
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c

0
1
0
0

4 0
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d

0
4
3
0
2
1

Hint

Explanation of the sample

In this sample, the filters are $a.bb/c$ and $bb/c/d$, and the addresses are $a.bb$, $bb/c/d$, $a.bb/c/d$, and $bb/c$. Only the address $bb/c/d$ matches the filter $bb/c/d$. The other addresses do not match any filters.

Subtask scoring and notes

Subtask 1 (27 points)

$1 \leq n \leq 1000, 1 \leq k \leq 1000, p = 1$.

All filters start with *. and end with /*.

Subtask 2 (25 points)

$1 \leq n \leq 50 000, 1 \leq k \leq 50 000, p = 2$.

There is no * in any filter.

Subtask 3 (48 points)

$1 \leq n \leq 50 000, 1 \leq k \leq 50 000, p = 3$.

There are no restrictions.

Translation source: GPT 5.2.

Translated by ChatGPT 5