小红的好串
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红定义一个字符串是“好串”，当且仅当该该字符串在长度和它相等的字符串中，"red"子序列的数量是最多的。
例如，"rreedd"是好串，因为包含了8个"red"子序列。而"redred"则不是好串。

现在小红拿到了一个字符串，她有多次询问，每次询问一个区间，你需要回答将该区间对应的子串修改为好串的最小修改次数（每次修改可以修改任意一个字符）。

输入描述:

第一行输入两个正整数n,q，代表字符串的长度和询问次数。
第二行输入一个长度为n的、仅由小写字母组成的字符串。
接下来的q行，每行输入两个正整数l,r，代表询问的是第l个字符到第r个字符组成的子串。
1\leq n,q \leq 10^5
1\leq l \leq r \leq n

输出描述:

输出q行，每行输出一个整数，代表将该字符串修改为好串的最小修改次数。
示例1

输入

复制 
8 3
rreeddrr
1 4
1 6
3 8

输出

复制 
1
0
6

说明

第一次询问的子串是"rree"，修改为"rred"即可，只需要修改1个字符。
第二次询问的子串是"rreedd"，本身即为好串，不需要修改。
第三次询问的子串是"eeddrr"，修改为"rreedd"需要修改6次。