Petya非常喜欢幸运数字。大家都知道,幸运数字是正整数,其小数记录中仅包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。
Petya 带回家长度为 n 的字符串 s。该字符串仅由幸运数字组成。数字从 1 开始从左到右编号。现在 Petya 应该执行以下形式的 m 个查询:
- switch l r — 在索引从 l 到 r 的所有位置上“切换”数字(即将其替换为相反数),包括:每个数字 4 替换为 7,每个数字 7 替换为 4 (1 ≤ l ≤ r ≤ n);
- count — 查找并在屏幕上打印字符串 s 的最长非递减子序列的长度。
字符串 s 的子序列是可以通过删除 s 的零个或多个元素而从 s 获得的字符串。如果每个连续数字不小于前一个数字,则称字符串为非递减字符串。
帮助 Petya 处理请求。
输入
第一行包含两个整数n和m (1 ≤ n ≤ 106, 1 ≤ m ≤ 3·105)——字符串s的长度和对应的查询次数。第二行包含 n 个不带空格的幸运数字——Petya 的初始字符串。接下来的 m 行包含语句中描述的形式的查询。
输出
对于每个查询计数,在一行上打印一个答案。
示例
输入 #1
2 3 47 count switch 1 2 count
输出 #1
2 1
输入 #2
3 5 747 count switch 1 1 count switch 1 3 count
输出 #2
2 3 2
注意
在第一个样本中,字符串 s 完成某些操作后的时间顺序如下(所寻求的最大子序列用粗体标记):
1. 47
2. 74
3. 74
1. 747
2. 447
3. 447
4. 774
5. 774