This task is very simple. You are given a binary string (i.e. a string consisting of digits '0' and '1') of length n. The digits are numbered from the left to the right starting with 1. Now you have to execute m queries of two types on this string of the following form:
• toggle l r: “toggle” digits (i.e. replace them with their opposite) at all positions with indexes from l to r (1≤l≤r≤n), inclusive : each digit 0 is replaced with 1 and each digit 1 is replaced with 0.
• print : find and print the length of the longest non-decreasing subsequence of string s.
Subsequence of 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.
Input
The first line contains two integers n and m (1≤n≤1000000, 1≤m≤300000) — the length of the string s and number of queries correspondingly. The second line contains the binary string s. Next m lines contain queries in the form described in the statement.
Output
For each query print output an answer on a single line.
Sample
| Input | Output |
|---|---|
3 5 101 print toggle 1 1 print toggle 1 3 print | 2 3 2 |
