Mật khẩu tuần hoàn

Trên không gian mạng, mỗi người dùng đều được đại diện bởi một tài khoản định danh kèm theo một phương thức bảo vệ. Mật khẩu là một công cụ bảo mật phổ biến, được tạo thành bởi một chuỗi các ký tự đặc trưng riêng của chủ nhân tài khoản.

Ngày nay, mật khẩu tỏ ra kém an toàn hơn các công cụ bảo mật mới khác như nhận diện khuôn mặt (Face ID), dấu vân tay (fingerprint) hay xác thực hai lớp (2FA), bởi mật khẩu có thể dễ dàng bị "bẻ khoá" bởi những phương thức tấn công đơn giản như "tấn công brute-force": duyệt tự động tất cả các khả năng của xâu mật khẩu. Phương thức này đặc biệt nguy hiểm nếu mật khẩu có chứa các xâu con tuần hoàn, bởi quy luật tuần hoàn có thể khiến cho mật khẩu trở nên dễ đoán hơn.

Bạn là chủ tài khoản của một hệ thống mạng nội bộ. Để đảm bảo an toàn, bạn cần kiểm tra lại xem mật khẩu hiện tại của tài khoản có tồn tại sự tuần hoàn nào hay không. Biết rằng mật khẩu hiện tại là một xâu $S$ gồm $N$ ký tự Latin thường. Bạn hãy thực hiện $Q$ yêu cầu kiểm tra sự tuần hoàn của các xâu con $S[l_q:r_q]$ của mật khẩu trên ($1\le q\le Q$). Xâu con $S[l:r]$ gồm các ký tự từ vị trí $l$ đến vị trí $r$ của $S$ (các vị trí đánh số từ $1$).

Lưu ý: Một xâu $T$ gọi là tuần hoàn nếu tồn tại một xâu $X\ne T$ sao cho $T=X+X+\dots +X$ (ghép liền nhau từ hai bản sao của $X$ trở lên).

Ví dụ, xâu $T_1=\mathtt{\text{ababab}}$ là xâu tuần hoàn vì nó được cấu tạo bởi $3$ xâu $\mathtt{\text{ab}}$ ghép liền với nhau. Ngược lại, xâu $T_2=\mathtt{\text{abcab}}$ không phải là xâu tuần hoàn. Xâu chỉ gồm một ký tự cũng không phải là xâu tuần hoàn.

Yêu cầu: Với mỗi truy vấn, xác định xem xâu con tương ứng có phải là xâu tuần hoàn hay không.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $N$ mô tả độ dài mật khẩu.
• Dòng tiếp theo chứa xâu $S$ mô tả mật khẩu gồm $N$ ký tự Latin in thường.
• Dòng tiếp theo chứa số nguyên dương $Q$ mô tả số yêu cầu kiểm tra.
• $Q$ dòng tiếp theo, dòng thứ $q$ chứa hai số nguyên dương $l_q$ và $r_q$ ($1\le l_q\le r_q\le N$) mô tả yêu cầu kiểm tra thứ $q$ trên xâu $S[l_q:r_q]$.

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $q$ ứng với truy vấn $q$ là YES (nếu xâu con $S[l_q:r_q]$ tuần hoàn) hoặc NO (nếu xâu con $S[l_q:r_q]$ không tuần hoàn).

Ràng buộc

• $1\le N,Q\le {10}^5$.
• $1\le l_q\le r_q\le N$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N,Q\le {10}^2$.
• Subtask 2 ($20\%$ số điểm): $N,Q\le {10}^3$.
• Subtask 3 ($30\%$ số điểm): $N,Q\le {10}^4$.
• Subtask 4 ($30\%$ số điểm): $N,Q\le {10}^5$.

Ví dụ