Problem Description

Translated from COI 2021 T3 "Izvanzemaljci"

In a two-dimensional plane, there are $N$ integer points $(x_i, y_i)$. Please find $K$ disjoint squares such that all integer points are inside or on the boundary of these squares. If there are multiple solutions, find the one with the smallest possible area of the largest square. If there are still multiple solutions, output any one of them.

Two squares are considered disjoint if they do not share any edges or vertices, 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 containing three integers $a_i$, $b_i$, and $l_i$, representing a square with its bottom-left corner at $(a_i, b_i)$ and a side length of $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 Input and Output

Sample Input #1

3 1
1 1
1 3
2 2

Sample Output #1

0 1 2

Sample Input #2

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

Sample Output #2

1 1 4
5 7 3

Sample Input #3

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

Sample Output #3

1 1 2
5 5 2
5 10 1

Notes

Sample Explanation

For Sample #2:

For Sample #3:

Data Range

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

见题面 Input 部分

见题面 Output 部分