The Canadian Construction Crew (CCC) is working on a new project! They have been tasked with paving the roads in a city. The road network can be modelled by a graph with $N$ vertices and some number of edges, with the vertices representing intersections, and the roads representing edges. Over $Q$ days, they will be given an additional requirement, specifying that a new road is to be paved between intersections $a_i$ and $b_i$, which requires their road paving machine to pave the road exactly $x_i$ times, no more, no less. Unfortunately, their road paving machine does not have an off switch and will pave every road that it travels on. The road paving machine must start and end at any intersection (possibly two different intersections) and cannot be moved to a different intersection without paving the roads in between the intersections. The road paving machine may decide to move back and forth on the same road until it is paved exactly the correct number of times. After each day, can you determine if there is a way to satisfy each of the requirements up to and including that day? Note that the road paving machine does not actually pave the roads at the end of each day. You are simply tasked with determining whether it is possible to pave the roads.

There may be multiple roads between two intersections, but there will not be a road between an intersection and itself.

Constraints

For this question, Python users are recommended to use PyPy over CPython.

For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

$2\le N\le 100000$
$1\le Q\le 300000$
$1\le a_i,b_i\le N$
$a_i\ne b_i$
$1\le x_i\le 1000$

Subtask 1 [10%]

$2\le N\le 3$
$1\le Q\le 3$

Subtask 2 [40%]

$2\le N\le 1000$
$1\le Q\le 3000$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line of input contains $2$ integers, $N$ and $Q$, representing the number of intersections in the city, and the number of days where requirements will be given.

The next $Q$ lines describe the requirements. Each line contains $3$ integers, $a_i$, $b_i$, $x_i$, indicating that on the $i^{th}$ day, a new road is required to be paved exactly $x_i$ times between intersections $a_i$, and $b_i$.

Output Specification

Output $Q$ lines. On the $i^{th}$ line, output YES if it is possible to use the road paver machine to satisfy all requirements up to and including the $i^{th}$ day. Otherwise, output NO.

Sample Input 1

2 2
1 2 2
2 1 1

Sample Output 1

YES
YES

Sample Explanation 1

On the first day, the road paving machine can take the path $1\to 2\to 1$.

On the second day, the road paving machine can take the path $2\to 1\to 2\to 1$.

Sample Input 2

4 4
1 2 1
4 3 2
4 2 1
2 3 2

Sample Output 2

YES
NO
YES
YES

Sample Explanation 2

On the first day, the road paving machine can take the path $1\to 2$.

On the second day, the road paving machine cannot take any path to pave both roads.

On the third day, the road paving machine can take the path $1\to 2\to 4\to 3\to 4$.

On the fourth day, the road paving machine can take the path $1\to 2\to 3\to 4\to 2\to 3\to 4$.