Overview

This problem asks us to efficiently determine, for each query, whether a substring \(T_i\) extracted from the infinitely repeated string \(S^{\infty}\) appears as a contiguous substring of the original string \(S\).

Analysis

Basic Observations

Since \(S^{\infty}\) is a string with period \(N\), the starting position of \(T_i\) is determined by \(\text{start} = (L_i - 1) \bmod N\) (0-indexed). Let \(\text{length} = R_i - L_i + 1\) be the length of \(T_i\):

• If \(\text{length} > N\): Since the length of \(S\) is \(N\), a substring longer than \(N\) cannot appear in \(S\). The answer is No.
• If \(\text{start} + \text{length} \leq N\): \(T_i = S[\text{start} : \text{start}+\text{length}]\), which is directly a substring of \(S\). The answer is Yes.
• If \(\text{start} + \text{length} > N\) (wraparound): \(T_i\) is the concatenation of the suffix \(S[\text{start}:N]\) and the prefix \(S[0:\text{end}]\). Here, \(\text{tail} = N - \text{start}\) and \(\text{end} = \text{length} - \text{tail}\).

Analysis of the Wraparound Case

We want to check whether \(T = S[\text{start}:N] + S[0:\text{end}]\) appears somewhere in \(S\). That is, we want to determine if there exists a position \(p\) such that \(S[p:p+\text{length}]\) matches \(T\).

We consider this match in terms of the split point \(j = p + \text{tail}\). \(j\) is the boundary within \(S\) where “the match with the suffix part ends and the match with the prefix part begins.” The conditions are:

1. \(S[p:j] = S[\text{start}:N]\) (matches the last \(\text{tail}\) characters of \(S\))
2. \(S[j:j+\text{end}] = S[0:\text{end}]\) (matches the first \(\text{end}\) characters of \(S\))
3. \(j \in [\text{tail},\ N - \text{end}]\) (within valid range)

Using the Z-function

• Condition 2 can be checked using the Z-function of \(S\). Since \(Z[j]\) is “the length of the longest common prefix between \(S\) and \(S[j:]\)”, the condition is \(Z[j] \geq \text{end}\).
• Condition 1 can be checked using the reverse Z-function (the Z-function of the reversed string \(S\)). Using the Z-function \(Z_R\) of \(R = \text{reverse}(S)\), \(Z_R[N-j]\) represents “how many characters ending at position \(j\) in \(S\) match the suffix of \(S\).” The condition is \(Z_R[N-j] \geq \text{tail}\).
• Condition 3 is naturally included in conditions 1 and 2 (\(j \geq \text{tail}\) is implied by \(\min(j, Z_R[N-j]) \geq \text{tail}\), and \(j \leq N-\text{end}\) is implied by \(\min(Z[j], N-j) \geq \text{end}\)).

Reduction to a 2D Dominance Problem

For each split point \(j\) (\(1 \leq j \leq N-1\)), define: $\(b_j = \min(j,\ Z_R[N-j]), \quad a_j = \min(Z[j],\ N-j)\)$

Then the answer for query \((\text{tail}, \text{end})\) is:

Does there exist a \(j\) such that \(b_j \geq \text{tail}\) and \(a_j \geq \text{end}\)?

This is a 2D dominance problem. If we precompute the function \(f(t) = \max\{a_j \mid b_j \geq t\}\), then each query reduces to simply checking whether \(f(\text{tail}) \geq \text{end}\).

\(f\) can be computed in \(O(N)\) as follows: 1. Compute the array \(g[t] = \max\{a_j \mid b_j = t\}\) 2. Take the suffix maximum from right to left: \(f[t] = \max(g[t],\ f[t+1])\)

Algorithm

1. Compute the Z-function \(Z\) of \(S\).
2. Compute the Z-function \(Z_R\) of \(R = \text{reverse}(S)\).
3. For each \(j = 1, \ldots, N-1\), compute \(b_j = \min(j, Z_R[N-j])\) and \(a_j = \min(Z[j], N-j)\).
4. Store \(g[b_j] = \max(g[b_j], a_j)\) in the array \(g\), then build \(f\) by taking suffix maximums from right to left.
5. For each query:
   • \(\text{length} > N\) → No
   • \(\text{start} + \text{length} \leq N\) → Yes (no wrap)
   • Wraparound → Yes if \(f[\text{tail}] \geq \text{end}\), otherwise No

Complexity

• Time complexity: \(O(N + Q)\) (Z-function computation is \(O(N)\), building \(f\) is \(O(N)\), each query is \(O(1)\))
• Space complexity: \(O(N)\)

Implementation Notes

• Since \(L_i, R_i\) can be as large as \(10^{18}\), use \(\bmod N\) to compute the starting position. In Python, big integers are handled natively, so there is no concern about overflow.

• The Z-function is implemented using the standard linear algorithm. We define \(Z[0] = N\) (the entire string is a prefix of itself).

• When building the array \(f\), only those \(j\) with \(b_j \geq 1\) and \(a_j \geq 1\) are relevant (since \(\text{tail}, \text{end} \geq 1\)).

• Wraparound occurs only when \(\text{start} \geq 1\) and \(\text{end} \geq 1\). If wraparound would occur with \(\text{start} = 0\), then \(\text{length} > N\), which is already determined as No.

  Source Code

import sys
from math import gcd

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    S = input_data[idx].decode(); idx += 1
    
    # We need to determine for each query (L, R):
    # T_i is the substring of S^inf from position L to R.
    # We need to check if T_i appears as a contiguous substring of S.
    
    # Key observations:
    # - If R - L + 1 > N, answer is No.
    # - If R - L + 1 <= N, T_i is a substring of S+S (since S^inf has period N).
    #   Specifically, T_i starts at position ((L-1) % N) in S+S (0-indexed).
    #   T_i = (S+S)[start : start + length] where start = (L-1) % N, length = R - L + 1.
    #   This is a substring of S+S of length <= N.
    #   We need to check if this substring appears somewhere within S (positions 0..N-1, 
    #   i.e., as (S)[p : p+length] for some 0 <= p <= N - length).
    
    # If start + length <= N, then T_i = S[start : start+length], which is already a substring of S. Answer: Yes.
    # If start + length > N, then T_i wraps around. T_i = S[start:] + S[:end] where end = (start + length) - N.
    # We need to check if this concatenation appears as a substring of S.
    
    # For the wrapping case, T_i = S[start:N] + S[0:end] where end = start + length - N.
    # This is a string of length = (N - start) + end = length.
    # We need: does there exist p in [0, N-length] such that S[p:p+length] == S[start:N] + S[0:end]?
    
    # Using Z-function or string matching on carefully constructed strings.
    # 
    # Alternative approach using the "failure function" / Z-function:
    # Consider the string S + S. Any T_i (when length <= N) is a substring of S+S.
    # We need to check if that substring of S+S also appears within the first N characters of S+S (i.e., within S).
    #
    # For the non-wrapping case (start + length <= N): it's trivially in S. Answer: Yes.
    # For the wrapping case: T = S[start:] + S[:end]. We need to find this pattern in S.
    #
    # Key insight using the period structure:
    # T wraps around, meaning it's S[start:N] + S[0:end].
    # For T to appear at position p in S: S[p..p+len-1] = S[start..N-1] + S[0..end-1].
    # This means S[p..p+(N-start)-1] = S[start..N-1] AND S[p+(N-start)..p+len-1] = S[0..end-1].
    # Second condition: S[p+(N-start)+j] = S[j] for j=0..end-1, which means position p+(N-start) 
    # is a place where S "restarts", i.e., S[p+(N-start)..p+(N-start)+end-1] = S[0..end-1].
    
    # Use Z-function of S: Z[i] = length of longest common prefix of S and S[i:].
    # Condition: exists p in [0, N-length] such that:
    #   1) S[p : p+(N-start)] = S[start : N]  (suffix of S starting at 'start' matches at position p)
    #   2) Z[p + (N - start)] >= end  (at position p+(N-start), at least 'end' chars match prefix of S)
    #   Also need: p + (N-start) <= N (so that index is valid for Z), and p+(N-start) can be 0 only if p=0 and start=0 (non-wrapping).
    
    # For condition 1: S[p..p+tail-1] = S[start..N-1] where tail = N - start.
    # Build Z-function of reverse(S) to find suffix matches, or use a different construction.
    # Actually, let's build the Z-function of the string: S[start:] + '#' + S. Then positions after '#' where Z >= tail indicate matches.
    # But start varies per query... We need a general approach.
    
    # Let me use hashing for O(1) substring comparison.
    
    MOD1 = (1 << 61) - 1
    BASE1 = 131
    
    n = N
    h = [0] * (n + 1)
    pw = [1] * (n + 1)
    for i in range(n):
        h[i+1] = (h[i] * BASE1 + ord(S[i])) % MOD1
        pw[i+1] = pw[i] * BASE1 % MOD1
    
    def get_hash(l, r):  # 0-indexed [l, r)
        return (h[r] - h[l] * pw[r - l]) % MOD1
    
    # Z-function of S
    Z = [0] * n
    Z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            Z[i] = min(r - i, Z[i - l])
        while i + Z[i] < n and S[Z[i]] == S[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] > r:
            l, r = i, i + Z[i]
    
    # Suffix Z: for each position i, longest match of S[i:] with S[N-k:] (suffix matching)
    # We need: for condition 1, S[p:p+tail] == S[start:N], i.e., a suffix of S starting at 'start'.
    # Let's build "suffix array" style: reverse Z-function.
    # Let R = reverse(S). ZR = Z-function of R.
    # ZR[i] gives longest common prefix of R and R[i:], which corresponds to longest common suffix of S ending at position N-1-i in S... 
    # Actually let me think differently.
    
    # For each query with wrapping, we need to check:
    # exists p in [0, N-length] such that S[p:p+length] has hash equal to hash of T.
    # T's hash = hash(S[start:N]) concatenated with hash(S[0:end]).
    # T_hash = get_hash(start, N) * pw[end] + get_hash(0, end)) % MOD1
    # We need: exists p such that get_hash(p, p+length) == T_hash.
    # This is O(N) per query which is too slow.
    
    # Better: use the structure. T = S[start:N] + S[0:end].
    # Let tail = N - start, so length = tail + end.
    # We need p such that:
    #   S[p:p+tail] == S[start:N]  AND  S[p+tail:p+tail+end] == S[0:end]
    # 
    # Condition 2: S[p+tail : p+tail+end] == S[0:end], means Z[p+tail] >= end (if p+tail > 0), or p+tail==0 which means p=0,tail=0 impossible since tail>=1.
    # Actually p+tail can equal 0 only if p=0 and tail=0, but tail = N-start >= 1 since start < N.
    # If p+tail = N, that's out of bounds for Z. But p+tail <= p+length <= N, and p+tail = N means end=0 which contradicts wrapping.
    # So p+tail < N always in wrapping case.
    # Condition 2: Z[p+tail] >= end.
    
    # Condition 1: S[p:p+tail] == S[start:N]. Use hashing: get_hash(p, p+tail) == get_hash(start, N).
    # 
    # Precompute for each position j (1<=j<N): the set of positions where Z[j] >= some value.
    # We want: for given (start, end, tail=N-start, length=tail+end):
    #   exists p in [0, N-length] such that Z[p+tail] >= end AND get_hash(p, p+tail) == get_hash(start, N).
    #   p+tail ranges over [tail, N-length+tail] = [tail, N-end].
    #   So we need j in [tail, N-end] with Z[j] >= end and get_hash(j-tail, j) == get_hash(start, N).
    #   i.e., S[j-tail:j] == S[start:N], which is S[j-tail:j] == S[N-tail:N].
    
    # S[j-tail:j] == S[N-tail:N] means the tail characters ending at position j-1 match the last tail characters of S.
    # Define: for each position j in S (1-indexed end), let suffmatch[j] = length of longest match of S[..j-1] suffix with S's suffix.
    # More precisely, let's define using reverse Z:
    # Let R = S reversed. ZR = Z-function of R. 
    # ZR[i] for R means: longest common prefix of R and R[i:].
    # R[i:] reversed = S[0:N-i], R reversed = S.
    # Common prefix of R and R[i:] of length k means R[0:k] == R[i:i+k], 
    # which means S[N-k:N] == S[N-i-k:N-i].
    # So S[N-i-k:N-i] == S[N-k:N] with k = ZR[i].
    # In other words, the substring of S ending at position N-i-1 (0-indexed) of length ZR[i] matches the suffix of S of the same length.
    
    # We need: S[j-tail:j] == S[N-tail:N], i.e., substring ending at position j-1 of length tail matches suffix of S of length tail.
    # Using the reverse Z result: let i' be such that N - i' = j, so i' = N - j.
    # Then ZR[i'] = ZR[N-j] gives the longest match. We need ZR[N-j] >= tail.
    
    # So condition 1 becomes: ZR[N-j] >= tail, where j in [tail, N-end].
    # Combined: Z[j] >= end AND ZR[N-j] >= tail, j in [tail, N-end].
    # Note j=0 would mean ZR[N]=tail, but ZR has indices 0..N-1, so j<N always (since end>=1, j<=N-end<=N-1).
    # j=N-end: need Z[N-end]>=end. Z[0]=N>=end always, but j=N-end, if N-end=0 then j=0, Z[0]=N>=end=N, ok. And ZR[N-0]=ZR[N] which is out of bounds... 
    # Actually j ranges [tail, N-end]. If tail=0, that means start=N which won't happen. 
    # j can be 0 only if tail=0. Since we're in wrapping case, start>=1 (otherwise start=0 and start+length>N means length>N, already handled). Actually start = (L-1)%N, could be 0. If start=0, then tail=N, length=N+end>N, but we already check length<=N, so end<=0, contradiction. So start>=1, tail<=N-1, j>=tail>=1. Good.
    # N-j: j<=N-end, so N-j>=end>=1. j>=tail>=1, so N-j<=N-1. So N-j in [1,N-1], valid for ZR.
    
    R = S[::-1]
    ZR = [0] * n
    ZR[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            ZR[i] = min(r - i, ZR[i - l])
        while i + ZR[i] < n and R[ZR[i]] == R[i + ZR[i]]:
            ZR[i] += 1
        if i + ZR[i] > r:
            l, r = i, i + ZR[i]
    
    # For each j in [1, N-1], we have Z[j] and ZR[N-j].
    # For a query with (tail, end) where tail+end<=N, tail>=1, end>=1:
    #   We need: exists j in [tail, N-end] with Z[j]>=end and ZR[N-j]>=tail.
    
    # This is still potentially O(N) per query in worst case if we scan.
    # We need a smarter approach.
    
    # Observation: ZR[N-j] >= tail = N-start means the suffix match at position j is long enough.
    # Let's define for each j: a[j] = Z[j] (prefix match length), b[j] = ZR[N-j] (suffix match length).
    # We need: exists j in [tail, N-end] with a[j] >= end and b[j] >= tail.
    # Since tail + end = length, and length <= N, we have tail = length - end.
    # Actually tail = N - start, end = start + length - N. And length = R-L+1.
    
    # Alternative: note that a[j] + b[j] tells us something. If a[j] + b[j] >= N, then S is periodic
    # in a certain sense. But in general this doesn't hold.
    
    # Let me think about it differently. 
    # Condition: a[j] >= end AND b[j] >= tail, with j in [tail, N-end].
    # Note that j >= tail and b[j] >= tail: b[j] >= tail means the suffix of S of length tail matches 
    # at a certain position. The set of j where b[j] >= tail is determined by the suffix structure.
    
    # For efficiency, let's precompute for each j the value a[j] + b[j], and also precompute 
    # range-max or similar structures. But the constraints are 2D (a[j]>=end, b[j]>=tail, j in range).
    
    # Let me try: group queries. For each j, it can answer queries where tail <= j, end <= a[j], tail <= b[j], end <= N-j.
    # i.e., tail <= min(j, b[j]) and end <= min(a[j], N-j).
    # Since tail + end = length <= N, and we want the existence of ANY such j...
    
    # Key insight: if a[j] + b[j] >= length for some valid j, then we might be able to split.
    # Actually: we need a[j] >= end and b[j] >= tail. Given a[j] and b[j], the set of (tail,end) pairs
    # with tail+end=length that are satisfied is: tail <= b[j] and end <= a[j], i.e., 
    # length - a[j] <= tail <= b[j], which requires length <= a[j] + b[j].
    # Also j must be in [tail, N-end] = [tail, N-length+tail], i.e., tail in [max(1,j-?), ...].
    # Actually j in [tail, N-end]: tail <= j and j <= N-end = N-length+tail, so tail >= j-N+length = j-(N-length).
    # So tail in [max(1, j-(N-length)), j] intersected with [length-a[j], b[j]].
    
    # This is getting complex. Let me try a different approach entirely.
    
    # Approach: for each j from 1 to N-1, define c[j] = Z[j] + ZR[N-j].
    # If c[j] >= N, then for ANY wrapping query with length <= N where j is in [tail, N-end]:
    #   Since a[j]+b[j] >= N >= length = tail+end, and we need tail<=b[j], end<=a[j]:
    #   a[j] >= N - b[j], so a[j] >= N - b[j]. We need a[j]>=end=length-tail and b[j]>=tail.
    #   If a[j]+b[j]>=N>=length, then for tail = min(b[j], j) ... hmm still complicated.
    
    # Let me try the offline approach with sorting.
    # For each j in [1, N-1], we have (b[j], a[j]) meaning it can handle queries with tail<=b[j] and end<=a[j].
    # Also j must be in [tail, N-end], i.e., tail <= j <= N-end, i.e., tail <= j and tail >= j-(N-length).
    # Given tail and end (with tail+end=length), j in [tail, N-end]=[tail, N-end].
    # 
    # For a query (tail, end): answer is Yes iff exists j in [tail, N-end] with Z[j]>=end and ZR[N-j]>=tail.
    
    # Offline approach: 
    # Sort queries by 'end' in increasing order.
    # For each threshold 'end', the set of valid j's has Z[j] >= end. As 'end' increases, fewer j's are valid.
    # Among valid j's (Z[j]>=end), we need one in [tail, N-end] with ZR[N-j]>=tail.
    # 
    # Hmm, we need ZR[N-j] >= tail AND j >= tail AND j <= N-end.
    # This is a 2D range query which is hard.
    
    # Let me try yet another approach. 
    # For the wrapping case, T = S[start:] + S[:end]. 
    # Build the string P = S + '#' + S + S. Then T appears in S iff T appears in the first N characters of P.
    # But T varies per query...
    
    # Actually, let's think about it as: T is a substring of SS = S+S starting at position 'start' with length 'length'.
    # We want to know if T appears in S, i.e., appears in SS at some position p with p+length <= N.
    # So we want: the substring SS[start:start+length] appears at some position in S.
    # 
    # This is equivalent to: in the string SS, do the substrings SS[start:start+length] and SS[p:p+length] 
    # match for some p in [0, N-length]?
    # 
    # Using suffix array of SS (length 2N), we can answer "does this substring appear at any position in [0, N-length]?"
    # This is a classic problem: given a suffix array, for a query substring, find its range in the SA,
    # then check if any suffix in that range starts at position <= N-length.
    
    # SA of SS has length 2N. For each query, find the range [lo, hi] in SA where the substring SS[start:start+length] matches,
    # then check if min of starting positions in SA[lo:hi+1] is <= N-length.
    # With sparse table for range-min, this is O(1) per query after O(N log N) preprocessing.
    
    # Building SA of length 2N where N can be 5*10^5: SA of length 10^6, feasible with SA-IS or DC3 in O(N).
    # In Python, building SA might be slow... Let me try with the doubling approach.
    
    # Actually, let's use a simpler approach. We can build the suffix array of S + S using the doubling method.
    # But in Python, for N up to 5*10^5, SS has length 10^6. Suffix array construction in Python might be too slow.
    
    # Let me think about using hashing instead.
    # For each query: we have T = SS[start:start+length]. We want to check if T appears in S.
    # We can compute the hash of T, then check against all substrings of S of the same length.
    # But that's O(N) per query.
    
    # With some precomputation: for each length l, store all hashes of substrings of S of length l in a set.
    # But l can vary per query, and there are up to N distinct lengths, each with up to N hashes. 
    # Total storage O(N^2), too much.
    
    # OK here's another idea that might work:
    # 
    # For the wrapping case, we need j in [1, N-1] such that:
    #   Z[j] >= end AND ZR[N-j] >= tail AND j >= tail AND j <= N - end
    #
    # Let's define for each j: the "coverage" is the set of (tail, end) pairs it satisfies.
    # tail <= min(j, ZR[N-j]) and end <= min(Z[j], N-j).
    # So the maximum length it can handle is min(j, ZR[N-j]) + min(Z[j], N-j).
    # 
    # For a given query, we need any j that covers it.
    # 
    # Let me define: for each j, let bj = min(j, ZR[N-j]) and aj = min(Z[j], N-j).
    # Then j satisfies the query (tail, end) iff tail <= bj and end <= aj.
    # The query is answerable iff exists j with tail <= bj and end <= aj.
    # This is a dominance query: given a set of points (bj, aj), does any point dominate (tail, end)?
    # i.e., exists (bj, aj) with bj >= tail and aj >= end.
    # This is equivalent to: max(aj : bj >= tail) >= end.
    # 
    # So if we sort the points by bj in decreasing order and compute prefix max of aj,
    # or equivalently, define f(tail) = max(aj : bj >= tail), then answer is Yes iff f(tail) >= end.
    # f is non-increasing. We can compute f for all tail values from 1 to N-1.
    
    # This is O(N) precomputation and O(1) per query!
    # 
    # Wait, let me double-check. The constraint was:
    # j in [tail, N-end], Z[j] >= end, ZR[N-j] >= tail.
    # 
    # j >= tail: included in bj = min(j, ZR[N-j]) >= tail, since bj >= tail implies j >= tail.
    # j <= N-end: included in aj = min(Z[j], N-j) >= end, since aj >= end implies N-j >= end, i.e., j <= N-end.
    # Z[j] >= end: included in aj >= end since aj = min(Z[j], N-j).
    # ZR[N-j] >= tail: included in bj >= tail since bj = min(j, ZR[N-j]).
    # 
    # Yes! All four conditions are captured by bj >= tail and aj >= end.
    # So f(tail) = max over {j : bj >= tail} of aj.
    # Answer Yes iff f(tail) >= end.
    
    # Precompute f:
    # f[t] = max(aj for j in 1..N-1 if min(j, ZR[N-j]) >= t)
    # for t = 1, 2, ..., N-1.
    
    # To compute: iterate over all j from 1 to N-1, for each j, it contributes to all t <= bj.
    # f[t] = max of aj over all j with bj >= t.
    # Compute: create array f of size N+1, init 0.
    # For each j, f[1..bj] could be updated with aj. But that's O(N) per j in worst case.
    # Better: f[bj] = max(f[bj], aj) for each j, then sweep from right to left:
    # f[t] = max(f[t], f[t+1]).
    
    # Wait, f[t] = max over {j: bj >= t} of aj = max over {j: bj = t} of aj, union with {j: bj > t}.
    # So f[t] = max(f[t+1], max(aj for j with bj = t)).
    # So: initialize g[t] = max(aj for j with bj = t), then f[t] = max(g[t], f[t+1]).
    
    max_b = N  # bj can be at most N-1 since j <= N-1 and ZR[N-j] <= N.
    g = [0] * (N + 1)
    
    for j in range(1, N):
        bj = min(j, ZR[N - j])
        aj = min(Z[j], N - j)
        if bj >= 1 and aj >= 1:
            if aj > g[bj]:
                g[bj] = aj
    
    f = [0] * (N + 2)
    for t in range(N, 0, -1):
        f[t] = max(g[t] if t <= N else 0, f[t + 1] if t + 1 <= N + 1 else 0)
    
    out = []
    for i in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        length = R - L + 1
        if length > N:
            out.append("No")
            continue
        start = (L - 1) % N  # 0-indexed start in S
        # T = (S+S)[start : start+length]
        if start + length <= N:
            # T is entirely within S, so it's trivially a substring of S
            out.append("Yes")
            continue
        # Wrapping case
        tail = N - start  # length of suffix part: S[start:N]
        end = length - tail  # length of prefix part: S[0:end]
        # Need f[tail] >= end
        if tail <= N and f[tail] >= end:
            out.append("Yes")
        else:
            out.append("No")
    
    sys.stdout.write('\n'.join(out) + '\n')

solve()

---

This editorial was generated by claude4.6opus-thinking.