Suppose you are given a string \(s\) of size \(n\) consisting of lowercase letters only. You will be given \(q\) queries. Each query can be of below two types:
- \(1\) \(l\) \(r\) \(ch:\) From \(l\) to \(r\), change characters in the string \(s\) to \(ch\), i.e., make \(s[l] = s[l + 1] = \) \(...\) \(s[r] = ch\)
- \(2\) \(l\) \(r:\) Suppose string \(t\) is the substring of string \(s\) from index \(l\) to \(r\), or, \(t = \) \(s[l ... r]\)
For each query of type \(2\) answer will be Yes, if we can rearrange the characters in the string \(t\) so that the string becomes a palindrome. Otherwise, the answer is No.
Do note that query \(1\) makes permanent changes to the string \(s\), i.e., for all queries after it, the string is modified.
For each query of type \(2\), you don't make changes to the string \(s\). Or in other words, the string remains the same after query of type \(2\).
It is recommended to use Fast I/O.
Input Format
- The first line contains a string \(s\) of size \(n\).
- The second line contains one integer \(q\) - number of queries. Then \(q\) queries follow.
- Each query will be of one of the two types as explained above.
Output Format
For each query of type \(2\), output the answer in a separate line.
Constraints
- \(1 \leq n \leq 10^{5}\)
- \(1 \leq q \leq 10^5\)
- In each query, \(1 \leq l \leq r \leq n\) will always follow.
- In each query of type \(1\), \(a \leq ch \leq z\) will always follow.
- The string \(s\) consists of lowercase letters only.
- It is guaranteed that there will be at least \(1\) query of type \(2\).
The given string is \(abcsjakj\).
- After the first query, the string becomes \(abczzzzj\).
- The second query considers the substring \(s[6..8] = zzj\). Let's say this is denoted by \(t\). In this string, characters can be rearranged such that \(t \) becomes \(zjz\), which is a palindrome. Therefore the answer to this query is \(Yes\).
- After the third query, the string becomes \(aaaaazzj\).
- After the fourth query, the string becomes \(aaffazzj\).
- The fifth query considers the substring \(s[3...6] = ffaz\). It can be shown that, this substring can't be converted into a palindrome. Therefore the answer to this query is \(No\).
- The sixth query considers the substring \(s[3...7] = ffazz\). Let's say this is denoted by \(t\). We can see that the string \(t\) is a palindrome. Therefore the answer to this query is \(Yes\).
- The seventh query considers the substring \(s[1...1] = a\). A string of size 1 is always a palindrome. Therefore the answer to this query is \(Yes\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor