小红的好子串询问

题号：NC269965
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红定义一个字符串是“好串”，当且仅当该字符串不包含长度不小于 2 的回文子串。
现在小红拿到了一个仅包含"red"三种字符的字符串，她有如下两个操作：
· 输入 1 x chr：将第 $x$ 个字符修改为 $chr$
· 输入 2 l r：询问第 $l$ 个字符到第 $r$ 个字符的子串再修改最少多少个字符可以变成好串（每次修改后也必须是"red"三种字符中的一种）。
你能帮帮她吗？

输入描述:

第一行输入两个正整数，代表字符串长度、操作次数。
第二行输入一个仅包含长度为的、"red"三种字符的字符串。
接下来的行，每行输入一个操作或者，含义如上所述。




保证至少有一次操作 2。

本题有5%的数据满足：
有25%的数据满足：
另外有20%的数据满足：所有操作均为操作2。

输出描述:

对于每个操作 2，输出一个整数表示答案，即子串变成好串的最小修改次数。

示例1

输入

复制

5 3
deder
2 2 4
1 3 r
2 1 3

输出

复制

1
0

说明

第一次询问的子串是"ede"，将第一个或者第三个字符修改为'r'可以变成好串。
第二次询问的子串是"der"，是好串。