题目描述

译自 JOI Open 2021 T1 「交配 / Crossing」

你知道「净是一些奇怪研究实验室」（Just Odd Investigations Laboratory）吗？这个实验室的业务就是去做「奇怪的研究」的。接下来我们简称其为 JOI 实验室。

最近几年，在世界各地的几个历史遗迹发现了盛开的大片花田。JOI 实验室发现花田中的花是新品种，并且它们的基因有相似的特征。这些新品种的花的基因是长度为 $N$ 且由 $\texttt{J, O, I}$ 组成的字符串。这些字符串被称为基因序列。

你是在 JOI 实验室工作的研究院。你最初有三朵新品种的花。它们的基因序列分别为 $S_A,S_B,S_C$。

你可以通过杂交的方式，让两朵新品种的花产生一种新品种的花。新得到的花的基因序列中第 $i$ 个字母按如下方式确定：

• 如果两朵花的基因序列中第 $i$ 个字母是一样的，新得到的花的基因序列中第 $i$ 个字母将会和两亲本第 $i$ 个字母一致；
• 如果两朵花的基因序列中第 $i$ 个字母是不一样的，新得到的花的基因序列中第 $i$ 个字母将会是 $\texttt{J, O, I}$ 中的一个，并和两亲本第 $i$ 个字母都不一样；

换句话说，如果两朵花基因序列的第 $i$ 个字母分别为 $c_1$ 和 $c_2$，新得到的花朵的基因序列中第 $i$ 个字母 $c_3$ 如下表所示：

$c_1$	$\texttt J$	$\texttt J$	$\texttt J$	$\texttt O$	$\texttt O$	$\texttt O$	$\texttt I$	$\texttt I$	$\texttt I$
$c_2$	$\texttt J$	$\texttt O$	$\texttt I$	$\texttt J$	$\texttt O$	$\texttt I$	$\texttt J$	$\texttt O$	$\texttt I$
$c_3$	$\texttt J$	$\texttt I$	$\texttt O$	$\texttt I$	$\texttt O$	$\texttt J$	$\texttt O$	$\texttt J$	$\texttt I$

你可以用相同的花朵杂交任意多次。如果你得到了一种新的花朵，你可以在随后的杂交中使用。

为了获得更多好看的花朵，JOI 实验室提出了 $(Q+1)$ 个基因序列，它们从 $0$ 到 $Q$ 编号，并给了你一个描述这些候选基因序列的表。这个表包含一个字符串 $T_0$ 和整数 $L_j,R_j$ 和字符 $C_j$（这里 $1\le j\le Q$）。候选基因序列按如下规则给出。

• 候选基因序列 $0$ 是 $T_0$。
• 候选基因序列 $j\ (1\le j\le Q)$ 是把候选基因序列 $j-1$ 中从第 $L_j$ 到第 $R_j$ 个位置的字符全部替换为 $C_j$ 得到的。

给定整数 $N$ 和初始三朵花的基因序列，描述候选基因序列的表，你需要写一个程序确定对于每一个候选基因序列，是否可以通过初始三朵花杂交零次及以上获得。

输入格式

第一行一个正整数 $N$。

接下来三行，每行一个长度为 $N$ 的字符串，分别为 $S_A,S_B,S_C$。

接下来一行一个正整数 $Q$。

接下来一行一个长为 $N$ 的字符串 $T_0$。

接下来 $Q$ 行，每行两个整数和一个字符 $L_j,R_j,C_j$。

输出格式

输出 $(Q+1)$ 行到标准输出。对于第 $(j+1)\ (0\le j\le Q)$ 行，如果可以通过通过初始三朵花杂交零次及以上获得候选基因序列 $j$，则输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

Yes
No
Yes
Yes

3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

No
No
Yes

数据范围与提示

对于全部数据，满足：

• $1\le N\le 2\times 10^5$
• $S_A,S_B,S_C,T_0$ 的长度均为 $N$，并且只包含 $\texttt{J, O, I}$
• $1\le Q\le 2\times 10^5$
• $1\le L_j\le R_j\le N\ (1\le j\le Q)$
• $C_j\ (1\le j\le Q)$ 是 $\texttt{J, O, I}$ 中的一个

详细子任务附加条件及分值如下表所示。

子任务编号	附加限制	分值
$1$	$S_A=S_B=S_C,N\le 100$	$3$
$2$	$S_A=S_B=S_C$	$23$
$3$	$N\le 100$
$4$	无附加限制	$51$