新年快乐 。゚・ (⁄ ⁄>⁄ ︿ ⁄<⁄ ⁄) ・゚。

1719. 字典树

给定 n 个只由小写字母组成字符串,第 i 个字符串为 S_i 。接下来有 m 个询问,第 i 个询问给定一个只由小写字母组成的字符串 T_i ,对于每个询问,求有多少个字符串 S 满足其前缀为 T_i 。不保证 S 各不相同。

输入

首先输入一行一个整数 n(1\le n\le10^5)

接下来输入 n 行,第 i 行一个字符串 S_i(1\le S_i\le5\times 10^5) 。保证 \sum_{i=1}^nS_i\le 5\times 10^5

接下来输入一行一个整数 m(1\le m\le10^5)

接下来输入 m 行,第 i 行一个字符串 T_i(1\le T_i\le 5\times 10^5) 。保证 \sum_{i=1}^nT_i\le 2\times10^6

输出

对于每个询问,输出一行一个整数,代表询问结果

样例

标准输入 复制文本
8
smile
sweet
sister
sadistic
suprice
service
space
suanfa
6
string
s
su
sum
sad
t
标准输出 复制文本
0
8
2
0
1
0
标准输入 复制文本
7
acautomaton
acautomaton
acautomation
suffixarray
suffixautomation
generalsuffixautomation
sunday
7
trie
acautomaton
acautomat
acauto
su
sun
sudormrf
标准输出 复制文本
0
2
3
3
3
1
0
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 9
通过 5