题目描述

两个字符串之间的最长公共子串是出现在两个字符串中的最长连续字符序列。给定一个长度为 $n$ 的字符串 $s$ 和 $q$ 次查询，每次查询给出两个参数 $l$ 和 $r$，计算前缀 $s[1..l]$ 和后缀 $s[r..n]$ 之间的最长公共子串的长度。

输入格式

第一行包含两个正整数 $n$ 和 $q$ （$1 \leq n, q \leq 2 \cdot 10^5$）—字符串 $s$ 的长度和查询操作的数量。第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s$。接下来的 $q$ 行，每行包含两个正整数 $l$ 和 $r$ （$1 \leq l, r \leq n$）。

输出格式

对于每个查询操作，在单独的一行上输出一个整数，表示 $s[1..l]$ 和 $s[r..n]$ 之间的最长公共子串的长度。

10 14
aaabaaaaab
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
7 1
4 8
6 10
5 5
2 5

1
2
3
4
4
4
3
2
1
7
3
1
4
2