QUERYIT - SLIS

Rachit, Sandeep, Yogesh, Vikram and Shubham are very good friends. They participated in a contest MNNIT INSOMNIA as a team but there was a problem which was not solved by any of the teams. So they were desperate to solve that problem. After the contest they asked you for your help to solve the problem. Help them to solve the problem. The problem is as follows:

There is an array of length n consisting of only 0 and 1 as elements. You have to answer q queries. There are two type of queries:

Type 0: There is l and r. You have to change each 0 to 1 and each 1 to 0 from l to r (both inclusive).

Type 1: print the length of longest non decreasing subsequence of the array.

Note: Indexing is 1 based.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Input

First line consists of two integers n and q where n is length of array and q is number of queries.

Second line consists of array of length n without spaces.

After that there are q lines containing type of query. And for type 0 query it has two integers l and r.

1<=n,q<=10^5, 1<=l<=r<=n

Output

Print a single line for each query of type 1 containg length of longest non decreasing subsequence.

Example

Input:
5 5
10111
1
0 3 5
1
0 2 3
1

Output:
4
4
3

Added by:Sandeep Kumar Singh
Date:2017-06-01
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-12-05 14:52:48
AC in one go! for those who wants to use segment tree, dont forget to count the number of '01' and also '10' for the update.
2021-04-07 17:40:03
@ebraheemahmed, for test : 0011 ans will be 4, but finidng count using seg tree will give 2.
2019-12-22 21:44:43 DK...
I'm think the same code works fine, if the printf querie type was in a range.
2018-08-19 14:00:40
WA at test case 10 :( , i'm using segment tree , is there any tricky case ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.