题目描述

The field for testing the robots consists of $n$ cells numbered by integers $1$ to $n$ from left to right. Each cell contains a letter of the English alphabet; reading the letters from the first to the $n$-th cell forms the string $s$.

There are two robots that can move across the field, with the following conditions:

• The robots know the string $s$;
• The robots can freely exchange information;
• The robots always know the distance between them, as well as which robot is to the left and which is to the right;
• Each of the two robots can read the letter that is directly below it;

In one step, a robot can, after exchanging information with the other robot, move to an adjacent cell to the left or to an adjacent cell to the right. If a robot attempts to move left of the first cell or right of the $n$-th cell, it is destroyed.

The scientists want to conduct $q$ experiments, in the $i$-th of which the first robot is placed at position $x_i$, and the second at position $y_i$. The goal of the robots in each experiment is to visit as many different cells as possible. For each experiment, it is necessary to determine the maximum number of cells that the robots can visit without risking destruction.

输入格式

The first line contains a pair of numbers $n$ and $q$ ($1 \le n,q \le 300\,000$) --- the number of cells and the number of experiments.

The second line contains the string $s$ of length $n$, consisting of $n$ lowercase Latin letters.

In the following $q$ lines, pairs of numbers $x_i$, $y_i$ are given ($1 \le x_i , y_i \le n$).

输出格式

For each experiment, output the maximum number of different cells that the robots can visit.

10 4
aabaabbaab
4 5
8 5
2 3
1 1

3
10
3
3

提示

Consider the last experiment in the example. The robots start at the same point and see the letter $\texttt{a}$. They understand that moving left is dangerous, as it may lead to the destruction of the robot. However, moving right is safe, as the last letter of the string is $\texttt{b}$. One or both robots move to the right until they reach the letter $\texttt{b}$. Upon reaching the letter $\texttt{b}$, the robots know that the string before it was $\texttt{aab}$, which could be either the beginning or the end of the string; they cannot go beyond its limits without risking destruction, so they managed to visit a total of $3$ cells.