2023 年上海市大学生程序设计竞赛 - 七月赛

D. 回文文回

单点时限: 2.0 sec

内存限制: 512 MB

  • 回文串“是翻转后仍然不变的字符串,例如”qwq”,”abba”。
  • 一个字符串中的”回文子串“是指这个字符串一个具有回文性质 的子串,例如”qwq”中的回文字串有”q”,”w”,”q”,”qwq”。
  • 但你认为这些还是太简单了,于是你定义一个字符串中的”本质不同的回文子串“是去重后的回文子串,例如”qwq”中的”本质不同回文子串”有”q”,”w”,”qwq”。
  • 但这看起来还是没意思,于是你定义”本质不同公共回文子串“是两个字符串的”本质不同回文子串”的集合的交集,例如”qaqw”和”qwq”的”本质不同的公共回文子串”是”q”,”w”。

现在有 $n$ 个小写字母字符串和 $m$ 组询问,把字符串编号为 $1\sim n$ ,每组询问会询问字符串编号为 $i,j$ ,”本质不同的公共回文子串“的数量。如果 $i=j$ ,则是问编号为 $i$ 的字符串有多少本质不同的公共回文子串。

输入格式

第一行两个正整数,分别依次表示 $n$ 和 $m$。 ($2 \le n \le 10^5, 1\le m \le 10^5$)
接下来 $n$ 行,每行一个非空小写字母字符串。 (所有字符串长度总和 $\le 2.2\times 10^5$)
再接下来 $m$ 行,每行两个正整数 $i,j$ 表示询问第 $i$ 个字符串和第 $j$ 个字符串的本质不同字符串数量。

输出格式

$m$ 行,每行一个非负整数表示答案。

样例

Input
4 4
z
naxvbir
vxa
lslnzfumuvtsf
4 4
2 4
1 4
3 3
Output
11
2
1
3
Input
4 4
ajlltc
gicxwxbid
xw
mcugbdyd
4 4
1 2
4 4
4 3
Output
8
1
8
0
Input
4 4
ttld
dltjjustaat
jjustaatsujjjjustaat
dltjjustaats
4 2
1 2
2 4
4 2
Output
10
3
10
10
Input
4 4
ncrhgvhmjqp
wvkv
vk
y
4 3
3 4
3 4
2 4
Output
0
0
0
0