You are given a set of n distinct points in the plane. Each point has integer coordinates between 0 \dots k, and is either blue or red.

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

Example

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: