У Поликарпа есть строка 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
