/ 
Time Limit: 6 sec / Memory Limit: 512 MB
配点 : 1100 点
問題文
英小文字のみからなる文字列がN個あります。i番目の文字列はS_iです。すべての文字列は相異なります。
次のQ個のクエリに答えてください。i番目のクエリは、以下のような形式です。
クエリ: 整数k_iと、{'a','b',...,'z'}の並び替えである文字列p_{i,1}p_{i,2}...p_{i,26}が与えられる。文字の順序がp_{i,1} < p_{i,2} < ... < p_{i,26}のとき、文字列S_{k_i}はN個の文字列たちの中で辞書順で何番目か出力せよ。
制約
- 1 ≦ N,Q ≦ 100000
- 1 ≦ | S_i | (1 ≦ i ≦ N)
- S_i (1 ≦ i ≦ N)は英小文字のみからなる。
- | S_i |たちの合計は400000以下。
- S_iたちはすべて相異なる。
- 1 ≦ k_i ≦ N(1 ≦ i ≦ Q)
- すべての1 ≦ i ≦ Qに対し、p_{i,1}p_{i,2}...p_{i,26}は"abcd...z"の並び替えである。
入力
入力は以下の形式で標準入力から与えられる。
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}
出力
Q行出力せよ。
i行目には、i番目のクエリに対し、文字列S_{k_i}はN個の文字列たちの中で辞書順で何番目かを表す整数を出力せよ。
入力例 1
5 aa abbaa abbba aaab aaaaaba 5 1 abcdefghijklmnopqrstuvwxyz 2 bacdefghijklmnopqrstuvwxyz 3 abcdefghijklmnopqrstuvwxyz 4 bacdefghijklmnopqrstuvwxyz 5 abcdefghijklmnopqrstuvwxyz
出力例 1
1 2 5 4 2
文字の順序が"a" < "b"のとき、入力の文字列を辞書順にソートすると"aa","aaaaaba","aaab","abbaa","abbba"となるので、 1,3,5番目のクエリにはそれぞれ1,5,2と答えます。
また、文字の順序が"b" < "a"のとき、入力の文字列を辞書順にソートすると"abbba","abbaa","aa","aaab","aaaaaba"となるので、 2,4番目のクエリにはそれぞれ2,4と答えます。
入力例 2
8 abrakatabra abadaba abracadabra atcoder grand contest ababa a 6 3 abcdefghijklmnopqrstuvwxyz 6 qwertyuiopasdfghjklzxcvbnm 8 poiuytrewqlkjhgfdsamnbvcxz 2 qazwsxedcrfvtgbyhnujmikolp 1 plokmijnuhbygvtfcrdxeszwaq 4 mnbvcxzasdfghjklpoiuytrewq
出力例 2
4 8 2 3 4 7
Score : 1100 points
Problem Statement
There are N strings of lowercase alphabet only. The i-th string is S_i. Every string is unique.
Provide answers for the Q queries below. The i-th query has the following format:
Query: An integer k_i and a string p_{i,1}p_{i,2}...p_{i,26} that results from permuting {a,b,...,z} are given. Output the sequence of the string S_{k_i} among the N strings in lexicographical order when the literal sequence is p_{i,1}<p_{i,2}<...<p_{i,26}.
Constraints
- 1 ≦ N,Q ≦ 100000
- 1 ≦ |S_i| (1 ≦ i ≦ N)
- S_i (1 ≦ i ≦ N) is a string of lowercase alphabet.
- The sum of |S_i| is no more than 400000.
- Every S_i is unique.
- 1 ≦ k_i ≦ N (1 ≦ i ≦ Q)
- For all 1 ≦ i ≦ Q, p_{i,1}p_{i,2}...p_{i,26} is a permutation of
abcd...z.
Input
Inputs are provided from standard inputs in the following form.
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
Output Q lines.
On line i, for the i-th query, output an integer indicating the sequence of the string S_{k_i} among the N strings in lexicographical order.
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
When the literal sequence is a < b, sorting the input strings in lexicographical order yields aa, aaaaaba, aaab, abbaa, abbba. The answers to queries 1, 3, and 5 are thus 1, 5, and 2, respectively.
When the literal sequence is b < a, sorting the input strings in lexicographical order yields abbba, abbaa, aa, aaab, aaaaaba. The answers to queries 2 and 4 are thus 2 and 4, respectively.
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