Two Dots

"Only 1% can solve this problem!!!"

One day, Yunee saw an advertisement for the game named "Two Dots". The goal of this game is to connect all pairs of points with the same colors.

The rules are as follows. The game area is a square of size $L\times L$. $N$ points are on the square, some completely inside and others on the boundary. They are divided into $N/2$ pairs by their colors. You can connect a pair of points by drawing a curved line between them. The lines must lie completely inside the square and must never cross each other.

Yunee found that the problem in the advertisement can never be solved. Yunee is angry about this and plans to report the ad as false by proving that the problem cannot be solved. If the problem cannot be solved, then only 0% can solve this problem!!!

Write a program that determines whether the given problem can be solved.

The first line contains an integer $L$ $(1\leq L \leq 100{,}000)$ and an even integer $N$ $(2\leq N\leq \min\{300{,}000, (L+1)^2\})$. $L$ is the side length of the game area and $N$ is the number of points. The four vertices of the game area are $(0, 0)$, $(L, 0)$, $(L, L)$, and $(0, L)$.

The next $N$ lines describe the points. The $i$-th line contains the coordinates $x, y$ and the color $c$ of the $i$-th point $(0 \leq x, y \leq L, 1 \leq c \leq N/2)$. The coordinates of the $N$ points are distinct. There are exactly two points with each color $c=1,\cdots,N/2$.

Output 1% if the problem can be solved, and 0% otherwise.