题目描述

给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件:

• $1 \leq l \leq r$。
• $s[i: i+l-1]$ 字典序小于 $s[i+l: i+2l-1]$ 。

输入格式

第一行包含一个整数 $c$，表示子任务编号。$c=0$ 表示该测试点为样例。

第二行包含两个正整数 $n, q$，表示字符串长度和询问次数。

第三行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。

接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \leq n$。

输出格式

对于每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。

0
9 3
abacababa
1 4
2 4
3 3

3
1
2

提示

数据范围

对于所有数据，$1 \le n,q\le 5\times 10^5$，$1 \le i + 2r - 1 \le n$，字符串 $s$ 仅包含小写字母。

子任务 1（20%）：$n,q\le 5\times 10^3$ 。

子任务 2（10%）：$n,q\le 10^5$ ，保证 $s$ 中每个字符在 a,b 中随机生成。

子任务 3（20%）：$n,q\le 10^5$ 。

子任务 4（20%）：$n,q\le 3\times 10^5$ 。

子任务 5（30%）：无特殊限制。