← 返回题目列表

AtCoder · icpc2015summer_day2_f

F. 几乎周期字符串

中文机器翻译题面 查看原题

问题陈述

文字列 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} 。


约束

  • 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仅由字母表中的小写字母组成 输出超过

输入格式

输入是按以下格式从标准输入给出的。
S
Q
l_1 r_1 t_1
...
l_Q r_Q t_Q

输出格式

Q 行。 第 i 行中,i 个查询的答案是 输出为 Yes 或 至少 No 。

示例输入 1

abcabcaxcabc
4
1 9 3
8 12 3
1 4 2
2 3 2

示例输出 1

Yes
Yes
No
Yes

示例输入 2

isuruu
4
3 6 1
3 6 2
3 6 3
2 4 1

示例输出 2

Yes
Yes
Yes
No