Codeforces

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya brought home string s with the length of n. The string only consists of lucky digits. The digits are numbered from the left to the right starting with 1. Now Petya should execute m queries of the following form:

switch l r — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from l to r, inclusive: each digit 4 is replaced with 7 and each digit 7 is replaced with 4 (1 ≤ l ≤ r ≤ n);
count — find and print on the screen the length of the longest non-decreasing subsequence of string s.

Subsequence of a string s is a string that can be obtained from s by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.

Help Petya process the requests.

Input

The first line contains two integers n and m (1 ≤ n ≤ 106, 1 ≤ m ≤ 3·105) — the length of the string s and the number of queries correspondingly. The second line contains n lucky digits without spaces — Petya's initial string. Next m lines contain queries in the form described in the statement.

Output

For each query count print an answer on a single line.

Examples

input

Copy

2 3
47
count
switch 1 2
count

output

Copy

2
1

input

Copy

3 5
747
count
switch 1 1
count
switch 1 3
count

output

Copy

2
3
2

Note

In the first sample the chronology of string s after some operations are fulfilled is as follows (the sought maximum subsequence is marked with bold):

In the second sample:

题意：给出一个字符串，两种操作，第一种反正l~r 第二种查询字符串长度(4在前7在后这种)

思路：维护一下翻转和没翻转的 4 7 47的长度，最后结果肯定是由 4L+7R 47L+7R 4L+47R 这三种

代码：

#include<bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn = 1e6+5;
char s[maxn];
int len4[maxn<<2][2],len7[maxn<<2][2],len[maxn<<2][2];
bool fg[maxn<<2];
void push_up(int rt)
{
    int l=rt<<1,r=rt<<1|1;
    for(int i=0; i<2; i++)
    {
        len4[rt][i]=len4[l][i]+len4[r][i];
        len7[rt][i]=len7[l][i]+len7[r][i];
        len[rt][i]=max(len4[l][i]+len7[r][i],max(len[l][i]+len7[r][i],len4[l][i]+len[r][i]));
    }
}
void Reverse(int rt)
{
    swap(len4[rt][0],len4[rt][1]);
    swap(len7[rt][0],len7[rt][1]);
    swap(len[rt][0],len[rt][1]);
    fg[rt]=!fg[rt];
}
void push_down(int rt)
{
    if(!fg[rt]) return;
    Reverse(rt<<1);
    Reverse(rt<<1|1);
    fg[rt]=!fg[rt];
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        s[l]=='4'?len4[rt][0]++:len7[rt][0]++;
        len4[rt][1]=len7[rt][0];
        len7[rt][1]=len4[rt][0];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void updata(int l,int r,int rt,int L,int R)
{
       if(L<=l&&r<=R)
       {
           Reverse(rt);
           return;
       }
       push_down(rt);
       int m=l+r>>1;
       if(L<=m)
        updata(lson,L,R);
       if(R>m)
        updata(rson,L,R);
        push_up(rt);
}
int query(int rt)
{
    return max(len4[rt][0],max(len7[rt][0],len[rt][0]));
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    scanf("%s",s+1);
    build(1,n,1);
   // cout<<"?"<<endl;
    while(m--)
    {
        char op[10];
        scanf("%s",op);
        if(op[0]=='c')
        {
            printf("%d
",query(1));
        }
        else
        {
            int l,r;
            scanf("%d %d",&l,&r);
            updata(1,n,1,l,r);
        }
    }
}

View Code

PS:摸鱼怪的博客分享，欢迎感谢各路大牛的指点~