Graph of operations
The undirected graph is given. For each edge (u, v) some binary operation and the value of c are given. The number c can take the values of 0 or 1, and the operation can be one of the next: the logical multiplication (AND), the logical addition (OR) and the addition by modulo two (XOR). You need, if its possible, to assign to each vertex u the value of 0 or 1 (lets denote this value as A(u)) in a such way, that for every edge (u, v) the result of assigned to it binary operation on values A(u) and A(v) equals to the number c, written on this edge.
The rules of operations are next:
(0 AND 1) = (1 AND 0) = (0 AND 0) = 0, (1 AND 1) = 1
(0 OR 1) = (1 OR 0) = (1 OR 1) = 1, (0 OR 0) = 0
(0 XOR 1) = (1 XOR 0) = 1, (1 XOR 1) = (0 XOR 0) = 0
Input
The first line contains the number of vertices n and edges m in a graph (1 ≤ n ≤ 1000, 0 ≤ m ≤ 300000). The next m lines describe the edges. Each edge is given by the numbers of connected vertices u[i], v[i] (1 ≤ u[i], v[i] ≤ n, u[i] ≠ v[i]), the value of c[i] and the name of operation (AND, OR or XOR). No edge is given in a list more than one time.
Output
Print "YES" if you can find the desired set of values for vertices, and "NO" otherwise.