辞书
题号：NC296300
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}由于撤云读错了 2025 ICPC 武汉邀请赛的 J 题，因此提出了另一个问题。
\hspace{15pt}给你一个长度为 n 的字符串 s=s_1s_2\cdots s_n（下标从 1 开始），有 q 次操作。
\hspace{15pt}每次操作给出两个整数 l, r，表示区间 s[l..r]，标记所有起始于位置 l 且以子串 s[l..r] 为前缀的子串。每次操作后，输出到当前为止所有被标记的子串的数量。

【名词解释】
\hspace{15pt}s[l..r]：代表字符串 s 从下标 l 开始、到下标 r 结束的子串（双闭）。
\hspace{15pt}字符串的前缀：从字符串起始位置开始的一段连续子串。对于字符串 s，其前 i 个字符构成的字符串称为 s 的第 i 个前缀，记为 s[1..i]。例如，对于字符串 \texttt{，其前缀有 \texttt{、\texttt{ 和 \texttt{。

输入描述:

\hspace{15pt}第一行输入两个整数 n, q \left(1 \leq n, q \leq 10^5\right)，表示字符串长度、操作次数。 
\hspace{15pt}第二行输入一个长度为 n，由小写字母构成的字符串 s，表示给定的字符串。 
\hspace{15pt}此后 q 行，第 i 行输入两个整数 l_i, r_i \left(1 \leq l_i \leq r_i \leq n\right)，表示第 i 次操作的区间。

输出描述:

\hspace{15pt}对于每次操作，新起一行输出一个整数，表示到当前为止所有被标记的子串的数量。
示例1

输入

复制 
5 6
abcde
1 2
1 2
2 3
5 5
4 5
3 3

输出

复制 
4
4
7
8
9
12

说明

\hspace{15pt}对于第一次询问，\texttt{、\texttt{、\texttt{、\texttt{ 被标记。
\hspace{15pt}对于第二次询问，全部子串都已经被标记，没有新增。
示例2

输入

复制 
4 2
aaaa
1 1
1 2

输出

复制 
4
4