[SGU505] Prefixes and Suffixes

题目描述

Andrew 在研究基因时发现，许多特征都与某些前缀和后缀是否出现有关。

我们把一条基因表示成一个只包含小写英文字母的非空字符串。现在给定 $n$ 条基因，并回答 $m$ 个询问。

每个询问给出两个非空字符串 $p,s$，你需要求出有多少条给定基因同时满足：

• $p$ 是它的前缀；
• $s$ 是它的后缀。

注意，前缀与后缀允许发生重叠。

输入格式

第一行一个整数 $n$，表示基因数量。

接下来 $n$ 行，每行一个非空的小写英文字母字符串，表示一条基因。

接下来一行一个整数 $m$，表示询问数量。

接下来 $m$ 行，每行两个非空字符串 $p,s$，分别表示要求的前缀和后缀。

输出格式

对于每个询问输出一行一个整数，表示同时以 $p$ 为前缀、以 $s$ 为后缀的给定基因数量。

数据范围

• $1\le n\le 10^5$；
• 所有给定基因的长度总和不超过 $10^5$；
• $1\le m\le 10^5$；
• 所有询问中前缀和后缀的长度总和不超过 $2\times 10^5$；
• 所有字符串均只包含小写英文字母。

样例

样例输入

3
aaaaa
abacabaa
avtobus
6
a a
a aa
aa a
aaaaa aaaa
abac caba
abac a

样例输出

2
2
1
1
0
1