Description

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:

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.

Input Format

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 Format

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.

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

Hint

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.

Translated by ChatGPT 5