「SWTR-7」How to AK NOI?

#### 一些关于字符串的定义与约定详见「帮助 / 提示」部分。 #### 请不要恶意卡评测。 --- 小 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$ | | $70$ | | 10 points | | 2 | $200$ | $200$ | | $200$ | | 10 points | | 3 | $10^3$ | $10^3$ | | $10^3$ | | 10 points | | 4 | | | | | $1$ | 10 points | | 5 | $2\times 10^5$ | $10^5$ | $0$ | $2\times 10^4$ | $5$ | 15 points | | 6 | $2\times 10^5$ | $10^5$ | $5\times 10^4$ | $2\times 10^4$ | $5$ | 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](https://www.luogu.com.cn/contest/51773) E。 idea & solution & data：[Alex_Wei](https://www.luogu.com.cn/user/123294)；验题：[tzc_wk](https://www.luogu.com.cn/user/115194)。