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