Magic Circle Spell Constraints

The magic circle consists of \(N\) hubs. Each hub can be assigned one of the five elements: Metal, Wood, Water, Fire, and Earth. These elements interact with each other via two kinds of relationships:

• Generation (\(\text{sheng}\)): An element \(x\) generates the next element in the cycle. In our formulation, if a hub \(u\) has value \(a_u\) then a spell of type sheng on an ordered pair \((u,v)\) requires \[ a_v \equiv a_u + 1 \pmod{5} \] (i.e. the element at hub \(v\) is determined by adding 1 modulo 5 to the element at hub \(u\)).
• Control (\(\text{ke}\)): An element \(x\) controls the element that is 2 ahead in the cycle. Formally, a spell of type ke on \((u,v)\) requires \[ a_v \equiv a_u + 2 \pmod{5}. \]

The system starts with no spells. Then a sequence of operations is performed. In each operation, a new version of the magic circle is created based on a previous version. Each operation is given with a parent version index p; the new operation is applied on the magic circle state as it was immediately after operation p (with p = 0 representing the initial empty state).

There are two kinds of operations:

1. Add operation: p add u v r — based on version p, add a spell requiring that hub u and hub v satisfy the relationship specified by r (which is either sheng or ke). You may assume that when sheng is specified, the relation constraint is \(a_v \equiv a_u + 1 \pmod{5}\), and when ke is specified, it is \(a_v \equiv a_u + 2 \pmod{5}\).
2. Delete operation: p del k — based on version p, delete the spell that was added in the k-th operation (which is guaranteed to be an add‐operation that exists in that version).

After each operation, determine whether there exists an assignment of elements (each represented by an integer modulo 5, i.e. from \(0\) to \(4\)) to the hubs satisfying all spell constraints in that version.

Input/Output Example:

Example: 
Input:
3 5
0 add 1 2 sheng
1 add 2 3 ke
2 add 1 3 sheng
2 del 2
4 add 2 3 sheng

Output:
YES
YES
NO
YES
YES

Note: In the above sample, the first line 3 5 indicates there are 3 hubs and 5 operations. The answers for operations 1 to 5 are printed in order on separate lines.

inputFormat

The first line contains two integers \(N\) and \(Q\) — the number of hubs and the number of operations respectively. The next \(Q\) lines each represent an operation. Each operation has one of the following formats:

• p add u v r: Based on version p (\(0 \le p < \) current operation index), add a spell between hubs u and v. The relation r is either sheng (meaning \(a_v \equiv a_u + 1 \pmod{5}\)) or ke (meaning \(a_v \equiv a_u + 2 \pmod{5}\)).
• p del k: Based on version p, delete the spell that was added in the k-th operation.

Operations are numbered from 1 to \(Q\). Note that version 0 is the initial state with no spells.

outputFormat

After each operation, output a single line containing YES if there exists an assignment of elements to the hubs satisfying all spells in the current version, or NO otherwise.

sample

3 5
0 add 1 2 sheng
1 add 2 3 ke
2 add 1 3 sheng
2 del 2
4 add 2 3 sheng

YES
YES
NO
YES
YES

</p>