Lucky Queries

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A string contains only 4 and 7. A range can be switched, and count asks for the longest non-decreasing subsequence length.

Input

The first line contains $n,m$ and the second line contains $s$. Each operation is:

• switch l r: swap 4 and 7 on $[l,r]$.
• count: print the length of the longest non-decreasing subsequence of the entire string.

Output

Print one line for every count command.

Subtasks

• 20 points: $n,m\le50$.
• 30 points: $n,m\le5000$.
• 50 points: $n\le10^6$, $m\le3\cdot10^5$.

Examples

Input

2 3
47
count
switch 1 2
count

Output

2
1

Explanation

Initially 47 is already non-decreasing, so the answer is 2. After switching the whole range, the string is 74; a longest non-decreasing subsequence then has length 1.