G. Поликарп и палиндромы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть строка S, стоящая из N строчных латинских символов. Поликарпа интересует, являются ли определенные подстроки строки S палиндромами. Палиндромом называется строка, которая одинаково читается справа налево и слева направо. Но этого Поликарпу мало: он еще может менять символы в строке. Поликарпу интересно, можно ли быстро определять, является ли палиндромом заданная подстрока строки S, если в S можно заменять символы. Всего Поликарп последовательно проводит K операций.

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

В первой строке находится строка S. Её длина N, 1 ≤ N ≤ 100000. S состоит только из строчных латинских символов.

Во второй строке находится единственное целое число K, 1 ≤ K ≤ 100000 — количество операций.

В следующих K строках находятся описания операций, по одной в каждой строке. Каждая строка начинается с целого числа ti, которое может принимать значения 1 и 2. Если ti равно 1, то это дальше идут два целых числа li и ri, 1 ≤ li ≤ ri ≤ N. Это означает - необходимо определить, является ли подстрока slisli + 1... sri палиндромом. Если ti равно 2, то дальше идет целое число pi и строчный латинский символ ci. Это означает — заменить в строке S символ на позиции pi на ci

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

Для каждой операции определения палиндрома необходимо вывести на отдельных строках "YES", если подстрока является палиндромом, или "NO", если не является. Кавычки выводить не нужно.

Примеры
Входные данные
ababaccc
8
1 1 5
1 1 8
1 2 4
2 5 b
2 6 a
2 7 b
2 8 a
1 1 8
Выходные данные
YES
NO
YES
YES
Входные данные
aaaa
10
1 1 1
1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 3
1 3 4
1 4 4
Выходные данные
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES