You are given a string $S$ of length $n$ consisting of only lowercase English letters.

There are $q$ queries, each of the form $(l, r)$, you have to determine if $S[l…r]$ is a palindrome.

Input

• The first line contains a string $S$.
• The second line contains an integer $q$.
• The next $q$ lines, each line contains 2 integers $l, r$, a query.

Output

• Print $q$ lines. On each line, print YES if the string is a palindrome, otherwise print NO.

Constraints

• $1 \le |S| \le 2000$.
• $1 \le q \le 10^5$.
• $1 \le l, r \le |S|$.

Example

Input:

abcbd
2
1 3
2 4

Output:

NO
YES