简单字符串题

题号：NC312053
时间限制：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$ 取模后输出。

输入描述:

第一行输入两个整数 ，表示字符串长度、查询次数。
第二行输入一个长度为 ，仅由小写字母构成的字符串 。
第三行输入  个整数 ，表示第  个位置的权值。
此后  行，第  行输入两个整数 ，表示第  次查询的区间。

输出描述:

对于每一次询问，新起一行输出一个整数，表示原字符串所有子串的价值和对  取模后的结果。

示例1

输入

复制

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

备注: