题目描述

你拥有 $N$ 枚瓷砖，编号为 $1$ 到 $N$。每枚瓷砖的正面和反面颜色均为黑色或白色。这里，黑色用字符 'B' 表示，白色用字符 'W' 表示。瓷砖 $i$（$1 \le i \le N$）的正面颜色由字符串 $S$ 的第 $i$ 个字符表示，瓷砖 $i$ 的反面颜色由字符串 $T$ 的第 $i$ 个字符表示。

乌兹别克斯坦以其瓷砖装饰的历史建筑而闻名。在参观了乌兹别克斯坦的清真寺和伊斯兰学校后，你被这些美丽的建筑所吸引，并购买了一台奇特的机器。这台机器左右两侧各有一个平台，在每个平台上各放置一枚瓷砖，就可以用这两枚瓷砖换得一枚新瓷砖。设左平台放置的瓷砖为 $a$，右平台放置的瓷砖为 $b$，则用 $a$ 和 $b$ 换得的新瓷砖 $c$ 满足以下条件：

• $c$ 的正面颜色：若 $a$ 的反面颜色与 $b$ 的正面颜色相同则为黑色，否则为白色。
• $c$ 的反面颜色：若 $a$ 的正面颜色与 $b$ 的反面颜色相同则为黑色，否则为白色。

你打算用这 $N$ 枚瓷砖和这台奇特机器，在 $Q$ 天里进行以下活动。第 $j$ 天（$1 \le j \le Q$）的活动为模式 1 或模式 2 之一：

• 模式 1：将瓷砖 $X_j$ 的正面颜色改为字符 $Y_j$ 所表示的颜色，并将瓷砖 $X_j$ 的反面颜色改为字符 $Z_j$ 所表示的颜色。其中 $Y_j, Z_j$ 为 'B' 或 'W'。
• 模式 2：将瓷砖 $L_j, L_j+1, \dots, R_j$ 按此顺序从左到右排成一列。针对这一列，你可以进行任意次（$0$ 次到 $R_j - L_j$ 次）以下操作，然后思考能否使得该列中正面为白色的瓷砖恰好为 $M_j$ 枚：
  • 选择列中相邻的两枚瓷砖，将它们从列中取出。将这两枚瓷砖中原本位于左侧的放到机器的左平台，右侧的放到右平台，用这两枚瓷砖换得一枚新瓷砖，然后将这枚新瓷砖插入到列中原本两枚瓷砖所在的位置。

给定瓷砖的信息以及每天活动的信息，请编写一个程序，输出所有模式 2 活动的判定结果。

输入格式

输入从标准输入中以以下格式给出：

$N$
$S$
$T$
$Q$
(Query 1)
(Query 2)
$\vdots$
(Query $Q$)

每个 (Query $j$)（$1 \le j \le Q$）包含若干个由空格分隔的整数或字符。其中第一个数为整数 $1$ 或 $2$，记作 $P_j$，则该行的具体内容为以下两种之一：

• 当 $P_j = 1$ 时，该行紧接着有一个整数 $X_j$ 和两个字符 $Y_j, Z_j$，按此顺序给出。表示第 $j$ 天的活动为模式 1，即把瓷砖 $X_j$ 的正面颜色改为 $Y_j$ 所表示的颜色，反面颜色改为 $Z_j$ 所表示的颜色。其中 $Y_j, Z_j$ 为 B 或 W。
• 当 $P_j = 2$ 时，该行紧接着有三个整数 $L_j, R_j, M_j$，按此顺序给出。表示第 $j$ 天的活动为模式 2，即将瓷砖 $L_j, L_j+1, \dots, R_j$ 按此顺序从左到右排成一列，并通过操作思考能否使该列中正面为白色的瓷砖恰好为 $M_j$ 枚。

输出格式

对于所有满足 $P_j = 2$ 的 $j$（$1 \le j \le Q$），按 $j$ 的升序每行输出一个结果：如果能使该列中正面为白色的瓷砖恰好为 $M_j$ 枚，则输出 Yes，否则输出 No。

4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1

Yes
Yes
No
Yes

6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2

No
Yes
Yes
Yes
Yes
No
No
Yes

提示

样例解释 1

• 第 1 天：将瓷砖 $3,4$ 按此顺序从左到右排成一列。若不进行任何操作，则只有瓷砖 $3$ 的正面为白色，因此可以使正面为白色的瓷砖恰好为 $1$ 枚。故输出 Yes。
• 第 2 天：将瓷砖 $1,2$ 按此顺序排成一列。若选择瓷砖 $1$ 和 $2$ 进行一次操作，操作后的列包含一枚瓷砖，该瓷砖的正面和反面均为黑色，因此可以使正面为白色的瓷砖恰好为 $0$ 枚。故输出 Yes。
• 第 3 天：将瓷砖 $3$ 的正面和反面均改为黑色。
• 第 4 天：将瓷砖 $3,4$ 排成一列。可以证明无法通过操作使正面为白色的瓷砖恰好为 $2$ 枚。故输出 No。
• 第 5 天：将瓷砖 $2,3,4$ 排成一列。若先选择瓷砖 $3$ 和 $4$ 进行一次操作，操作后列中有两枚瓷砖：左侧为瓷砖 $2$，右侧为新瓷砖（其正面和反面均为黑色）。再选择这两枚瓷砖进行一次操作，操作后列中剩一枚瓷砖，其正面为白色、反面为黑色，因此可以使正面为白色的瓷砖恰好为 $1$ 枚。故输出 Yes。

该输入样例满足子任务 $1,5,6,7$ 的数据范围。

数据范围

• $1 \le N \le 300\,000$
• $S$ 是由 B、W 组成的长度为 $N$ 的字符串
• $T$ 是由 B、W 组成的长度为 $N$ 的字符串
• $1 \le Q \le 300\,000$
• $P_j$ 为 $1$ 或 $2$（$1 \le j \le Q$）
• 当 $P_j = 1$ 时，$1 \le X_j \le N$（$1 \le j \le Q$）
• 当 $P_j = 1$ 时，$Y_j$ 为 'B' 或 'W'（$1 \le j \le Q$）
• 当 $P_j = 1$ 时，$Z_j$ 为 'B' 或 'W'（$1 \le j \le Q$）
• 当 $P_j = 2$ 时，$1 \le L_j \le R_j \le N$（$1 \le j \le Q$）
• 当 $P_j = 2$ 时，$0 \le M_j \le R_j - L_j + 1$（$1 \le j \le Q$）
• $N, Q, P_j, X_j, L_j, R_j, M_j$ 均为整数

子任务

1. (6 分) $N \le 6$
2. (10 分) $N \le 100$，且 $P_j = 2$（$1 \le j \le Q$）
3. (9 分) $N \le 500$，且 $P_j = 2$（$1 \le j \le Q$）
4. (8 分) $N \le 1700$，且 $P_j = 2$（$1 \le j \le Q$）
5. (23 分) $N \le 10\,000$，$Q \le 10\,000$
6. (14 分) $N \le 100\,000$，$Q \le 100\,000$
7. (30 分) 无额外限制

翻译由 DeepSeek 完成