22415번 - ほぼ周期文字列 다국어

文字列 $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}$ となることとする。

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

$S$

$Q$

$l_1$ $r_1$ $t_1$

$...$

$l_Q$ $r_Q$ $t_Q$

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

• $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$はアルファベットの小文字のみからなる