402658: GYM100834 G Polycarp and Palindromes

Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identically right to left and left to right. But it is not enough for Polycarp: he can change the signs in the string. Polycarp is eager to know if it is possible to know and define very quickly if the substring of the string S is a palindrome if the letters in S can be substituted. Polycarp conducts K operations one after another.

There is string S in the first line. Its length is N, 1 ≤ N ≤ 100000. S consists of only small Latin letters.

The second line contains the only integer K, 1 ≤ K ≤ 100000 — the number of operations.

Next K lines contain the descriptions of operations, one in each line. Each line starts with the integer t_i, which can take the values 1 and 2. If t_i equals 1, two integers l_i and r_i, 1 ≤ l_i ≤ r_i ≤ N follow it. It means — it is necessary to define if the substring s_lis_li + 1... s_ri is a palindrome. If t_i equals 2, it is followed by the integer p_i and a small Latin letter c_i. It means — to substitute in the string S sign in position p_i to c_i

Output "YES" in separate lines for each operation of the palindrome definition if the substring is a palindrome, or "NO", if it isn’t (without quotations).

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