Number Of Valid Words

hard

1. You are given N number of words.
2. You are given M puzzles in the form of M strings.
3. For a given puzzle, a word is valid if both the following conditions are confirmed - 
    Condition 1 -&gt; Word contains the first letter of puzzle.
    Condition 2 -&gt; For each letter in word, that letter should be present in puzzle.
4. You have to print the number of valid words corresponding to a puzzle.

Input Format

A number N N space separated strings A number M M space separated strings

Output Format

Check the sample ouput and question video.

Constraints

1 &lt;= N &lt;= 10^5
4 &lt;= length of word &lt;= 50
1 &lt;= M &lt;= 10^4
length of puzzle string = 7
puzzle string doesn't contain any repeated characters.

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

7
aaaa asas able ability actt actor access 
6
aboveyz abrodyz abslute absoryz actresz gaswxyz

Output

aboveyz -> 1
abrodyz -> 1
abslute -> 3
absoryz -> 2
actresz -> 4
gaswxyz -> 0

Minimum Number Of Software Developers

Triplets - 1