E. Stacked Pearls
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Naseem owns a jewelry shop and likes to show his most beautiful pearls at the storefront on a $$$n \times n$$$ board. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each pearl has its own size. Naseem has an infinite amount of pearls of each size

Naseem thinks that the board looks good if he can fill the board with pearls so that choosing any two pearls on adjacent cells in the board, the sum of their sizes would be the same for any other pair of pearls on adjacent cells. Two cells are considered adjacent if they share a side

Initially, the board is empty. At each second, Naseem will add a pearl to an empty cell, remove a pearl from a cell or replace a pearl on a cell. More formally, Naseem will choose a cell on the $$$x_{th}$$$ row and $$$y_{th}$$$ column and a pearl of size $$$v$$$, remove the pearl on the cell if it exists, and put a pearl of size $$$v$$$ on the cell if $$$v \ne 0$$$. Otherwise, if $$$v = 0$$$ he leaves the cell empty.

Naseem wants to know if the board looks good after each second. He is a busy guy because he keeps counting the money he gets from the shop, so can he help him doing so?

Input

The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 10^5)$$$. The size of the board and the number of seconds Naseem will make changes on the board, respectively.

The next $$$q$$$ lines of the input each contains $$$3$$$ integer numbers $$$x$$$, $$$y$$$ and $$$v$$$ ($$$1 \le x, y \le n, 0 \le v \le 10^9$$$), where $$$x$$$ and $$$y$$$ are the coordinates of the cell on the board and $$$v$$$ is the size of the pearl he will put on the cell. If $$$v = 0$$$, then he will leave the cell empty

Output

For each second, print YES if the board is good. Otherwise, print NO. Note that the case of the each letter

You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.

Examples
Input
3 4
1 1 1
2 3 4
1 2 3
1 2 1
Output
YES
YES
NO
NO
Input
3 5
2 1 1
1 3 4
2 1 1
2 2 3
2 2 0
Output
YES
YES
YES
NO
YES