Problem J

I am a magician. I have a string of emeralds and pearls. I may insert new jewels in the string, or remove old ones. I may even reverse a consecutive part of the string. At anytime, if you point to two jewels and ask me, what is the length of the longest common prefix (LCP) of jewel strings starting from these two jewels, I can answer your question instantly. Can you do better than me?

Formally, you'll be given a string of 0 and 1. You're to deal with four kinds of operations (in the following descriptions, L denotes the current length of the string, and jewel positions are number 1 to L numbered from left to right):

1 p c

Insert a jewel c after position p (0<=p<=L. p=0 means insert before the whole string). c=0 means emerald, c=1 represents pearl.

2 p

Remove the jewel at position p (1<=p<=L).

3 p1 p2

Reverse the part starting from position p1, ending at position p2 (1<=p1 < p2<=L)

4 p1 p2

Output the LCP length of jewel strings starting from p1 and p2 (1<=p1 < p2<=L).

Input

There will be several test cases. The first line of each test case contains an integer n and m (1<=n,m<=200,000), where n is the number of pearls initially, m is the number of operations. The next line contains a 01 string of length n. Each of the next m lines contains an operation. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each type-4 operation, output the answer.

Sample Input

12 9
000100001100
1 0 1
4 2 6
3 7 10
4 1 7
2 9
4 3 11
4 1 9
4 1 7
4 2 3

Output for the Sample Input

3
6
2
0
3
2

Explanation

String after operation 1 0 1: 1000100001100

String after operation 3 7 10: 1000101000100

String after operation 2 9: 100010100100