题目描述

有 $N$ 个仅包含小写字母的字符串。第 $i$ 个字符串是 $S_i$。每个字符串都是唯一的。

回答下面的 $Q$ 个查询。第 $i$ 个查询的格式如下：

查询：给定一个整数 $k_i$ 和一个字符串 $p_{i,1}p_{i,2}...p_{i,26}$，该字符串结果来自于对 {a$,$b$,...,$z} 进行排列。输出当字面顺序为 $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$ 是唯一的。
• $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