# Mirror IIOT 2023-2024 Round I | Periodic Words

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 128MB Input: Output:

A string $s$ is said to be periodic if there exists a string $t$ such that $s$ can be obtained by concatenating multiple (at least $2$) copies of $t$.
In other words, $s$ is periodic if $s = t + t + \ldots + t$ for some string $t \neq s$, where $+$ is the string concatenation operation.

You are given a string $A=\overline{a_0a_1\ldots a_{N-1}}$ of length $N$ and $Q$ queries of the form $l_i, r_i$.
For each query, determine whether the substring $A[l_i\ldots r_i] = \overline{a_{l_i}a_{l_i+1}\ldots a_{r_i}}$ is a periodic string.

## Input data

The first line contains an integer $N$. The second line contains a string $S$ of length $N$.
The third line contains an integer $Q$. The next $Q$ lines contain the values $l_i, r_i$, describing the queries.

## Output data

For each query, print YES if the required substring is a periodic string or NO if it is not.

## Constraints and clarifications

• $1 \le N, Q \le 100 \ 000$.
• $0 \le l_i \le r_i \le N - 1$.
• The string consist of lowercase letters of the English alphabet.
• For tests worth $10$ points, $N, Q \leq 100$.
• For tests worth $20$ more points, $N, Q \leq 1000$.
• For tests worth $20$ more points, $N, Q \leq 10\,000$.

## Example

stdin

14
abacbaabcabccc
5
0 13
0 3
6 11
11 13
6 10


stdout

NO
NO
YES
YES
NO


### Explanation

In the first query, it is asked if the whole string is periodic, so the answer is NO.

In the third query, the substring $abcabc$ is periodic, as it can be obtained by concatenating $abc$ twice.