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).
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.
For each type-4 operation, output the answer.
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
3 6 2 0 3 2
String after operation 1 0 1: 1000100001100
String after operation 3 7 10: 1000101000100
String after operation 2 9: 100010100100