题目描述

(<span style="font-family:宋体;

mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">我并不想告诉你题目名字是什么鬼</span>)

mso-hansi-font-family:"Times New Roman"">有一个长度为

n<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">的仅包含小写字母的字符串</span>S,<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">下标范围为</span>[1,n].

</p>

mso-hansi-font-family:"Times New Roman"">现在有若干组询问

,<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">对于每一个询问</span>,<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">我们给出若干个后缀</span>(<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">以其在</span>S<span style="font-family:

宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">中出现的起始位置来表示</span>),<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";

mso-hansi-font-family:"Times New Roman"">求这些后缀两两之间的</span>LCP(LongestCommonPrefix)<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman"">的长度之和</span>.<span style="font-family:

宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">一对后缀之间的</span>LCP<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";

mso-hansi-font-family:"Times New Roman"">长度仅统计一遍</span>.

</p>

输入格式

第一行两个正整数n,m,分别表示S的长度以及询问的次数.

接下来一行有一个字符串S.

接下来有m组询问,对于每一组询问,均按照以下格式在一行内给出:

首先是一个整数t,表示共有多少个后缀.接下来t个整数分别表示t个后缀在字符串S中的出现位置.

输出格式

7 3
popoqqq
1 4
2 3 5
4 1 2 5 6

0
0
2
Hint
样例解释:
对于询问一,只有一个后缀”oqqq”,因此答案为0.
对于询问二,有两个后缀”poqqq”以及”qqq”,两个后缀之间的LCP为0,因此答案为0.
对于询问三,有四个后缀”popoqqq”,”opoqqq”,”qqq”,”qq”,其中只有”qqq”,”qq”两个后缀之间的LCP不为0,且长度为2,因此答案为2.
对于100%的测试数据,有S<=5*10^5,且Σt<=3*10^6.
特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次.