Alien Squares

Given N integer points in the 2D plane, your task is to choose K non-intersecting axis‐aligned squares such that every point lies either inside or on the boundary of at least one square. Among all valid constructions, you must output one in which the area of the largest square is minimized. If there are multiple valid solutions, output any one of them.

Non-intersecting here means that any two squares should not have any edges that intersect or even touch. Moreover, it is not allowed that one square is completely contained within another.

inputFormat

The first line contains two integers N and K (1 ≤ K ≤ N ≤ 10⁵), representing the number of points and the number of squares respectively.

Each of the following N lines contains two integers x and y, denoting the coordinates of a point.

outputFormat

Output exactly K lines. On each line, print three integers: the x-coordinate and y-coordinate of the square's bottom-left corner, followed by its side length. The squares must be non-intersecting (they cannot even touch), and their union must cover all the given points.

sample

4 1
0 0
0 1
1 0
1 1

0 0 1