题目描述

译自 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$ 如下表所示：

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

为了获得更多好看的花朵，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}$。

样例 1

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

Yes
No
Yes
Yes

初始的三个基因序列是 $\texttt{JOJO}$，$\texttt{JJOI}$ 和 $\texttt{OJOO}$。下面是通过杂交获得的新品种花朵。

1. $T_0$ 是 $\texttt{IJOJ}$。因为通过杂交 $\texttt{JJOI}$ 和 $\texttt{OJOO}$ 可以获得，因此输出 $\texttt{Yes}$。
2. $T_1$ 是 $\texttt{OOOO}$。因为无法通过杂交初始花朵有限次获得这个基因序列，因此输出 $\texttt{No}$。
3. $T_2$ 是 $\texttt{OJOO}$。因为初始你就有这种花，不需要杂交，因此输出 $\texttt{Yes}$。
4. $T_3$ 是 $\texttt{OIII}$。你可以通过杂交 $\texttt{JJOI}$ 和 $\texttt{OJOO}$ 获得 $\texttt{IJOJ}$，然后杂交 $\texttt{JOJO}$ 和 $\texttt{IJOJ}$ 就可以获得 $\texttt{OIII}$ 了，因此输出 $\texttt{Yes}$。

这组样例输入满足子任务 $3,4$ 的限制。

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

No
No
Yes

初始三朵花的基因序列只是 $\texttt{JOI}$。你只能通过杂交获得 $\texttt{JOI}$ 一种基因序列。

1. $T_0$ 是 $\texttt{OJI}$。因为无法通过杂交初始花朵有限次获得这个基因序列，因此输出 $\texttt{No}$。
2. $T_1$ 是 $\texttt{OOI}$。因为无法通过杂交初始花朵有限次获得这个基因序列，因此输出 $\texttt{No}$。
3. $T_2$ 是 $\texttt{JOI}$。你可以获得这种花朵，因此输出 $\texttt{Yes}$。

这组样例满足子任务 $1,2,3,4$ 的限制。

数据范围与提示

对于全部数据，满足：

• $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}$ 中的一个

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