Dominik 是一个非常特别的学生，他非常喜欢玩不同尺寸的蓝色和红色立方体。

他决定按照以下两个奇特的规则来搭建积木塔：

• 直接位于另一个立方体正上方的立方体，其颜色不能与下方的立方体相同。
• 在塔中，位于某个立方体上方的所有立方体，其尺寸都必须小于该立方体。

Dominik 打开了他的玩具箱，里面恰好有 $n$ 个立方体。对于每个 $i$（$1 \le i \le n$），Dominik 恰好有一个尺寸为 $i$ 的立方体，它的颜色要么是红色，要么是蓝色。

Dominik 玩腻了搭积木塔，于是他提出了 $q$ 个困难的问题。在每个问题中，Dominik 会想到两个数 $l$ 和 $r$。他想知道，为了使搭建的塔中仅包含尺寸在 $l$ 到 $r$（含）之间的立方体，且每座塔都符合他的奇特规则，他最少需要搭建多少座塔。每个尺寸在 $l$ 到 $r$ 之间的立方体都必须被使用，即必须被放置在某座塔中。

由于大学期中考试临近，Dominik 必须花大量时间学习，因此他请求你帮助他回答这 $q$ 个问题。

输入格式

第一行包含两个自然数 $n$ 和 $q$（$1 \le n, q \le 1 \cdot 10^5$），分别表示立方体的数量和问题的数量。

第二行包含一个字符串 $s$，其中字符 $s_i$ 表示尺寸为 $i$ 的立方体的颜色。字符串中的每个字符都将是 'P' 或 'C'。

接下来的 $q$ 行中，每行包含两个数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示 Dominik 询问的左右边界。

输出格式

输出 $q$ 行，每行输出一个整数，表示对 Dominik 对应问题的回答。

子任务

样例

输入样例 1

7 4
PPCPPCC
1 7
1 5
3 7
4 5

输出样例 1

3
3
2
2

输入样例 2

6 2
CCCCCC
1 6
2 5

输出样例 2

6
4

输入样例 3

16 1
PPPCPCCCCCCPPPPP
1 16

输出样例 3

6

说明

样例 2 解释：所有立方体都是红色的（'C'），因此任何包含至少 2 个立方体的塔都不符合 Dominik 的规则。由此可知，每座塔只能恰好包含 1 个立方体，因此每个问题的答案就是 $l$ 到 $r$ 之间的立方体数量，即 $r - l + 1$。