F. Подстроки в строке
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка s, обработайте q запросов, каждый из которых имеет один из следующий типов:

  • 1 i c — Изменить i-й символ в строке на c.
  • 2 l r y — Рассмотрим подстроку строки s, начинающуюся с символа с номером l и заканчивающуюся на символ с номером r. Выведите количество раз, которые y входит в неё как подстрока.
Входные данные

В первой строке задана строка s (1 ≤ |s| ≤ 105), состоящая из строчных букв английского алфавита.

Во второй строке задано число q (1 ≤ q ≤ 105) — количество запросов.

Следующие q строк описывают запросы и могт в зависимости от типа запроса имеють следующие форматы:

  • 1 i c (1 ≤ i ≤ |s|)
  • 2 l r y (1 ≤ l ≤ r ≤ |s|)

c — это строчная буква английского алфавита, y — непустая строка, состоящая из строчных букв английского алфавита.

Сумма |y| по всем запросам второго типа не превосходит 105.

Гарантируется, что в тесте есть хотя бы один запрос второго типа.

Строки индексируются, начиная с 1.

|s| обозначает длину строки s.

Выходные данные

Для каждого запроса типа 2 выведите ответ в отдельной строке.

Примеры
Входные данные
ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba
Выходные данные
3
1
Входные данные
abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa
Выходные данные
2
2
1
Примечание

В первом тестовом примере изначально строка aba встречается 3 раза как подстрока на подотрезке [1, 7].

После запроса первого типа строка становится равной ababcbaba и строка aba встречается только один раз как подстрока на отрезке [1, 7].