Веселощі з рядками

Обмеження: 3 сек., 256 МіБ

Марічка дала Зеникові доволі складне завдання, і в нього нема жодної ідеї, як його розв’язати (Ну, він не поїхав на Ужгородську літню школу, тож, мабуть, у цьому справа.)

Початково є рядок \(s\) з \(n\) символів. Зеник має обробити \(m\) запитів на цьому рядку. Є три типи запитів:

1. i \(p\) \(c\) — вставити символ \(c\) відразу після \(p\)-го символу. Якщо \(p\) дорівнює 0, вставити \(c\) на початок рядка.

2. d \(p\) — видалити \(p\)-ий символ з рядка.

3. q \(a\) \(b\) — знайти та вивести довжину найбільшого спільного префікса рядків \(s[a..|s|]\) і \(s[b..|s|]\).

Вхідні дані

У першому рядку задано два цілі числа \(n\) і \(m\).

Другий рядок містить рядок завдовжки \(n\).

Наступні \(m\) рядків містять запити, по одному в рядку, в описаному вище форматі.

Гарантується, що рядок завжди складається з малих англійських букв, і всі індекси в запитах валідні.

Вихідні дані

Виведіть відповідь для кожного запиту третього типу.

Обмеження

\(1 \le n, m \le 5 \cdot 10^4\).

Приклади