ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1989. Subpalindromes

Time limit: 0.5 second
Memory limit: 64 MB
You have a string and queries of two types:
  1. replace i’th character of the string by character a;
  2. check if substring sj...sk is a palindrome.

Input

The first line contains a string consisting of n small English letters. The second line contains an integer m that is the number of queries (5 ≤ n, m ≤ 105). The next m lines contain the queries.
Each query has either form “change i a”, or “palindrome? j k”, where i, j, k are integers (1 ≤ in; 1 ≤ jkn), and character a is a small English letter.

Output

To all second type queries, you should output “Yes” on a single line if substring sj...sk is a palindrome and “No” otherwise.

Sample

inputoutput
abcda
5
palindrome? 1 5
palindrome? 1 1
change 4 b
palindrome? 1 5
palindrome? 2 4
No
Yes
Yes
Yes
Problem Author: Mikhail Rubinchik
Problem Source: Open Ural FU Championship 2013