G. Polycarp and Palindromes
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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 ti, which can take the values 1 and 2. If ti equals 1, two integers li and ri, 1 ≤ li ≤ ri ≤ N follow it. It means — it is necessary to define if the substring slisli + 1... sri is a palindrome. If ti equals 2, it is followed by the integer pi and a small Latin letter ci. It means — to substitute in the string S sign in position pi to ci

Output

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).

Examples
Input
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
Output
YES
NO
YES
YES
Input
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
Output
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES