Веселощі з рядками
Обмеження: 3 сек., 256 МіБ
Марічка дала Зеникові доволі складне завдання, і в нього нема жодної ідеї, як його розв’язати (Ну, він не поїхав на Ужгородську літню школу, тож, мабуть, у цьому справа.)
Початково є рядок \(s\) з \(n\) символів. Зеник має обробити \(m\) запитів на цьому рядку. Є три типи запитів:
i
\(p\) \(c\) — вставити символ \(c\) відразу після \(p\)-го символу. Якщо \(p\) дорівнює 0, вставити \(c\) на початок рядка.d
\(p\) — видалити \(p\)-ий символ з рядка.q
\(a\) \(b\) — знайти та вивести довжину найбільшого спільного префікса рядків \(s[a..|s|]\) і \(s[b..|s|]\).
Вхідні дані
У першому рядку задано два цілі числа \(n\) і \(m\).
Другий рядок містить рядок завдовжки \(n\).
Наступні \(m\) рядків містять запити, по одному в рядку, в описаному вище форматі.
Гарантується, що рядок завжди складається з малих англійських букв, і всі індекси в запитах валідні.
Вихідні дані
Виведіть відповідь для кожного запиту третього типу.
Обмеження
\(1 \le n, m \le 5 \cdot 10^4\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 6 abacaba q 2 6 i 1 c i 5 b q 1 4 d 2 q 4 7 | 2 4 0 |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|