Чергова задача ICPC про рядки

Вхідні дані

Перший рядок вхідних даних містить $2$ цілих числа $n, q$ ( $1 \leq n \leq 5 \times 1 0^{4}, 1 \leq q \leq 1 0^{5}$ 1 \leq n \leq 5\times 10^4, 1 \leq q \leq 10^5).

Другий рядок вхідних даних містить рядок $s$ довжини $n$ , що складається з малих латинських літер.

Далі йдуть $q$ рядків, які мають один із наступних форматів:

Якщо це запит першого типу, він містить ціле число $k_{i}$ k_i ( $1 \leq k_{i} \leq n$ 1 \leq k_i \leq n) та символ нижнього регістру $c_{i}$ c_i. Цей запит означає заміну символу $s_{k_{i}}$ s_{k_i} на $c_{i}$ c_i
Якщо це запит другого типу, він містить число $0$ і непорожній рядок $p$ із символів нижнього регістру. Для цього типу запиту вам потрібно знайти скільки разів $p$ зустрічається як підрядок $s$ .

Гарантується, що існує принаймні один запит типу $2$ .

Гарантується, що сума довжин рядків $p$ за всіма запитами типу $2$ не перевищує $5 \cdot 1 0^{4}$ 5\cdot 10^4.

Вихідні дані

Для кожної операції типу $2$ виведіть кількість входжень рядку запиту як підрядка $s$ .

Приклади

Приклад 1

Loading

Приклад 2

Loading