P7803 [JOI Open 2021] Hybrid / Crossing

**Warning: Abusing the judging system for this problem will result in your account being banned.**

In your repository, there are $3$ sequences $S_A, S_B, S_C$ of length $N$, consisting only of `J`, `O`, and `I`. You may perform a C operation (full name: Cross operation, abbreviated as C operation). In each C operation, you choose two strings $C_1, C_2$ from the repository. The string produced after the C operation is $C_3$. For any $i \in [1, N]$, let the characters at position $i$ in these three strings be $c_1, c_2, c_3$, respectively, then: |$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| The meaning of the table above is: when $c_1, c_2$ are the corresponding characters, then $c_3$ must be the corresponding character as well. After performing a C operation, the produced string will be added into the repository. You are given a string $T_0$ of length $N$ consisting only of `J`, `O`, and `I`, and $Q$ integers $L_j, R_j$ and $Q$ characters $C_j$. These define $Q$ strings $T_j$ of length $N$ by the following rule: > $T_j$ is obtained from $T_{j-1}$ by replacing the characters from the $L_j$-th to the $R_j$-th position with $C_j$. For each string (including $T_0$), determine whether it can be obtained from the given initial repository by performing the C operation one or more times. If the string is exactly the same as one of the strings already in the repository, it is also considered “obtainable by performing C operations”; see $T_2$ in Sample 1 for details. Any strings added to the repository while processing the $j$-th string will be cleared before determining the $(j+1)$-th string.

The first line contains an integer $N$, the length of the strings. The next $3$ lines contain $S_A, S_B, S_C$, the strings in the initial repository. The fifth line contains an integer $Q$, the number of given strings. The sixth line contains a string $T_0$, as described above. The next $Q$ lines each contain two integers and one character $L_j, R_j, C_j$, as described above.

Output $Q+1$ lines, each being `Yes` or `No`. The $j$-th line indicates whether $T_{j-1}$ can be obtained from the initial repository.

#### Explanation of Sample 1 - $T_0$ can be obtained by performing a C operation on `JJOI` and `OJOO`. - $T_1$ is `OOOO`, and cannot be obtained from the repository by performing C operations. - $T_2$ is `OJOO`. Since `OJOO` is in the repository, it can be obtained. - $T_3$ is `OIII`: 1. Perform a C operation on `JJOI` and `OJOO` to produce `IJOJ`. 2. Perform a C operation on `JOJO` and `IJOJ` to produce `OIII`. #### Explanation of Sample 2 - $T_0$ cannot be obtained from the repository by performing C operations. - $T_1$ is `OOI`, and cannot be obtained from the repository by performing C operations. - $T_2$ is `JOI`. Since `JOI` is in the repository, it can be obtained. #### Constraints and Notes **This problem uses bundled testdata.** - 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): No special constraints. For $100\%$ of the testdata: - $1 \le N \le 2 \times 10^5$. - $S_A, S_B, S_C$ are strings of length $N$ consisting only of `J`, `O`, and `I`. - $1 \le Q \le 2 \times 10^5$. - $T_0$ is a string of length $N$ consisting only of `J`, `O`, and `I`. - $1 \le L_j \le R_j \le N$. - $C_j \in \{$`J`, `O`, `I`$\}$. #### Note Translated from [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). Translated by ChatGPT 5