题目描述

一款新的手机游戏在市场上流行起来。游戏开始时，屏幕上给出若干个点，玩家需要用若干个正方形覆盖这些点，并使得最大的正方形尽可能小。

所有正方形的边都必须与手机屏幕的边平行，并且正方形之间不能相交，也不能互相包含。

游戏一共有三个等级：

• 第 1 级：用 1 个正方形覆盖所有点；
• 第 2 级：用 2 个正方形覆盖所有点；
• 第 3 级：用 3 个正方形覆盖所有点。

Pesho 很快解决了第 1 级，但在后面的等级遇到了困难。请你编写程序 squares：给定 $N$ 个点和正方形数量 $K$，求出如何用 $K$ 个正方形覆盖所有点，使得这些正方形中最大的边长尽可能小。

我们把手机屏幕看作笛卡尔坐标系，所有给定点以及输出正方形的顶点都必须是整数坐标点。

输入格式

第一行输入两个正整数 $N,K$，分别表示点的数量和正方形的数量。

接下来 $N$ 行，每行输入两个整数 $x,y$，表示一个点的坐标。

输出格式

输出 $K$ 行。

第 $s$ 行输出三个整数 $x_s,y_s,l_s$，表示第 $s$ 个正方形的左下角坐标为 $(x_s,y_s)$，边长为 $l_s$。

如果存在多种最优方案，输出任意一种即可。

数据范围

• $1 \le N \le 10^5$；
• $1 \le K \le 3$；
• $-10^9 \le x,y \le 10^9$；
• $-3\times 10^9 \le x_s,y_s \le 3\times 10^9$；
• $1 \le l_s \le 2\times 10^9$。

子任务

一个子任务的分数仅在通过该子任务的全部测试点以及它依赖的子任务后获得。

样例 1

输入

3 1
1 1
1 3
2 2

输出

0 1 2

样例 2

输入

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

输出

1 1 4
5 7 3

样例 3

输入

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

输出

1 1 2
5 5 2
5 10 1