310480: CF1840E. Character Blocking

E. Character Blockingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two strings of equal length $s_1$ and $s_2$, consisting of lowercase Latin letters, and an integer $t$.

You need to answer $q$ queries, numbered from $1$ to $q$. The $i$-th query comes in the $i$-th second of time. Each query is one of three types:

• block the characters at position $pos$ (indexed from $1$) in both strings for $t$ seconds;
• swap two unblocked characters;
• determine if the two strings are equal at the time of the query, ignoring blocked characters.

Note that in queries of the second type, the characters being swapped can be from the same string or from $s_1$ and $s_2$.

Input

The first line of the input contains a single integer $T$ ($1 \le T \le 10^4$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains a string $s_1$ consisting of lowercase Latin letters (length no more than $2 \cdot 10^5$).

The second line of each test case contains a string $s_2$ consisting of lowercase Latin letters (length no more than $2 \cdot 10^5$).

The strings have equal length.

The third line of each test case contains two integers $t$ and $q$ ($1 \le t, q \le 2 \cdot 10^5$). The number $t$ indicates the number of seconds for which a character is blocked. The number $q$ corresponds to the number of queries.

Each of the next $q$ lines of each test case contains a single query. Each query is one of three types:

• "$1\ \ \ pos$" — block the characters at position $pos$ in both strings for $t$ seconds;
• "$2\ \ \ 1/\;\!2\ \ \ pos_1\ \ \ 1/\;\!2\ \ \ pos_2$" — swap two unblocked characters. The second number in the query indicates the number of the string from which the first character for the swap is taken. The third number in the query indicates the position in that string of that character. The fourth number in the query indicates the number of the string from which the second character for the swap is taken. The fifth number in the query indicates the position in that string of that character;
• "$3$" — determine if the two strings are equal at the time of the query, ignoring blocked characters.

For queries of the first type, it is guaranteed that at the time of the query, the characters at position $pos$ are not blocked.

For queries of the second type, it is guaranteed that the characters being swapped are not blocked.

All values of $pos, pos_1, pos_2$ are in the range from $1$ to the length of the strings.

The sum of the values of $q$ over all test cases, as well as the total length of the strings $s_1$, does not exceed $2 \cdot 10^5$.

Output

For each query of the third type, output "YES" if the two strings $s_1$ and $s_2$ are equal at the time of the query, ignoring blocked characters, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes" and "YES" will be accepted as a positive answer.

ExampleInput

2
codeforces
codeblocks
5 7
3
1 5
1 6
1 7
1 9
3
3
cool
club
2 5
2 1 2 2 3
2 2 2 2 4
1 2
3
3

Output

NO
YES
NO
YES
NO

Note

Let's look at the strings $s_1$ and $s_2$ after each of the $q$ queries. Blocked characters will be denoted in red.

First example input:

($codeforces$, $codeblocks$) $\rightarrow$ ($codeforces$, $codeblocks$) $\rightarrow$ ($code\color{red}{f}orces$, $code\color{red}{b}locks$) $\rightarrow$ ($code\color{red}{fo}rces$, $code\color{red}{bl}ocks$) $\rightarrow$ ($code\color{red}{for}ces$, $code\color{red}{blo}cks$) $\rightarrow$ ($code\color{red}{for}c\color{red}{e}s$, $code\color{red}{blo}c\color{red}{k}s$) $\rightarrow$ ($code\color{red}{for}c\color{red}{e}s$, $code\color{red}{blo}c\color{red}{k}s$) $\rightarrow$ ($codef\color{red}{or}c\color{red}{e}s$, $codeb\color{red}{lo}c\color{red}{k}s$)

Second example input:

($cool$, $club$) $\rightarrow$ ($cuol$, $clob$) $\rightarrow$ ($cuol$, $cbol$) $\rightarrow$ ($c\color{red}{u}ol$, $c\color{red}{b}ol$) $\rightarrow$ ($c\color{red}{u}ol$, $c\color{red}{b}ol$) $\rightarrow$ ($cuol$, $cbol$)

题目大意：
你被给定了两个等长的由小写拉丁字母组成的字符串s1和s2，以及一个整数t。你需要回答q个查询，编号从1到q。第i个查询在第i秒发生。每个查询是以下三种类型之一：
1. 阻塞位置pos（从1开始索引）在两个字符串中的字符，持续t秒；
2. 交换两个未阻塞的字符；
3. 判断在查询时刻，忽略阻塞字符后，两个字符串是否相等。

注意，在第二种类型的查询中，被交换的字符可以来自同一个字符串，也可以来自s1和s2。

输入输出数据格式：
输入：
- 第一行包含一个整数T（1≤T≤10^4）——测试用例的数量。
- 接下来是T个测试用例的描述。
- 每个测试用例的第一行包含一个由小写拉丁字母组成的字符串s1（长度不超过2×10^5）。
- 每个测试用例的第二行包含一个由小写拉丁字母组成的字符串s2（长度不超过2×10^5）。
- 字符串长度相等。
- 每个测试用例的第三行包含两个整数t和q（1≤t,q≤2×10^5）。数字t表示字符被阻塞的秒数。数字q对应查询的数量。
- 接下来的q行，每行包含一个查询。每个查询是三种类型之一：
- "1 pos" —— 阻塞位置pos在两个字符串中的字符，持续t秒；
- "2 1/2 pos1 1/2 pos2" —— 交换两个未阻塞的字符。查询中的第二个数字表示第一个交换字符来自的字符串编号。第三个数字表示该字符在字符串中的位置。第四个数字表示第二个交换字符来自的字符串编号。第五个数字表示该字符在字符串中的位置；
- "3" —— 判断在查询时刻，忽略阻塞字符后，两个字符串是否相等。

输出：
- 对于每个第三种类型的查询，如果查询时刻忽略阻塞字符后，字符串s1和s2相等，输出"YES"，否则输出"NO"。
- 输出每个字母可以是任何大小写。例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。

示例：
输入：
2
codeforces
codeblocks
5 7
3
1 5
1 6
1 7
1 9
3
3
cool
club
2 5
2 1 2 2 3
2 2 2 2 4
1 2
3
3
输出：
NO
YES
NO
YES
NO

注意：
- 在每个查询中，pos、pos1、pos2的值都在1到字符串长度的范围内。
- 所有测试用例的q值之和，以及字符串s1的总长度，不超过2×10^5。题目大意： 你被给定了两个等长的由小写拉丁字母组成的字符串s1和s2，以及一个整数t。你需要回答q个查询，编号从1到q。第i个查询在第i秒发生。每个查询是以下三种类型之一： 1. 阻塞位置pos（从1开始索引）在两个字符串中的字符，持续t秒； 2. 交换两个未阻塞的字符； 3. 判断在查询时刻，忽略阻塞字符后，两个字符串是否相等。 注意，在第二种类型的查询中，被交换的字符可以来自同一个字符串，也可以来自s1和s2。 输入输出数据格式： 输入： - 第一行包含一个整数T（1≤T≤10^4）——测试用例的数量。 - 接下来是T个测试用例的描述。 - 每个测试用例的第一行包含一个由小写拉丁字母组成的字符串s1（长度不超过2×10^5）。 - 每个测试用例的第二行包含一个由小写拉丁字母组成的字符串s2（长度不超过2×10^5）。 - 字符串长度相等。 - 每个测试用例的第三行包含两个整数t和q（1≤t,q≤2×10^5）。数字t表示字符被阻塞的秒数。数字q对应查询的数量。 - 接下来的q行，每行包含一个查询。每个查询是三种类型之一： - "1 pos" —— 阻塞位置pos在两个字符串中的字符，持续t秒； - "2 1/2 pos1 1/2 pos2" —— 交换两个未阻塞的字符。查询中的第二个数字表示第一个交换字符来自的字符串编号。第三个数字表示该字符在字符串中的位置。第四个数字表示第二个交换字符来自的字符串编号。第五个数字表示该字符在字符串中的位置； - "3" —— 判断在查询时刻，忽略阻塞字符后，两个字符串是否相等。 输出： - 对于每个第三种类型的查询，如果查询时刻忽略阻塞字符后，字符串s1和s2相等，输出"YES"，否则输出"NO"。 - 输出每个字母可以是任何大小写。例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。 示例： 输入： 2 codeforces codeblocks 5 7 3 1 5 1 6 1 7 1 9 3 3 cool club 2 5 2 1 2 2 3 2 2 2 2 4 1 2 3 3 输出： NO YES NO YES NO 注意： - 在每个查询中，pos、pos1、pos2的值都在1到字符串长度的范围内。 - 所有测试用例的q值之和，以及字符串s1的总长度，不超过2×10^5。