Задан неориентированный граф. Каждому ребру (u, v) графа приписана некоторая бинарная операция и некоторое число c. Число c может принимать значения 0 или 1, а операции могут быть слудющими: логическое умножение (AND), логическое сложение (OR) и сложение по модулю два (XOR). Необходимо выяснить, можно ли присвоить каждой вершине u число 0 или 1 (обозначим это значение как A(u)) таким образом, чтобы для каждого ребра (u, v) результат приписанной ему бинарной операции над величинами A(u) и A(v) был равен написанному на нем числу c.

Правила вычисления указанных операций:

• (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

Входные данные

В первой строке записано количество вершин n и ребер m в графе (1 ≤ n ≤ 1000, 0 ≤ m ≤ 300000). Следующие m строк содержат описание ребер. Ребро задается номерами соединяемых вершин ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), числом ci и названием операции (AND, OR или XOR). Никакое ребро не задается более одного раза.

Выходные данные

Выведите "YES", если можно найти требуемый набор значений для вершин, и "NO" в противном случае.