众所周知，一群俄罗斯科学家在 2016 年发现了一个外星文明。他们的卫星成功捕获了 $K$ 张高分辨率的正方形图像，这永远改变了人类历史的进程。如今，五年过去了，世界上几乎每个地方都有自己的太空计划来研究外星人。遗憾的是，在克罗地亚，我们决定解决一些更重要的问题，这使得科学研究落在了少数爱好者的肩上。Vladimir 就是其中之一。

不幸的是，Vladimir 没有足够的资源购买航天器或昂贵的望远镜，但他买得起热气球和一部手机。他决定不在外星文明上浪费时间，而是寻找他家乡星球上存在智慧生命的迹象。从热气球上往下看，Vladimir 注意到了 $N$ 个人。他决定拍摄 $K$ 张平均分辨率的正方形图像，使得每个人都恰好出现在一张图像中。此外，他不希望任何细节出现在多于一张图像中。更重要的是，他认为让某张图片中可见的最大面积尽可能小是很重要的。

Vladimir 不是一个出色的程序员，所以他向你发送了一份正式规范，并等待你的帮助。

题目描述

在坐标系中有 $N$ 个整点。你需要找到恰好 $K$ 个不相交的正方形，覆盖所有 $N$ 个点。正方形的边必须平行于坐标轴，且其顶点应位于整数坐标上。需要使最大正方形的面积尽可能小。

我们称一个正方形覆盖了一个点，如果该点完全位于其内部，或位于其顶点或边上。如果两个正方形的边不相交也不接触，且其中任何一个正方形都没有完全包含在另一个正方形中，则称这两个正方形是不相交的。

输入格式

第一行包含整数 $N$ 和 $K$。

接下来的 $N$ 行中，第 $i$ 行包含整数 $x_i$ 和 $y_i$ ($0 \le |x_i|, |y_i| \le 10^9$)，表示第 $i$ 个点（人）的坐标。所有 $N$ 个点各不相同。

输出格式

输出 $K$ 行，每行包含三个整数 $x_i, y_i$ ($0 \le |x_i|, |y_i| \le 3 \cdot 10^9$) 和 $l_i$ ($1 \le l_i \le 2 \cdot 10^9$)，唯一确定第 $i$ 个正方形的位置，其中 $(x_i, y_i)$ 表示其左下角顶点，$l_i$ 表示其边长。

如果有多个正确的解，输出其中任意一个即可。

子任务

样例

输入 1

3 1
1 1
1 3
2 2

输出 1

1 1 2

输入 2

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

输出 2

1 1 4
5 7 3

输入 3

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

输出 3

1 1 2
5 5 2
5 10 1

说明

第二和第三个样例的解释：