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
```
