F - ほぼ周期文字列
Editorial
/
入力は以下の形式で標準入力から与えられる。
Q 行にわたって出力せよ。
i 行目には、i 番目のクエリの答えを
Time Limit: 2 sec / Memory Limit: 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
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