Problem Description

Translated from COI 2021 T3 "Izvanzemaljci".

There are $N$ integer points $(x_i, y_i)$ on a 2D plane. Find $K$ pairwise disjoint squares such that all integer points lie inside or on the boundary of the squares. If there are multiple solutions, choose the one that minimizes the area of the largest square among all valid constructions. If there are still multiple solutions, output any one of them.

Two squares are considered disjoint if their edges do not intersect or touch, and neither square is completely contained within the other.

Input Format

The first line contains two integers $N$ and $K$.

The next $N$ lines each contain two integers $x_i$ and $y_i$.

Output Format

Output $K$ lines. Each line contains three integers $a_i$, $b_i$, and $l_i$, indicating a square with lower-left corner $(a_i, b_i)$ and side length $l_i$.

You must ensure that $0 \le |a_i|, |b_i| \le 3 \times 10^9$ and $1 \le l_i \le 2 \times 10^9$.

3 1
1 1
1 3
2 2

0 1 2

5 2
1 3
3 1
5 5
5 10
7 7

1 1 4
5 7 3

5 3
1 3
3 1
5 5
5 10
7 7

1 1 2
5 5 2
5 10 1

Hint

Sample Explanation

Explanation for Sample #2:

Explanation for Sample #3:

Constraints

For all testdata, $1 \le N \le 10^5$, $1 \le K \le 3$, $0 \le |x_i|, |y_i| \le 10^9$.

Translated by ChatGPT 5