Jewel Magic

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):

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 5 MB.

Output

For each type-4 operation, output the answer.

Examples

Note

String after operation 1 0 1: 1000100001100 String after operation 3 7 10: 1000101000100 String after operation 2 9: 100010100100