One-Reversal Palindrome Substring Queries

In this problem, you are given a string s consisting of lowercase English letters and a number of queries. Each query provides two indices l and r (1-indexed), representing a substring s[l...r]. Your task is to determine whether it is possible to make the substring a palindrome by performing at most one reversal of a contiguous segment within the substring.

A string is a palindrome if it reads the same backwards as forwards. Let (k) be the number of characters in the substring that appear an odd number of times. It turns out that the substring can be transformed into a palindrome with at most one reversal if and only if (k \leq 2).

For example, consider the string "ababa". For the query (1, 3), the substring is "aba" which is already a palindrome, and for (2, 4), the substring is "bab" which is also a palindrome. However, if the substring does not satisfy this condition, it is impossible to fix it with just one reversal.

inputFormat

The first line contains an integer (n) ( (1 \leq n \leq 10^5)), the length of the string. The second line contains the string (s) consisting of lowercase English letters. The third line contains an integer (q) ( (1 \leq q \leq 10^5)) representing the number of queries. Each of the following (q) lines contains two integers (l) and (r) (1-indexed) representing a query.

outputFormat

For each query, output a single line with the word "YES" if the corresponding substring can be transformed into a palindrome with at most one reversal, or "NO" otherwise.## sample

5
ababa
3
1 3
2 4
1 5

YES
YES
YES