题目描述

若若又在机厅打舞萌 DX 了！

今天她打的歌曲是妄想感傷代償連盟。哼着再挑战 转生 瞬间移动的歌词，她想到了这样一道题：

你有一个长度为 $n$ 的仅包含大、小写英文字母的字符串 $S$，其中第 $i$ ($1 \leq i \leq n$) 个字符为 $S_i$。

如果 $S_i$ 和 $S_j$ ($1 \leq i < j \leq n$) 满足它们都是大写字母或小写字母，或者它们是同一个字母大小写不同的表示，则你可以在 $S_i$ 和 $S_j$ 之间进行传送，每次传送需要 $1$ 秒钟。

此外，你也可以在相邻两个字符之间移动，即从 $S_i$ ($1 \leq i \leq n$) 移动到 $S_j$ ($1 \leq j \leq n$, $\left| i - j \right| = 1$)，每次移动也需要 $1$ 秒钟。

假设你现在的位置在 $S_x$ 处，你至少需要多久才能到达 $S_y$ 呢？

输入格式

第一行两个正整数 $n$ ($2 \leq n \leq 10^5$) 和 $q$ ($1 \leq n \leq 10^5$)，用一个空格隔开，表示字符串 $S$ 的长度为 $n$，有 $q$ 次询问。

第二行一个长度为 $n$ 的字符串 $S$，仅包含大、小写英文字母。

之后 $q$ 行，每行两个正整数 $x$ ($1 \leq x \leq n$) 和 $y$ ($1 \leq y \leq n$, $x \neq y$)，表示询问从 $S_x$ 移动到 $S_y$ 至少需要多久。

输出格式

对于每次询问，输出一行一个正整数 $t$，表示从 $S_x$ 移动到 $S_y$ 至少需要 $t$ 秒钟。

样例

样例输入 1

5 1
WOruo
5 1

样例输出 1

2

样例输入 2

7 1
BaiYang
2 5

样例输出 2

1