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): 2 p Remove the jewel at position p (1 ≤ p ≤ 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). Output For each type-4 operation, output the answer. Explanation: String after operation 1 0 1: 1000100001100 String after operation 3 7 10: 1000101000100 String after operation 2 9: 100010100100 Sample Input 12 9 000100001100 101 426 3 7 10 417 29 4 3 11 419 417 423 1pc 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. 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).
2/2 Sample Output 3 6 2 0 3 2