시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 6 5 62.500%

문제

A binary array is an array which each element can be either 0 or 1. Aleka has a binary array B or length N. The elements of B are indexed from 1 to N.

Aleka will play with her array. She will run Q queries one after another. Each query can be one of the following type :

  • FLIP L R: Flip all bits of B from index L to R, inclusive. Flipping bit is changing the value of a bit from 0 to 1, or from 1 to 0.
  • COMBO L R: Let B' be the subarray of B only containing bits which indexed between L to R, inclusive. Find the length of the longest contiguous subarray of B' such that all elements in that subarray have the same value.

All the queries should be executed as in the input order, and for every COMBO-type query, output the answer for that query.

입력

The first line contains two integers: N Q (1 ≤ N, Q ≤ 100,000) in a line denoting the length of the array and the number of queries. The second line contains a string of N characters (of '0' or '1') representing the binary array B. The i-th character in the string corresponds to the i-th element of the binary array B ('0' represents 0, while '1' represents 1). The next Q lines each contains three integers T L R (1 ≤ T ≤ 2; 1 ≤ LRN) denoting the query. If T = 1, then this query is a FLIP query, otherwise this query is a COMBO query.

출력

For each COMBO-type query, print the answer of the query in the same order of the queries running order.

예제 입력 1

5 5
11000
1 2 3
2 1 5
1 4 5
2 1 5
2 1 4

예제 출력 1

2
3
2

After the first query, B becomes 10100.

For the second query, B' = 10100. The longest subarray satisfying the COMBO constraint is 00.

After the third query, B becomes 10111.

For the fourth query, B' = 10111. The longest subarray satisfying the COMBO constraint is 111.

For the fifth query, B' = 1011. The longest subarray satisfying the COMBO constraint is 11.