#P18747. [正睿NOI2021训练] 字符串

[正睿NOI2021训练] 字符串

字符串

给定长度为 nn 的小写英文字母字符串 SS,记从位置 ii 开始的后缀为 SiS_i。再给定长度为 nn 的正整数序列 a1,…,ana_1,\ldots,a_n。

有 QQ 次询问,每次给出 l,rl,r,求满足下列条件的有序对 (i,j)(i,j) 的数量:

$$l\le i,j\le r,\qquad \operatorname{lcp}(S_i,S_j)\ge a_i.$$

lcp⁡\operatorname{lcp} 表示两个字符串的最长公共前缀长度。允许 i=ji=j。条件中的阈值是 aia_i,因此交换 i,ji,j 后不一定仍合法;若 ai>∣Si∣a_i>|S_i|,以 ii 为第一项的所有数对都不合法。

输入格式

第一行两个正整数 n,Qn,Q。

第二行字符串 SS;第三行 nn 个正整数 a1,…,ana_1,\ldots,a_n。

接下来 QQ 行,每行两个整数 l,rl,r。

输出格式

每次询问输出一行一个整数,表示合法有序对数量。

数据范围

1≤n,Q≤1051\le n,Q\le10^5,1≤ai≤n1\le a_i\le n,1≤l≤r≤n1\le l\le r\le n。答案需要 64 位整数。

样例 1

输入

5 4
aabaa
1 2 1 2 1
1 3
2 4
3 5
1 5

输出

4

3

4

12