После того, как Никита не решил на IOI задачу с запросами на отрезке, он захотел порадовать участников сборов в Петрозаводске другой задачей с запросами на отрезке.

Вам дана строка s и целое число k. Далее даны запросы.

Запросы бывают двух видов:

Символы в строке нумеруются с единицы.

В первой строке дана строка s из латинских букв, после которой через пробел расположено целое число k (1 ≤ k ≤ 50). Длина строки не превосходит 10⁵. Во второй строке дано целое число m (1 ≤ m ≤ 10⁵) — количество запросов. В следующих m строках даны запросы. Каждая строка запроса начинается с типа (1 или 2), далее идут числа l, r (1 ≤ l ≤ r ≤ |s|). Далее для запросов первого типа следует символ c — строчная латинская буква.

На каждый запрос второго типа выведите целое число в отдельной строке.