problem-1-46

Karan and Akshay love challenging each other with awesome algorithmic questions. Today, Karan decided to give Akshay a relatively easy question. Karan has string s of length N consisting entirely of lowercase latin characters and he loves double palindromes (defined below). So he asks Akshay Q questions about the string of the type -

l r - consider the substring s[l...r] and report if the characters in this substring can be rearranged to form a double palindrome.

A palindrome is a string that read same forwards and backwards.

Let's define a double palindrome as a string that is concatenation of two palindrome, "AB" is a double palindrome if "A" and "B" are palindrome.

Eg. "abbacddc" is a double palindrome because "abba" and "cddc" are both palindromes.

But, Akshay is a very lazy guy. He asks you to solve the task at hand!(Height of laziness!)

If it is possible then print "YES", without quotes else print "NO".

Input format
The first line of input contains one integer N denoting the size of the string.

The second line of input contains the string s itself. It is guaranteed that the string consists only of lowercase latin characters.

The third line contains one integer Q denoting the total number of queries.

Next Q lines each contain two integers l r denoting the queries.

Output format
For each query output a single line with the string "YES" if the characters in the substring represented by the corresponding query can be rearranged to form double palindrome else output the string "NO".

Constraints

 1 ≤ N ≤ 10^5 
 1 ≤ Q ≤ 10^5 
 1 ≤ l ≤ r ≤ N 

Sub-tasks
For 25% points :  1 ≤ N, Q ≤ 10^3 

For 75% points : original constraints

Note : Output is case sensitive

Note : Palindrome can't be empty

SAMPLE INPUT
8
abcdabcd
2
1 8
3 5

SAMPLE OUTPUT
YES
NO

Explanation

For query 1, the substring can be rearranged to make the string "abbacddc" which is a double palindrome because "abba" and "cddc" are both palindromes.

Source: hackerearth | Difficulty: EASY


Solutions:
from string import ascii_lowercase
A = ord("a")
ad = {}
for c in ascii_lowercase:
	i = ord(c) - A
	ad[c] = 2 ** i
n = int(input())
t = (n + 1) * [0] 
s = input().strip()
for i in range(n):
	t[i+1] = t[i] ^ ad[s[i]]
for _ in range(int(input())):
	l, r = list(map(int, input().split()))
	if r - l < 1:
		print("NO")
		continue
	x = bin(t[l-1] ^ t[r]).count("1")
	print("NO" if x > 2 else "YES")