P7803 [JOI Open 2021] 杂交 / Crossing

**警告：滥用本题评测将被封号。**

你的资源库里有 $3$ 个长度为 $N$ 的只由 `J`，`O`，`I` 组成的序列 $S_A,S_B,S_C$，你可以进行 C 操作（全名为 Cross 操作，简写为 C 操作），每一次 C 操作你可以在资源库里选择两个字符串 $C_1,C_2$，C 操作后产生的字符串为 $C_3$，则对于任意 $i \in [1,N]$，设这三个字符串第 $i$ 个位置上的字符分别为 $c_1,c_2,c_3$，有： |$c_1$|$c_2$|$c_3$| |:-:|:-:|:-:| |J|J|J| |J|O|I| |J|I|O| |O|J|I| |O|O|O| |O|I|J| |I|J|O| |I|O|J| |I|I|I| 上面这个表格的意思是 $c_1,c_2$ 为对应字符时，$c_3$ 也应该是对应的字符。 进行 C 操作后将会把产生的字符串放入资源库。 你被给定了一个长度为 $N$ 的只由 `J`，`O`，`I` 组成的字符串 $T_0$，和 $Q$ 个整数 $L_j,R_j$ 和 $Q$ 个字符 $C_j$，由这些形成 $Q$ 个长度为 $N$ 的字符串 $T_j$，规则为： > $T_j$ 是由 $T_{j-1}$ 的第 $L_j$ 个字符到第 $R_j$ 个字符都替换成 $C_j$ 得到的。 求对于每一个字符串（包括 $T_0$），是否能由给定的资源库进行一次或多次 C 操作得来。如果该字符串与资源库的其中一个字符串一模一样，也可以称“进行 C 操作得来”，详细内容请看样例 1 的 $T_2$。 第 $j$ 个字符串进行 C 操作时放入资源库的字符串将会在对第 $j+1$ 个字符串判断时清空。

第一行一个整数 $N$ 代表字符串的长度。 接下来 $3$ 行 $S_A,S_B,S_C$ 代表给定的资源库里的字符串。 第五行一个整数 $Q$ 代表给定的字符串个数。 第六行一个字符串 $T_0$，意义如题面所述。 接下来 $Q$ 行每行两个整数和一个字符 $L_j,R_j,C_j$，意义如题面所述。

$Q+1$ 行每行一个字符串 `Yes` 或 `No`，第 $j$ 行代表第 $T_{j-1}$ 个字符串是否可以由初始资源库得来。

#### 样例 1 解释 - $T_0$ 可以由 `JJOI` 和 `OJOO` 经过 C 操作而来； - $T_1$ 为 `OOOO`，无法从资源库经过 C 操作而来； - $T_2$ 为 `OJOO`，资源库中有 `OJOO`，故可以； - $T_3$ 为 `OIII`： 1. 由 `JJOI` 和 `OJOO` 经过 C 操作产生 `IJOJ`； 2. 由 `JOJO` 和 `IJOJ` 经过 C 操作产生 `OIII`。 #### 样例 2 解释 - $T_0$ 无法从资源库经过 C 操作而来； - $T_1$ 为 `OOI`，无法从资源库经过 C 操作而来； - $T_2$ 为 `JOI`，资源库中有 `JOI`，故可以。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（3 pts）：$S_A=S_B=S_C$，$N \le 100$； - Subtask 2（23 pts）：$S_A=S_B=S_C$； - Subtask 3（23 pts）：$N \le 100$； - Subtask 4（51 pts）：无特殊限制。 对于 $100\%$ 的数据： - $1 \le N \le 2 \times 10^5$； - $S_A,S_B,S_C$ 是只包含 `J`，`O`，`I` 的长度为 $N$ 的字符串； - $1 \le Q \le 2 \times 10^5$； - $T_0$ 是只包含 `J`，`O`，`I` 的长度为 $N$ 的字符串； - $1 \le L_j \le R_j \le N$； - $C_j \in \{$`J`，`O`，`I`$\}$。 #### 说明 翻译自 [JOI 2020 / 2021 Open Contest A Crossing](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2021/crossing/2021-open-crossing-statement-en.pdf)。