C. Powerful String
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Define the power of a string $$$t$$$ of length $$$m$$$ as follows:

$$$$$$\prod_{i = 1}^{m} i^{f_t(t_i)}$$$$$$

Where:

— $$$t_i$$$ is the character at position $$$i$$$ of the string $$$t$$$.

— $$$f_t(c)$$$ is the number of occurrences of the character $$$c$$$ in the string $$$t$$$.

For example, if $$$t = $$$ "abca", then $$$f($$$'a'$$$) = 2$$$, $$$f($$$'b'$$$) = 1$$$, and $$$f($$$'c'$$$) = 1$$$, and the power of $$$t$$$ is equal to $$$1^2 \times 2^1 \times 3^1 \times 4^2 = 96$$$.

Given a string $$$s$$$ of length $$$n$$$, and $$$q$$$ queries of the following form:

— "$$$l, r$$$": determine whether it is possible to swap two characters in $$$t[l \dots r]$$$ such that the power of $$$t[l \dots r]$$$ increases.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line of the input contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

The third line of the input contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the following $$$q$$$ lines consists of two space-separated integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le n$$$).

Output

Output $$$q$$$ lines, the $$$i$$$-th of which contains the answer of the $$$i$$$-th query as follows:

Print "YES" (without quotes) if it is possible to increase the power in the $$$i$$$-th query, and print "NO"(without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

Examples
Input
5
ababa
2
1 2
1 3
Output
NO
YES
Input
2
aa
1
1 2
Output
NO