Cross Operation String Generation

You are given a resource library containing three strings \(S_A\), \(S_B\) and \(S_C\) of length \(N\). Each string consists only of the characters J, O, and I. You can perform an operation called a Cross Operation (C operation). In each C operation, you choose any two strings \(C_1\) and \(C_2\) from the resource library and generate a new string \(C_3\) of length \(N\). For every position \(i\) (\(1 \le i \le N\)), let \(c_1, c_2, c_3\) be the characters at position \(i\) in \(C_1, C_2, C_3\) respectively. They must satisfy the following rule:

[ \begin{array}{|c|c|c|} \hline c_1 & c_2 & c_3 \ \hline 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 \ \hline \end{array} ]

This table is interpreted as follows: When the two input characters are equal then the result is the same character; otherwise, if they are different then the result is the unique character from \(\{J, O, I\}\) that is not among the two.

After a C operation, the generated string \(C_3\) is added to the resource library. Initially, the resource library contains only the three given strings \(S_A, S_B, S_C\).

You are also given a string \(T_0\) (of length \(N\) and composed only of J, O, and I) and \(Q\) operations. For each \(j\) from \(1\) to \(Q\) an update is specified by two integers \(L_j, R_j\) and a character \(C_j\). The string \(T_j\) is obtained from \(T_{j-1}\) by replacing every character in the range \([L_j, R_j]\) (1-indexed) with \(C_j\).

For each string \(T_i\) (including \(T_0\)), determine whether it can be generated from the resource library via one or more C operations. Note that if \(T_i\) is exactly identical to one of the strings in the resource library (i.e. one of \(S_A, S_B, S_C\)), it is also considered as having been generated by C operations.

Important: When processing the \(j\)th string (\(T_j\)), any strings produced by C operations during that check will be cleared before checking the string \(T_{j+1}\); in other words, for every string the only available strings are the original resource library (\(S_A, S_B, S_C\)).

Observation

Observe that each C operation is applied independently on each position. Let \(x_i, y_i, z_i\) be the characters at position \(i\) of two chosen strings and the result respectively. The operation is defined as follows: \[ f(x, y)=\begin{cases} x, &\text{if } x=y,\\ \text{the unique element in }\{J,O,I\}\setminus\{x,y\}, &\text{if } x\neq y. \end{cases} \] Since the operation is performed independently on each position, the generation of the target string is equivalent to, for every position \(i\) (\(1 \le i \le N\)), checking whether the target character \(T(i)\) can be produced from the set \(\{S_A(i), S_B(i), S_C(i)\}\) under the binary operation \(f\).

Notice that:

• If all three characters at a position are the same (say, all are \(X\)), then the only possible outcome via any number of operations is \(X\).
• If at least two different characters appear at position \(i\), then by applying the operation on those two different characters you obtain the third character. Thus the closure is \(\{J, O, I\}\), and any character is possible at that position.

Thus, a string \(T\) is generatable if and only if for every position \(i\):

• If \(S_A(i)=S_B(i)=S_C(i)=X\) then \(T(i)\) must be \(X\);
• If at least two distinct characters occur among \(S_A(i),S_B(i),S_C(i)\), then any character is allowed.

Using this observation, determine for each \(T_0, T_1, \dots, T_Q\) whether it can be generated.

inputFormat

The input consists of several lines:

• The first line contains two integers \(N\) and \(Q\) \((1 \le N, Q \le \text{limits})\).
• The next three lines each contain a string of length \(N\): \(S_A\), \(S_B\), and \(S_C\), consisting only of the characters J, O, and I.
• The next line contains the string \(T_0\) of length \(N\), consisting of the characters J, O, and I.
• The following \(Q\) lines each contain two integers and a character: \(L_j\), \(R_j\) and \(C_j\) \((1 \le L_j \le R_j \le N,\; C_j \in \{J, O, I\})\). Each such line indicates that to obtain \(T_j\) from \(T_{j-1}\), you should replace all characters from position \(L_j\) to \(R_j\) (inclusive) with the character \(C_j\).

outputFormat

Output \(Q+1\) lines. The first line corresponds to \(T_0\) and the \(i\)th of the subsequent \(Q\) lines corresponds to \(T_i\). For each string, output Yes if the string can be generated from the resource library via one or more C operations, or No otherwise.

sample

5 2
JJJJJ
OOOOO
IIIII
JOIJO
2 4 J
5 5 I

Yes
Yes
Yes

</p>