Statement

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 + … + t for some string t ≠ s, where + is the string concatenation operation. You are given a string A=\overlinea_0a_1… 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… r_i] = \overlinea_l_ia_l_i+1… a_r_i is a periodic string.