提示: 欢迎访问OurACM平台。
Problem 1619 Revival's word

Accept: 13    Submit: 93
Time Limit: 5000 mSec    Memory Limit : 262144 KB

Problem Description

Recently, oaiei is crazy with word games, and the guess game is shown as follows:

Given a word, you need to rearrange the letters in the word and form a new word, and the new word have a certain significance.

For example: “a gentleman” can be converted into “elegant man”.

Clearly, oaiei do not want to do these trivial things, he wants your help. For a given word, you should find all the words whose letters are the same to the given word in the dictionary.

For example: “dame” and “made” are the results of “adem”.

After a period of time, oaiei has found, only to find the words whose letters are the same to the given word is far from enough. He would like to know how many words can be found in the dictionary using some letters of the word (not necessarily all use).

For example: “gentleman” can construct the word “gentle”, “man”, and so on.

Oaiei is lazy, can you help him?

Input

There are multiple tests. For each test, the first line is an integer N(1<=N<=100000), denoting the size of dictionary. The following N lines, each line contains a string S, S’s length is not exceed 26 and is not empty. The N+2 th line is an integer M(1<=M<=10000), denoting the number of queries, the following M lines, each line contains a string T, T’s length is not exceed 26 and is not empty. The strings are all lowercase letters.

Output

For each query, output the number of words whose letters are the same to the given word in the dictionary and the number of words can be found in the dictionary using some letters of the given word. You should separate the two integers by a blank space.

Sample Input

5 by girl class graduate bye 2 by bye

Sample Output

1 1 1 2

Source

Summer Training Qualification I

Submit  Back  Status  Discuss