Question
Can We Rearrange to form a Palindrome?
You are given a lowercase string
Each query consists of two integers
For each query, determine whether it is possible to rearrange the characters of this substring to form a palindrome.
s and q queries.Each query consists of two integers
L and R, representing the substring s[L...R] (inclusive, 0-indexed).For each query, determine whether it is possible to rearrange the characters of this substring to form a palindrome.
Input
The first line contains a single string s consisting of lowercase English letters.
The second line contains a single integer KaTeX can only parse string typed expression — the number of queries.
The following KaTeX can only parse string typed expression lines each contain two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the starting and ending indices of the substring (inclusive).
The second line contains a single integer KaTeX can only parse string typed expression — the number of queries.
The following KaTeX can only parse string typed expression lines each contain two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the starting and ending indices of the substring (inclusive).
Output
For each query, print "YES" if the substring can be rearranged into a palindrome, otherwise print "NO".
Example
Input
aabbcc
3
0 5
0 3
1 4
Output
YES
YES
NO
Explanation
The substring "aabbcc" can be rearranged to "abccba".
The substring "aabb" can be rearranged to "abba".
The substring "abbc" cannot be rearranged to be a palindrome.
aabbcc
3
0 5
0 3
1 4
Output
YES
YES
NO
Explanation
The substring "aabbcc" can be rearranged to "abccba".
The substring "aabb" can be rearranged to "abba".
The substring "abbc" cannot be rearranged to be a palindrome.