Count Prefix Occurrences

Given a list of strings and a list of prefixes, your task is to determine for each prefix how many strings begin with that prefix.

Formally, for each prefix \(p\) provided, count the number of strings \(s\) from the given list such that \(s\) starts with \(p\). That is, if the list of strings is \(S = [s_1, s_2, \dots, s_n]\) and the list of prefixes is \(P = [p_1, p_2, \dots, p_m]\), you must output a list \(C = [c_1, c_2, \dots, c_m]\) where \(c_i = \#\{ s \in S : s \text{ starts with } p_i \}\).

Note that the prefix matching is case-sensitive.

inputFormat

The input is given from stdin in the following format:

1. An integer \(n\) representing the number of strings.
2. \(n\) lines follow, each containing a non-empty string.
3. An integer \(m\) representing the number of prefix queries.
4. \(m\) lines follow, each containing a prefix string.

It is guaranteed that \(0 \leq n, m \leq 10^5\), and each string consists of only printable characters without spaces.

outputFormat

Print a single line to stdout containing \(m\) integers separated by a single space. The \(i\)-th integer represents the number of strings that start with the \(i\)-th prefix from the input.

If there are no prefix queries (i.e. \(m = 0\)), output an empty line.

5
apple
appetite
banana
application
apply
3
appl
ap
ban

3 4 1