F - ほぼ周期文字列 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

文字列 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|-t に対し、 W_{i} = W_{i+t} となることとする。

Constraints

  • 1 \leq |S| \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq l_i \leq r_i \leq |S|
  • 1 \leq t_i \leq r_i-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