Problem:


ほぼ周期文字列

文字列 S が与えられる。この文字列 S に対し、Q 個のクエリに答えよ。
 i 番目のクエリでは、S[l_i,\ r_i] から1文字まで変えてよいとき、S[l_i,\ r_i] を周期 t_i の文字列にできるかどうかを判定せよ。S[l,\ r] は文字列 S の l 文字目から r 文字目までの部分文字列を表す。

文字列 W が周期 t の文字列であるとは、i\ =\ 1,\2,\... ,\ |W| &minus; t に対し、
 W_{i} = W_{i+t}
となることとする。

Constraints

1  ≤  |S|  ≤  10^5

1  ≤  Q  ≤  10^5

1  ≤  l_i  ≤  r_i  ≤  |S|

1  ≤  t_i  ≤  r_i &minus; l_i+1 

Sはアルファベットの小文字のみからなる

Input Format

入力は以下の形式で標準入力から与えられる。

S
Q
l_1 r_1 t_1
...
l_Q r_Q t_Q

Output Format

Q 行にわたって出力せよ。
i 行目には、i 番目のクエリの答えを
Yes または No で出力せよ。

Sample Input 1

abcabcaxcabc
4
1 9 3
8 12 3
1 4 2
2 3 2

Sample Output 1

Yes
Yes
No
Yes

Sample Input 2

isuruu
4
3 6 1
3 6 2
3 6 3
2 4 1

Sample Output 2

Yes
Yes
Yes
No



Sample input:
abcabcaxcabc
4
1 9 3
8 12 3
1 4 2
2 3 2


Sample output:
Yes
Yes
No
Yes

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    base = 37; MOD = 10**9 + 9
    S = readline().strip()
    L = len(S)
    H = [0]*(L+1)
    pw = [1]*(L+1)
    ca = ord('a')
    v = 0
    for i in range(L):
        H[i+1] = v = (v * base + (ord(S[i]) - ca)) % MOD
    v = 1
    for i in range(1, L+1):
        pw[i] = v = v * base % MOD
    Q = int(readline())
    for i in range(Q):
        l, r, t = map(int, readline().split()); l -= 1
        m = r-l
        if ((H[r]-H[r-t]) - (H[l+t]-H[l]) * pw[m-t]) % MOD == 0:
            write("Yes\n")
            continue
        left = 0; right = m-t+1
        base = H[l] - H[l+t]
        while left+1 < right:
            mid = (left + right) >> 1
            if ((H[l+mid]-H[l+t+mid]) - base * pw[mid]) % MOD == 0:
                left = mid
            else:
                right = mid
        l1 = left
        left = 0; right = m-t-l1+1
        base = (H[r-t]-H[r]) % MOD
        while left+1 < right:
            mid = (left + right) >> 1
            if (H[r-t-mid]-H[r-mid]) * pw[mid] % MOD == base:
                left = mid
            else:
                right = mid
        l2 = left
        if l1+l2+1 == m-t:
            if l1 <= t or l2 <= t:
                write("Yes\n")
            else:
                write("No\n")
        else:
            if ((H[l+m-t-l2-1]-H[l+m-l2-1]) - (H[l+l1+1]-H[l+t+l1+1]) * pw[m-t-l2-l1-2]) % MOD != 0:
                write("No\n")
            else:
                p1 = l1; p2 = m-t-l2-1
                if p2 - p1 == t and S[l+p2-t] == S[l+p2+t]:
                    write("Yes\n")
                else:
                    write("No\n")
solve()