Migrated from Lutece 2976 A very very easy problem of bracket sequences

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bracket sequences are perfect examples of graceful balancing. Here we talk about bracket sequence consisting of '(' and ')'. For example, "(())", "()(())" are valid balanced bracket sequence.

More formally, a bracket sequence is valid if and only if it can be constructed by the following rules:

"()" is a valid bracket sequence. If $A$ is a valid bracket sequence, then $(A)$, i.e., adding a left bracket before and a right bracket after, forms a valid bracket sequence. If $A, B$ are valid bracket sequences, then $AB$, i.e., concatenating them, forms a valid bracket sequence. Today maco is playing a game with you. She has a valid bracket sequence $S$ with length $n$, and you can ask her questions in the form "What is the difference between the numbers of left and right brackets in the substring of $S$ from the $l$-th character to the $r$-th character?", and then maco will tell you the answer.

You want to determine the bracket sequence using the above method. After playing for a while, however, maco escaped and went to grab some sleep.

You want to retrieve a possible valid bracket sequence from already known queries. You may also find contradictions in the queries since maco was sleepy, in which case you should report no solution.

Input

The first line contains two integers $n, q\,$, denoting the length of the bracket sequence and the number of known queries.

In the following $q$ lines, the $i$-th line contains three integers $l_i, r_i, c_i\,$, denoting the $i$-th query ranges $q_i=[l_i, r_i]$, and the answer to the query is $c_i$, which is the number of the left brackets subtracts the number of right brackets in the interval.

It's guaranteed that $n$ is even, and the queried intervals are pairwise different.

Output

If there's no valid solution, print "NO".

Otherwise, print "YES"

Samples

4 1
1 2 0

YES

4 1
1 2 2

YES

2 2
1 1 1
2 2 -1

YES

2 1
1 1 2

NO

4 0

YES

Constraints

$2 \leq n \leq 3000$ $0 \leq q \leq \min ({n + 1\choose 2}, 5\times 10^5)$ $1 \leq l_i \leq r_i \leq n$ $\, -n \leq c_i \leq n$

Note

To help you better understand the meaning of the problem, maco wrote many samples and provided explanations for them.

The valid bracket sequence for the first example can be: $()()$, so the answer is YES.

The valid bracket sequence for the second example can be: $(())$, so the answer is YES.

The valid bracket sequence for the third example can be: $()$, so the answer is YES.

The fourth sample does not have a valid bracket sequence, so the answer is NO.

The valid bracket sequence for the fifth example can be: $(())$, so the answer is YES.

tips: Do not try any random algorithms, they will definitely fail, because maco has created very strong data. If you cannot pass using traditional algorithms, please consider which operations are unnecessary to achieve better complexity.