Nearly Cyclic String

Time Limit : 2 sec, Memory Limit : 262144 KB

ほぼ周期文字列

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

文字列 W が周期 t の文字列であるとは、i\ =\ 1,\2,\... ,\ |W| − 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 − 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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 2, Tokyo, Japan, 2015-09-12
http://acm-icpc.aitea.net/
http://jag2015summer-day2.contest.atcoder.jp/