Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Queries

By robin_aust · Limits 3s, 512 MB

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

InputOutput
3 5
101
print
toggle 1 1
print
toggle 1 3
print
2
3
2

    Discussion

    Statistics


    55% Solution Ratio

    moiddaEarliest, 1M ago

    YouKnowWhoFastest, 0.1s

    curly_bracesLightest, 2.4 MB

    NirjhorShortest, 1604B

    Submit

    Login to submit

    Related Contests