C. Эволюция ДНК
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как всем известно, любая ДНК состоит из нуклеотидов. Нуклеотиды могут быть четырех типов: «A», «T», «G», «C». ДНК в свою очередь является последовательностью нуклеотидов. Ученые получили возможность проследить за эволюцией очень редкого вида, ДНК которого описывается строкой s.

Эволюция вида представляет собой последовательность изменений в ДНК. Любое изменение в ДНК можно представить как изменение некоторого нуклеотида, например, в ДНК «AAGC» может произойти такое изменение: второй нуклеотид изменится на нуклеотид «T», в результате чего ДНК станет равной «ATGC».

Кроме того, ученым известно, что некоторые участки ДНК могли быть атакованы неизвестными инфекциями. Инфекцию также можно представить в виде последовательности нуклеотидов. Ученым интересно, были ли вызваны инфекциями какие-то изменения в ДНК. Поэтому иногда ученые хотят оценить степень воздействия интересующей их инфекции на участок ДНК по следующим правилам:

  • Пусть инфекция описывается строкой e и ученых интересует участок ДНК с позиции l по позицию r включительно.
  • Префикс строки eee... (т.е. строки, являющейся бесконечным повторением строки e) прикладывается к строке s с позиции l до позиции r включительно.
  • Значением степени воздействия инфекции на ДНК является количество позиций, в которых символы строки s совпали с приложенной строкой.

Помимо основной работы разработчиком, Иннокентий интересуется биоинформатикой, поэтому ученые обратились именно к нему за помощью. Однако, Иннокентий занят проведением VK Cup, поэтому он переложил эту задачу на участников. Помогите ученым!

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

В первой строке находится строка s (1 ≤ |s| ≤ 105), описывающая изначальную ДНК. Она состоит только из заглавных английских букв «A», «T», «G» и «C».

В следующей строке находится целое число q (1 ≤ q ≤ 105) — число событий.

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

  • 1 x c, где x — целое число (1 ≤ x ≤ |s|), а c — символ «A», «T», «G», «C», это означает, что в ДНК произошло изменение, а именно, нуклеотид на позиции x изменился на нуклеотид c.
  • 2 l r e, где l, r — целые числа (1 ≤ l ≤ r ≤ |s|), а e — строка из символов «A», «T», «G» и «C» (1 ≤ |e| ≤ 10), это означает, что ученых интересует степень воздействия инфекции e на участок ДНК с позиции l по r включительно.
Выходные данные

Для каждого запроса ученых (запроса второго типа) выведите в новой строке одно число — искомую степень воздействия инфекции на участок ДНК.

Примеры
Входные данные
ATGCATGC
4
2 1 8 ATGC
2 2 6 TTT
1 4 T
2 2 6 TA
Выходные данные
8
2
4
Входные данные
GAGTTGTTAA
6
2 3 4 TATGGTG
1 1 T
1 6 G
2 5 9 AGTAATA
1 10 G
2 2 6 TTGT
Выходные данные
0
3
1
Примечание

Рассмотрим первый пример. В первом событии второго типа все символы совпадают, поэтому ответ 8. Во втором запросе мы сравниваем строку «TTTTT...» и подстроку «TGCAT». Здесь два совпадения. В третьем запросе, после изменения ДНК, мы сравниваем строку «TATAT...» с подстрокой «TGTAT». Здесь 4 совпадения.