题目描述

译自 COI $2021$ T$3$「Izvanzemaljci」

在二维平面上有 $N$ 个整点 $(x_i,y_i)$，请找出 $K$ 个正方形，使得所有整点在正方形内或在正方形上。这些正方形两两之间不能有公共部分，如有多解，求出在所有构造方案中面积最大的正方形面积最小的那一种，如果还有多解，输出任意一组即可。

输入格式

第一行为两个整数 $N$，$K$。

接下来 $N$ 行，一行两个整数 $x_i$，$y_i$。

输出格式

共 $K$ 行，每行三个整数 $a_i$，$b_i$，$l_i$，表示有一个左下角为 $(a_i,b_i)$，边长为 $l_i$ 的正方形。

您需要保证 $0 \le |a_i|, |b_i| \le 3 \times 10^9$，$1 \le l_i \le 2 \times 10^9$。

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

1 1 4
5 7 3

数据规模与约定

对于全部数据，有 $1 \le N \le 10^5$，$1 \le K \le 3$，$0 \le |x_i|,|y_i| \le 10^9$。