题目描述

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

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

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

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

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

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

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

$c_1$	$\texttt{J}$			$\texttt{O}$			$\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{I}$	$\texttt{O}$	$\texttt{I}$		$\texttt{J}$	$\texttt{O}$	$\texttt{J}$

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

为了获得更多好看的花朵，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$，则输出 Yes，否则输出 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}$。下面是通过杂交获得的新品种花朵：

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

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

---

样例 2

输入

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

输出

No
No
Yes

解释

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

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

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

---

数据范围与提示

对于全部数据，满足：

• $1 \le N \le 2 \times 10^5$
• $S_A$, $S_B$, $S_C$, $T_0$ 的长度均为 $N$，并且只包含 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)$ 是 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