Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3462
Nobita's New Filesystem

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Nobita always forgets where a file is saved in his computer. In order to help him, Doraemon installs a tag-based filesystem in his computer.

A tag is a non-empty string which contains only lower case letters, numbers and '+', '.', '-', '_' symbols. In the new filesystem, a file is named using one or more distinct tags enclosed in square brackets. Two files are same if and only if they contain exactly same tags, where the orders of the tags do not matter. For example, '[comic][naruto][01]' and '[01][naruto][comic]' are same file.

In the new filesystem, a file can be matched when querying tags are exactly part of tags of that file. For example, '[comic][naruto][01]' and '[comic][naruto][02]' can both be matched when querying '[comic]' or '[comic][naruto]'. They can neither be matched when querying '[comic][foo]'.

Using the new filesystem, Nobita can find files easily. However, there is a defect in the filesystem: if a file is matched, then the full file must be read.

Now, you are given all files (names) and corresponding sizes (in bytes). Could you figure out how many bytes are read if Nobita is using some tags?

Input

This problem contains multi test cases (no more than 6). Please proceed till the end of input.

The first line of one case contains an integer N (0 ≤ N ≤ 1024), indicating the number of files. It is guaranteed that files in this section are distinct. There are 2048 distinct tags at most.

Following N lines, each line contains one filename following a positive 32-bit integer indicating the size of the file, in bytes. The filename contains 1023 characters at most.

The next line contains an integer K (0 ≤ K ≤ 8192), indicating the number of queries.

Following K lines, each line contains one query string (also a valid filename), which contains 1023 characters at most.

Output

For each query, output one integer B in one line, where B is the total bytes should be read. If no file is matched, output 0.

Sample Input

5
[comic][naruto][01] 1024
[comic][naruto][02] 1024
[comic][inuyasha][01] 1024
[comic][inuyasha][02] 1024
[comic][inuyasha][03] 1024
3
[inuyasha]
[comic][01]
[ost]

Sample Output

3072
2048
0

Author: WU, Jun
Contest: ZOJ Monthly, January 2011
Submit    Status