SvT

题目背景

(我并不想告诉你题目名字是什么鬼)

题目描述

有一个长度为 $n$ 的仅包含小写字母的字符串 $S$,下标范围为 $[1,n]$。 现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在 $S$ 中出现的起始位置来表示),求这些后缀两两之间的 LCP(最长公共前缀)的长度之和。一对后缀之间的 LCP 长度仅统计一遍。

输入输出格式

输入格式


第一行两个正整数 $n,m$,分别表示 $S$ 的长度以及询问的次数。 接下来一行有一个字符串 $S$。 接下来有 $m$ 组询问,对于每一组询问,均按照以下格式在一行内给出: 首先是一个整数 $t$,表示共有多少个后缀。接下来 $t$ 个整数分别表示 $t$ 个后缀在字符串 $S$ 中的出现位置。

输出格式


对于每一组询问,输出一行一个整数,表示该组询问的答案。由于答案可能很大,仅需要输出这个答案对于 $\text{23333333333333333}$ (一个巨大的质数)取模的余数。

输入输出样例

输入样例 #1

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

输出样例 #1

0
0
2

说明

样例解释: 对于询问一,只有一个后缀 `oqqq`,因此答案为 $0$。 对于询问二,有两个后缀`poqqq`以及`qqq`,两个后缀之间的 LCP 为 $0$,因此答案为 $0$。 对于询问三,有四个后缀 `popoqqq` , `opoqqq` , `qqq` , `qq`,其中只有 `qqq`,`qq` 两个后缀之间的LCP不为 $0$,且长度为 $2$,因此答案为 $2$。 对于 $100\%$ 的测试数据,有 $|S|\le 5\times 10^5$,且 $\sum t\le3\times10^6$。 特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次。 题目来源:bzoj 3879