P7409 SvT

（我并不想告诉你题目名字是什么鬼）

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

无

无

样例解释: 对于询问一，只有一个后缀 `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