402658: GYM100834 G Polycarp and Palindromes

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Polycarp and Palindromestime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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).

ExamplesInput
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

加入题单

算法标签: