题目描述

测试机器人的场地由 $n$ 个格子组成，从左到右编号为 $1$ 到 $n$。每个格子中有一个小写英文字母，连起来形成字符串 $s$。

有两个机器人可以在场地中移动。它们满足：

• 两个机器人都知道完整字符串 $s$；
• 两个机器人可以自由交换信息；
• 它们始终知道彼此之间的距离，以及哪个机器人在左、哪个在右；
• 每个机器人可以读取自己脚下的字母。

一步中，机器人可以在交换信息后向左或向右移动一格。如果机器人试图走到第 $1$ 个格子左边或第 $n$ 个格子右边，它会被摧毁。

科学家要进行 $q$ 次实验。第 $i$ 次实验中，第一个机器人初始在 $x_i$，第二个机器人初始在 $y_i$。机器人的目标是在不冒被摧毁风险的前提下，访问尽可能多的不同格子。

请对每次实验输出机器人最多能访问多少个不同格子。

输入格式

第一行输入两个整数 $n,q$。

第二行输入长度为 $n$ 的小写字符串 $s$。

接下来 $q$ 行，每行两个整数 $x_i,y_i$。

输出格式

对每次实验输出一个整数，表示最多能访问的不同格子数。

样例

10 4
aabaabbaab
4 5
8 5
2 3
1 1

3
10
3
3