Mirror IIOT 2023-2024 Round I | Periodic Words

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.