- Time limit: 1.00 s
- Memory limit: 512 MB
There are always four points with fixed coordinates: $(0,0)$ and $(k,0)$, which are blue, and $(0,k)$ and $(k,k)$, which are red. The other points may have any coordinates and colors, but there are never three points on the same line.
Your task is to add $n-2$ line segments, each of which connects two points of the same color, in such a way that all blue and red points belong to the same component, and no two line segments intersect.
Input
The first input line has two integers $n$ and $k$: the number of points and the coordinate upper bound.
After this, there are $n$ lines that describe the points. Each line has three integers $x$, $y$ and $c$: a point is located at $(x,y)$ and its color is blue ($c=1$) or red ($c=2$).
Output
Print $n-2$ lines that describe the connections. Each line must have four integers $x_1$, $y_1$, $x_2$ and $y_2$: the points $(x_1,y_1)$ and $(x_2,y_2)$ are connected.
You can print any valid solution, and it can be proven that there is always a solution.
Constraints
- $4 \le n \le 1000$
- $1 \le k \le 10^9$
Input:
8 6
0 0 1
0 6 2
1 4 1
3 4 2
4 1 1
4 5 1
6 0 1
6 6 2
Output:
0 0 1 4
0 0 6 0
0 6 6 6
1 4 4 5
6 0 4 1
6 6 3 4
The following figure corresponds to this example: