{"raw_statement":[{"iden":"statement","content":"**译自 [COI 2021](https://hsin.hr/coci/archive/2020_2021/) T3「[Izvanzemaljci](https://hsin.hr/coci/archive/2020_2021/olympiad_tasks.pdf)」**\n\n在二维平面上有 $N$ 个整点 $(x_i,y_i)$，请找出 $K$ 个不相交的正方形，使得所有整点在正方形内或在正方形上，如有多解，求出在所有构造方案中面积最大的正方形面积最小的那一种，如果还有多解，输出任意一组即可。\n\n两个正方形如果没有边相交或相碰，并且没有一个正方形完全被另一个正方形包含的情况，则这两个正方形不相交。"},{"iden":"input","content":"第一行为两个整数 $N$，$K$。\n\n接下来 $N$ 行，一行两个整数 $x_i$，$y_i$。"},{"iden":"output","content":"共 $K$ 行，每行三个整数 $a_i$，$b_i$，$l_i$，表示有一个左下角为 $(a_i,b_i)$，边长为 $l_i$ 的正方形。\n\n您需要保证 $0\\le |a_i|,|b_i|\\le 3\\times 10^9$，$1\\le l_i\\le 2\\times 10^9$。"},{"iden":"note","content":"【样例解释】\n\n样例 #2 解释：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/zatdwp0m.png)\n\n样例 #3 解释：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/u9roo5df.png)\n\n【数据范围】\n\n对于全部数据，有 $1\\le N\\le 10^5$，$1\\le K\\le 3$，$0\\le |x_i|,|y_i|\\le 10^9$。\n\n| Subtask |        限制        | 分数 |\n| :-----: | :----------------: | :--: |\n|   $1$   |       $K=1$        | $5$  |\n|   $2$   |       $K=2$        | $21$ |\n|   $3$   |  $N\\le 12$，$K=3$  | $12$ |\n|   $4$   | $N\\le 10^3$，$K=3$ | $30$ |\n|   $5$   |       $K=3$        | $32$ |"}],"translated_statement":null,"sample_group":[["3 1\n1 1\n1 3\n2 2","0 1 2"],["5 2\n1 3\n3 1\n5 5\n5 10\n7 7","1 1 4\n5 7 3"],["5 3\n1 3\n3 1\n5 5\n5 10\n7 7\n","1 1 2\n5 5 2\n5 10 1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}