#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define int long long
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_hash{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
const int INF = 2e9 + 7;
struct Area{
int mxX, mnX, mxY, mnY;
Area(){
mxX = mxY = -INF;
mnX = mnY = INF;
}
Area(int a, int b, int c, int d){
mxX = a;
mnX = b;
mxY = c;
mnY = d;
}
Area(int x, int y){
mxX = mnX = x;
mxY = mnY = y;
}
};
Area merge(Area a, Area b){
return Area(max(a.mxX, b.mxX), min(a.mnX, b.mnX), max(a.mxY, b.mxY), min(a.mnY, b.mnY));
}
int sideLen(Area x){
return max({1LL, x.mxX - x.mnX, x.mxY - x.mnY});
}
bool comp(pii& x, pii& y){
if(x.se != y.se){
return x.se < y.se;
}
return x.fi < y.fi;
}
vector<Area> squares;
bool disjoint(Area a, Area b){
if(a.mxX < b.mnX || b.mxX < a.mnX || a.mxY < b.mnY || b.mxY < a.mnY){
return true;
}
return false;
}
bool validateAndCheckDisjoint(int L){
for(int i = 0; i < sz(squares); i++){
if(sideLen(squares[i]) > L){
return false;
}
for(int j = i + 1; j < sz(squares); j++){
if(!disjoint(squares[i], squares[j])){
return false;
}
}
}
for(int i = 0; i < sz(squares); i++){
int lx = squares[i].mxX - sideLen(squares[i]);
for(int j = 0; j < sz(squares); j++){
if(i != j && squares[j].mxX < squares[i].mnX){
int pre = squares[i].mnX;
squares[i].mnX = squares[j].mxX;
if(!disjoint(squares[i], squares[j])){
lx = max(lx, squares[j].mxX + 1);
}
squares[i].mnX = pre;
}
}
squares[i].mnX = lx;
}
for(int i = 0; i < sz(squares); i++){
int px = squares[i].mnX + sideLen(squares[i]);
for(int j = 0; j < sz(squares); j++){
if(i != j && squares[j].mnX > squares[i].mxX){
int pre = squares[i].mxX;
squares[i].mxX = squares[j].mnX;
if(!disjoint(squares[i], squares[j])){
px = min(px, squares[j].mnX - 1);
}
squares[i].mxX = pre;
}
}
squares[i].mxX = px;
}
for(int i = 0; i < sz(squares); i++){
int ly = squares[i].mxY - sideLen(squares[i]);
for(int j = 0; j < sz(squares); j++){
if(i != j && squares[j].mxY < squares[i].mnY){
int pre = squares[i].mnY;
squares[i].mnY = squares[j].mxY;
if(!disjoint(squares[i], squares[j])){
ly = max(ly, squares[j].mxY + 1);
}
squares[i].mnY = pre;
}
}
squares[i].mnY = ly;
}
for(int i = 0; i < sz(squares); i++){
int py = squares[i].mnY + sideLen(squares[i]);
for(int j = 0; j < sz(squares); j++){
if(i != j && squares[j].mnY > squares[i].mxY){
int pre = squares[i].mxY;
squares[i].mxY = squares[j].mnY;
if(!disjoint(squares[i], squares[j])){
py = min(py, squares[j].mnY - 1);
}
squares[i].mxY = pre;
}
}
squares[i].mxY = py;
}
for(int i = 0; i < sz(squares); i++){
if(squares[i].mxX - squares[i].mnX != squares[i].mxY - squares[i].mnY){
return false;
}
for(int j = i + 1; j < sz(squares); j++){
if(!disjoint(squares[i], squares[j])){
return false;
}
}
}
return true;
}
vector<pair<pii, int>> changeToSquares(){
vector<pair<pii, int>> res = {};
for(auto ele : squares){
res.pb(mp(mp(ele.mnX, ele.mnY), sideLen(ele)));
}
return res;
}
void display(Area x){
cerr << "------\n";
debug(x.mxX);
debug(x.mnX);
debug(x.mxY);
debug(x.mnY);
}
void solve(vector<pii> a, int n, int k, int L){
if(k == 1){
if(sz(a) == 0){
Area now = Area(INF, INF);
squares.pb(now);
return;
}
// debug(a);
Area now = Area(a[0].fi, a[0].se);
for(int i = 1; i < sz(a); i++){
now = merge(now, Area(a[i].fi, a[i].se));
}
// display(now);
squares.pb(now);
return;
}
if(k == 2){
if(sz(a) == 0){
Area now = Area(-INF, -INF);
squares.pb(now);
solve(a, sz(a), k - 1, L);
return;
}
// debug(a);
for(int xd = 0;xd < 2; xd++){
Area now = Area(a[0].fi, a[0].se);
vector<pii> na = {};
bool zle = false;
for(int i = 1; i < sz(a); i++){
Area nowe = merge(now, Area(a[i].fi, a[i].se));
if(sz(squares) && !disjoint(nowe, squares[0])){
na.pb(a[i]);
zle = true;
continue;
}
if(sideLen(merge(now, Area(a[i].fi, a[i].se))) <= L && !zle){
now = merge(now, Area(a[i].fi, a[i].se));
}else{
na.pb(a[i]);
zle = true;
}
}
// debug(na);
// display(now);
squares.pb(now);
solve(na, sz(na), k - 1, L);
if(validateAndCheckDisjoint(L)){
return;
}
if(xd){
break;
}
squares.pop_back();
squares.pop_back();
sort(all(a));
}
return;
}
//debug(a);
Area now = Area(a[0].fi, a[0].se);
vector<pii> na = {};
bool zle = false;
int i = 1;
while(i < sz(a)){
int pocz = i;
while(i + 1 < sz(a) && a[i + 1].se == a[pocz].se){
i++;
}
Area now2 = now;
for(int j = pocz; j <= i; j++){
now2 = merge(now2, Area(a[j].fi, a[j].se));
}
if(!zle && sideLen(now2) <= L){
now = now2;
}else{
zle = true;
for(int j = pocz; j <= i; j++){
na.pb(a[j]);
}
}
i++;
}
// display(now);
squares.pb(now);
solve(na, sz(na), k - 1, L);
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
cin >> n >> k;
//cout << n << ' ' << k << '\n';
vector<pii> a(n);
for(int i = 0; i < n; i++){
cin >> a[i].fi >> a[i].se;
// cout << a[i].fi << ' ' << a[i].se << '\n';
}
if(n < k){
sort(all(a));
if(n == 1){
vector<pair<pii, int>> res = {mp(a[0], 1)};
for(int j = 2; j <= k; j++){
int x = (j == 2 ? (int)1e9 : (int)-1e9);
res.pb(mp(mp(x, 0), 1));
}
for(auto ele : res){
cout << ele.fi.fi << ' ' << ele.fi.se << ' ' << ele.se << '\n';
}
}else if(n == 2){
vector<pair<pii, int>> res = {mp(mp(a[0].fi - 1, a[0].se - 1), 1), mp(a[1],1)};
if(k == 3){
res.pb(mp(mp(INF, INF), 1));
}
for(auto ele : res){
cout << ele.fi.fi << ' ' << ele.fi.se << ' ' << ele.se << '\n';
}
}
return 0;
}
vector<pii> pocz = a;
int l = 1;
int p = INF;
int mid;
vector<pair<pii, int>> res;
int best = 2 * INF;
int nbest;
while(l < p){
mid = (l + p) / 2;
//cerr << "MID: " << mid << '\n';
bool f = false;
for(int i1 = 0; i1 < 2; i1++){
for(int i2 = 0; i2 < 2; i2++){
if(f){
break;
}
squares.clear();
vector<pii> na = pocz;
nbest = 0;
if(i1 && !i2){
for(auto& ele : na){
swap(ele.fi, ele.se);
}
sort(all(na), comp);
solve(na, n, k, mid);
if(validateAndCheckDisjoint(mid)){
for(auto& ele : squares){
nbest = max(nbest, sideLen(ele));
swap(ele.mnX, ele.mnY);
swap(ele.mxX, ele.mxY);
}
if(nbest < best){
res = changeToSquares();
}
f = true;
}
}else if(i2 && !i1){
for(auto& ele : na){
ele.se = -ele.se;
}
sort(all(na), comp);
//cerr << "POCZĄTEK INTERESUJĄCEJ CZĘŚCI Z -y\n";
solve(na, n, k, mid);
if(validateAndCheckDisjoint(mid)){
for(auto& ele : squares){
int pre = ele.mnY;
ele.mnY = -ele.mxY;
ele.mxY = -pre;
nbest = max(nbest, sideLen(ele));
}
if(nbest < best){
res = changeToSquares();
}
f = true;
}
}else if(i2 && i1){
for(auto& ele : na){
swap(ele.fi, ele.se);
ele.se = -ele.se;
}
sort(all(na), comp);
solve(na, n, k, mid);
if(validateAndCheckDisjoint(mid)){
for(auto& ele : squares){
int pre = ele.mnY;
ele.mnY = -ele.mxY;
ele.mxY = -pre;
swap(ele.mnX, ele.mnY);
swap(ele.mxX, ele.mxY);
nbest = max(nbest, sideLen(ele));
}
if(nbest < best){
res = changeToSquares();
}
f = true;
}
}else{
sort(all(na), comp);
solve(na, n, k, mid);
if(validateAndCheckDisjoint(mid)){
for(auto& ele : squares){
nbest = max(nbest, sideLen(ele));
}
if(nbest < best){
res = changeToSquares();
}
f = true;
}
}
}
if(f){
break;
}
}
if(f){
p = mid;
}else{
l = mid + 1;
}
}
for(auto ele : res){
cout << ele.fi.fi << ' ' << ele.fi.se << ' ' << ele.se << '\n';
}
return 0;
}
