Almost Periodic String

You are given a string $S$. Answer $Q$ queries about this string $S$. In the $i$-th query, you may change up to one character in $S[l_i, r_i]$. Determine whether $S[l_i, r_i]$ can be made into a string of period $t_i$. Here $S[l, r]$ denotes the substring of $S$ from the $l$-th character to the $r$-th character.

A string $W$ is a string of period $t$ if $W_i = W_{i+t}$ for every $i = 1, 2, ..., |W|-t$.

The input is given from standard input in the following format.

$S$

$Q$

$l_1$ $r_1$ $t_1$

$...$

$l_Q$ $r_Q$ $t_Q$

Output $Q$ lines. The $i$-th line must contain the answer to the $i$-th query as Yes or 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$ consists only of lowercase English letters