P8389 [COI 2021] Izvanzemaljci

**Translated from [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T3 "[Izvanzemaljci](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)".** 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.

The first line contains two integers $N$ and $K$. The next $N$ lines each contain two integers $x_i$ and $y_i$.

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$.

**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$. | Subtask | Constraints | Score | | :-----: | :------------------: | :---: | | $1$ | $K = 1$ | $5$ | | $2$ | $K = 2$ | $21$ | | $3$ | $N \le 12$, $K = 3$ | $12$ | | $4$ | $N \le 10^3$, $K = 3$ | $30$ | | $5$ | $K = 3$ | $32$ | Translated by ChatGPT 5