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 ss is said to be periodic if there exists a string tt such that ss can be obtained by concatenating multiple (at least 22) copies of tt.
In other words, ss is periodic if s=t+t++ts = t + t + \ldots + t for some string tst \neq s, where ++ is the string concatenation operation.

You are given a string A=a0a1aN1A=\overline{a_0a_1\ldots a_{N-1}} of length NN and QQ queries of the form li,ril_i, r_i.
For each query, determine whether the substring A[liri]=aliali+1ariA[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 NN. The second line contains a string SS of length NN.
The third line contains an integer QQ. The next QQ lines contain the values li,ril_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

  • 1N,Q100 0001 \le N, Q \le 100 \ 000.
  • 0liriN10 \le l_i \le r_i \le N - 1.
  • The string consist of lowercase letters of the English alphabet.
  • For tests worth 1010 points, N,Q100N, Q \leq 100.
  • For tests worth 2020 more points, N,Q1000N, Q \leq 1000.
  • For tests worth 2020 more points, N,Q10000N, 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 abcabcabcabc is periodic, as it can be obtained by concatenating abcabc twice.

Log in or sign up to be able to send submissions!