Background

Some definitions and conventions about strings are explained in the “Help / Hint” section.

Please do not maliciously exploit the judge.

Xiao A is reading an article — “How to AK NOI Elegantly?”.

Problem Description

Unfortunately, this article is written in English. Xiao A has very poor eyesight, and his vocabulary is also very small.

Specifically, this article can be represented by a string $t$. Another string $s$ is given: every word that Xiao A knows is a substring of $s$ with length at least $k$.

A text segment $T$ is called “readable” if and only if it can be split into several words that Xiao A can understand. For example, when $k=2$ and $s=\texttt{abcd}$, $\texttt{abcd/abc}$ and $\texttt{cd/ab/bc/bcd}$ are readable, while $\texttt{abcc}$ and $\texttt{tzcaknoi}$ are not readable.

Next, Xiao A will perform $q$ actions:

• Type 1: Rub his eyes. Specifically, Xiao A chooses a substring $t[l:r]$ of the article $t$ and modifies it into a string $x\ (|x|=r-l+1)$.
• Type 2: Read the article. Specifically, Xiao A chooses a substring $t[l:r]$ of the article $t$ and reads it. For each Type 2 operation, you need to tell Xiao A whether he can understand this text segment. If he can understand it, output Yes; otherwise output No.

Input Format

The first line contains a positive integer $T$, indicating the Subtask ID for this test point.
The second line contains a string $s$.
The third line contains a string $t$.
The fourth line contains a positive integer $k$.
The fifth line contains a positive integer $q$.

The next $q$ lines each describe one query. First, an operation parameter $op$ is given:

• If $op=1$, then two positive integers $l,r$ and a string $x$ follow, meaning to modify $t[l:r]$ into $x$.
• If $op=2$, then two positive integers $l,r$ follow, meaning one query.

Output Format

For each query, output one line: if it is readable, output Yes; otherwise output 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

Hint

“Constraints and Conventions”

Let $n=|s|$, $m=|t|$, $L=\sum |x|$.

For $100\%$ of the data: $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$. It is guaranteed that $|x|=r-l+1$, and the character set is $[\texttt{a,i}]$.

Subtask 0 contains the sample and Hack testdata.

• Subtask 0 ~ 3: time limit 1s.
• Subtask 4 ~ 6: time limit 1.5s.
• Subtask 7: time limit 3s.
• Subtask 8: time limit 4.5s.

“Subtask Dependencies”

This problem uses subtask dependencies.

Simply put, if Subtask a depends on Subtask b, then Subtask a will be counted toward the total score only when you pass all test points of Subtask b.

• Subtask 1 depends on Subtask 0.
• Subtask 2 depends on Subtask 0,1.
• Subtask 3 depends on Subtask 0,1,2.
• Subtask 6 depends on Subtask 0,5.
• Subtask 7 depends on Subtask 0,5,6.
• Subtask 8 depends on Subtask 0~7.

It is guaranteed that the Hack testdata of Subtask 0 satisfies all constraints of Subtask 1,2,3,6,7,8.

“Help / Hint”

A string $t'$ is a substring of $t$ if and only if we can delete some characters (possibly none) from the beginning and the end of $t$ and obtain $t'$.
Define $t[l:r]$ as the string formed by $t_lt_{l+1}\cdots t_{r-1}t_r$.

The input file is large, so please pay attention to IO optimization.

“Source”

Sweet Round 07 E.
idea & solution & data: Alex_Wei; problem checking: tzc_wk.

Translated by ChatGPT 5