Jewel Magic

Я маг. У мене є рядок із смарагдів і перлів. Я можу додавати нові коштовності в рядок або видаляти старі. Я навіть можу перевертати частини рядка. У будь-який момент, якщо ви вкажете на дві коштовності і запитаєте мене, яка довжина найдовшого спільного префікса (LCP) рядків коштовностей, починаючи з цих двох коштовностей, я можу миттєво відповісти на ваше запитання. Чи можете ви зробити це краще за мене?

Формально, вам буде дано рядок з 0 та 1. Вам потрібно виконувати чотири види операцій (у наступних описах L позначає поточну довжину рядка, а позиції коштовностей нумеруються від 1 до L зліва направо):

Вхідні дані

Буде кілька тестових випадків. Перша строка кожного тестового випадку містить цілі числа n та m (1 ≤ n, m ≤ 200,000), де n — це кількість перлів на початку, m — це кількість операцій. Наступний рядок містить рядок 01 довжиною n. Кожен з наступних m рядків містить операцію. Введення завершується кінцем файлу (EOF). Розмір вхідного файлу не перевищує 5 МБ.

Вихідні дані

Для кожної операції типу-4 виведіть відповідь.

Приклади

Примітка

Рядок після операції 1 0 1: 1000100001100 Рядок після операції 3 7 10: 1000101000100 Рядок після операції 2 9: 100010100100