Problem Description

There are $ N $ strings consisting only of lowercase English letters. The $ i $th string is $ S_i $. All strings are distinct.

Answer the following $ Q $ queries. The $ i $th query is in the following format:

Query: An integer $ k_i $ and a string $ p_{i,1}p_{i,2}...p_{i,26} $ which is a permutation of {'a','b',...,'z'} are given. Output the lexicographical rank of string $ S_{k_i } $ among the $ N $ strings when the order of characters is $ p_{i,1}p_{i,2}...p_{i,26} $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S_1 $ : $ S_N $ $ Q $ $ k_1 $ $ p_{1,1}p_{1,2}...p_{1,26} $ : $ k_Q $ $ p_{Q,1}p_{Q,2}...p_{Q,26} $

Output Format

Output $ Q $ lines.

The $ i $th line should contain an integer representing the lexicographical rank of string $ S_{k_i } $ among the $ N $ strings for the $ i $th query.

Sample Input and Output

Sample Input #1

5
aa
abbaa
abbba
aaab
aaaaaba
5
1 abcdefghijklmnopqrstuvwxyz
2 bacdefghijklmnopqrstuvwxyz
3 abcdefghijklmnopqrstuvwxyz
4 bacdefghijklmnopqrstuvwxyz
5 abcdefghijklmnopqrstuvwxyz

Sample Output #1

1
2
5
4
2

Sample Input #2

8
abrakatabra
abadaba
abracadabra
atcoder
grand
contest
ababa
a
6
3 abcdefghijklmnopqrstuvwxyz
6 qwertyuiopasdfghjklzxcvbnm
8 poiuytrewqlkjhgfdsamnbvcxz
2 qazwsxedcrfvtgbyhnujmikolp
1 plokmijnuhbygvtfcrdxeszwaq
4 mnbvcxzasdfghjklpoiuytrewq

Sample Output #2

4
8
2
3
4
7

Notes/Hints

Constraints

• $1 \leq N, Q \leq 100000$
• $1 \leq |S_i| \ (1 \leq i \leq N)$
• $S_i \ (1 \leq i \leq N)$ consists only of lowercase English letters.
• The sum of $|S_i|$ is at most $ 400000 $.
• All $ S_i $ are distinct.
• $1 \leq k_i \leq N \ (1 \leq i \leq Q)$
• For all $1 \leq i \leq Q$, $ p_{i,1}p_{i,2}...p_{i,26} $ is a permutation of "abcd...z".

Sample Explanation 1

For the queries with character order "a", the answers are $ 1, 5, 2 $ respectively. For the queries with character order "b", the answers are $ 2, 4 $ respectively.

见题面 Input 部分

见题面 Output 部分