← 返回题目列表

Codeforces · 145/E

E. 幸运查询

中文机器翻译题面 查看原题

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