eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Jewel Magic

Jewel Magic

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB

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

Вхідні дані

There will be several test cases. The first line of each test case contains an integer n and m (1n, m200,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.

Вихідні дані

For each type-4 operation, output the answer.

Приклад

Вхідні дані #1
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
Вихідні дані #1
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