小红定义一个字符串是“好串”，当且仅当该该字符串在长度和它相等的字符串中，"red"子序列的数量是最多的。 例如，"rreedd"是好串，因为包含了8个"red"子序列。而"redred"则不是好串。 现在小红拿到了一个字符串，她有多次询问，每次询问一个区间，你需要回答将该区间对应的子串修改为好串的最小修改次数（每次修改可以修改任意一个字符）。

输入描述:

第一行输入两个正整数，代表字符串的长度和询问次数。第二行输入一个长度为的、仅由小写字母组成的字符串。接下来的行，每行输入两个正整数，代表询问的是第个字符到第个字符组成的子串。

输出描述:

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