Ersel has a string of length \(\mathbf{N}\) is given and there are 2 different operations he has defined on this operation.

• toggle \(l\ r\): Inverts all characters from the \(l\)\(^{\mathbf{th}}\) position to the \(r\)\(^{\mathbf{th}}\). (Including \(l\) and \(r\), \(1\)s become \(0\) and \(0\)s come \(1\))
• count: Prints the length of the longest non-decreasing subsequence of string.

Ersel spends too much time executing those operations. Can you help Ersel and write a program that executes those operations quickly?

Input

The first line contains two integers \(\mathbf{N}\) and \(\mathbf{M}\). These integers indicate the length of the string and the number of queries, respectively.

The second line of input contains a string of length \(\mathbf{N}\) which consists of only "0" and "1".

Next \(\mathbf{M}\) lines contain the queries t and c.

• \(1 \leq l \leq r \leq \mathbf{N} \leq 10^{6} \)
• \(1 \leq \mathbf{M} \leq 10^{6} \)

Output

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

Examples

Input 1:

2 3
01
c
t 1 2
c

Output 1:

2
1

Input 2:

5 5
10101
c
t 2 4
c
t 1 3
c

Output 2:

3
4
5

Explanation

• 10101  

The first query is c. The longest subsequence is the substring 001 which consists of 2., 4. and 5. characters of the strings and its length is 3.

The second query is t, and 2 and 4 are given as parameters. After numbers from 2. position to 4. position is inverted, the string becomes 11011.

• 11011  

The third query is c. The longest subsequence is the substring 1111 which consists of 1., 2., 4. and 5. characters of the strings and its length is 4.

The fourth query is t, and 1 and 3 are given as parameters. After numbers from 1. position to 3. position is inverted, the string becomes 00111.

• 00111

The fifth and the last query is c. The longest subsequence is the substring 00111 which consists of all characters of the strings and its length is 5.