简单字符串题
时间限制：C/C++/Rust/Pascal 7秒，其他语言14秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给出一个长度为 n 的小写字符串 a_1a_2\cdots a_n，第 i 个位置有权值 b_i。

\hspace{15pt}现在，一共进行 Q 次查询，对于一次查询给出的区间 [x, y] \left(1\le x\le y\le n\right)，记模式串 S=a[x..y] = a_xa_{x+1}\cdots a_y、\textrm{occ}(S, T) 为字符串 S 在字符串 T 中出现的次数（允许重叠）。定义连续非空子串 a[l..r] \left(1\le l\le r\le n\right) 的价值为：

\displaystyle\textrm{occ}(S, a[l..r]) \times \sum_{i=l}^r b_i。

\hspace{15pt}求 a 的所有子串的价值和。由于答案可能很大，请将答案对 998\,244\,353 取模后输出。

输入描述:

\hspace{15pt}第一行输入两个整数 n,Q \left(1\le n,Q\le 10^6\right)，表示字符串长度、查询次数。
\hspace{15pt}第二行输入一个长度为 n，仅由小写字母构成的字符串 a。
\hspace{15pt}第三行输入 n 个整数 b_1,b_2,\cdots,b_n \left(0\le b_i<998\,244\,353\right)，表示第 i 个位置的权值。
\hspace{15pt}此后 Q 行，第 i 行输入两个整数 x_i,y_i \left(1\le x_i\le y_i\le n\right)，表示第 i 次查询的区间。

输出描述:

\hspace{15pt}对于每一次询问，新起一行输出一个整数，表示原字符串所有子串的价值和对 998\,244\,353 取模后的结果。
示例1

输入

复制 
5 4
abaab
1 2 1 2 1
1 1
1 2
2 3
3 4

输出

复制 
96
40
31
31

备注: