Problem Description

Define the common prefix of two strings as the substring that both strings share starting from the beginning. For example, the common prefix of the string identity and the string idealistic is ide.

A database contains $N$ strings.

The algorithm used to search for a string $W$ in this database is very primitive: it compares $W$ with the strings in the database one by one. For each pair of strings, it compares characters one by one until it finds a mismatching character or reaches the end of one of the strings, and then performs one final comparison to determine whether the two strings have the same length. When $W$ is found in the database, the algorithm stops.

By analyzing this algorithm, we find that the number of steps needed to find $W$ in the database equals the number of strings compared with $W$, plus the sum of the lengths of the common prefixes between $W$ and all strings that were compared with it.

There are $Q$ query strings.

Write a program that computes, for each query string, how many steps the program needs to find this word in the database.

Please note the unusual memory limit for this problem.

Input Format

The first line contains an integer $N$, the number of strings in the database.

The next $N$ lines each contain one string from the database. These strings are given in the order in which the algorithm checks them, and they are all distinct.

The next line contains an integer $Q$, the number of query strings.

The next $Q$ lines each contain one query string.

Output Format

For each query string, output one line with one integer, the number of steps required for the program to find this word in the database.

5
hobotnica
robot
hobi
hobit
robi
4
robi
hobi
hobit
rakija 

12
10
16
7 

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun 

8
29
14

Hint

For $100\%$ of the data, $1 \le N, Q \le 3 \times 10^4$, all strings have length $< 30$, and they contain only lowercase letters.

Explanation for Sample 2:

For Sample 2, the number of steps used to search for the string krampus is $8$, because we only need to compare the first character of each string in the database with this string.

When searching for malnar, each of the first three strings requires $3$ comparisons, and each of the remaining five strings requires $4$ comparisons, so there are $29$ comparisons in total.

To find the string majmun, we perform $14$ comparisons in total. For the first word, we make $6$ successful comparisons, but the last comparison determines that the string majmunica is longer than majmun. For the second string, we also make $6$ successful comparisons, and in the final comparison we find that the two strings have equal length, so the algorithm stops.

The score for this problem follows the original contest setting, with a full score of $90$ points.

Translated by ChatGPT 5