题目背景

一些关于字符串的定义与约定详见「帮助 / 提示」部分。

请不要恶意卡评测。

---

小 A 正在读一篇文章 ——《如何优雅地 AK NOI？》

题目描述

不幸的是，这篇文章是用英语写的。小 A 的视力很糟糕，同时词汇量也很小。

具体地，这篇文章可以用一个字符串 $t$ 表示。同时给出另一个字符串 $s$：小 A 所有认识的单词，都是 $s$ 的长度不小于 $k$ 的子串。

一段文字 $T$ 被称为「可读懂的」，当且仅当其能被分割成若干个小 A 读得懂的单词。例如当 $k=2$，$s=\texttt{abcd}$ 时，$\texttt{abcd/abc}$ 和 $\texttt{cd/ab/bc/bcd}$ 就是可读懂的，而 $\texttt{abcc}$ 和 $\texttt{tzcaknoi}$ 就是不可读懂的。

接下来，小 A 会进行 $q$ 次行动：

• Type 1：擦亮眼睛。具体地，小 A 会选择文章 $t$ 的一个子串 $t[l:r]$，并将其修改为字符串 $x\ (|x|=r-l+1)$。
• Type 2：阅读文章。具体地，小 A 会选择文章 $t$ 的一个子串 $t[l:r]$ 并进行阅读。对于每次 Type 2 的操作，你需要告诉小 A 他能不能看懂这段文字。能够读懂则输出 Yes，否则输出 No。

输入格式

第一行一个正整数 $T$，表示该点 Subtask 编号。
第二行一个字符串 $s$。
第三行一个字符串 $t$。
第四行一个正整数 $k$。
第五行一个正整数 $q$。

接下来 $q$ 行，每行表示一个询问。首先给出操作参数 $op$：

• 若 $op=1$，则接下来两个正整数 $l,r$ 与一个字符串 $x$，表示将 $t[l:r]$ 修改为 $x$。
• 若 $op=2$，则接下来两个正整数 $l,r$，表示一次询问。

输出格式

对于每个询问输出一行字符串：若可以读懂则输出 Yes，否则输出 No。

0
bbccabcacbcbac
cbcacbcabbcabca
3
17
2 1 2
2 1 4
2 1 6
2 2 15
2 6 15
2 9 15
1 4 13 babbccabbd
2 1 11
2 1 12
2 1 15
2 5 11
1 13 15 cab
2 3 12
2 7 10
2 11 15
2 10 14
2 9 14

No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
No
No
Yes

提示

「数据范围与约定」

记 $n=|s|$，$m=|t|$，$L=\sum |x|$。

Subtask	$n\leq$	$m\leq$	$L\leq$	$q\leq$	$k\leq$	分值
0						0 point
1	$70$			$70$		10 points
2	$200$			$200$
3	$10^3$			$10^3$
4					$1$
5	$2\times 10^5$	$10^5$	$0$	$2\times 10^4$	$5$	15 points
6			$5\times 10^4$			10 points
7					$6$	15 points
8						20 points

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^6$，$1\leq L\leq 3\times 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq q\leq 10^5$，$1\leq k\leq 8$。 保证 $|x|=r-l+1$，且字符集为 $[\texttt{a,i}]$。

---

Subtask 0 是样例及 Hack 数据。

• Subtask 0 ~ 3 时间限制 1s。
• Subtask 4 ~ 6 时间限制 1.5s。
• Subtask 7 时间限制 3s。
• Subtask 8 时间限制 4.5s。

「子任务依赖」

本题使用子任务依赖。

简单地说，如果 Subtask a 依赖于 Subtask b，那么只有你通过 Subtask b 的全部测试点时，Subtask a 才会计入总分。

• Subtask 1 依赖于 Subtask 0。
• Subtask 2 依赖于 Subtask 0,1。
• Subtask 3 依赖于 Subtask 0,1,2。
• Subtask 6 依赖于 Subtask 0,5。
• Subtask 7 依赖于 Subtask 0,5,6。
• Subtask 8 依赖于 Subtask 0~7。

保证 Subtask 0 的 Hack 数据符合 Subtask 1,2,3,6,7,8 的所有限制。

「帮助 / 提示」

字符串 $t'$ 是 $t$ 的子串，当且仅当我们能够从 $t$ 的开头和结尾删除若干个字符（可以不删除）并得到 $t'$。
定义 $t[l:r]$ 表示 $t_lt_{l+1}\cdots t_{r-1}t_r$ 所形成的字符串。

读入文件较大，请注意 IO 优化。

「题目来源」

Sweet Round 07 E。
idea & solution & data：Alex_Wei；验题：tzc_wk。