#include <bits/stdc++.h>

#pragma GCC optimize("03")

#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define pow2(x) ((x) * (x))
#define rev reverse
#define in insert
#define sz(x) (int)x.size()


using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, pii> piii;

const ll inf = (ll)1e18;
const int MAXN = (int)1e5;
const ll mod = (ll)1e9 + 7;

const double pi = acos(-1.0);

const int motion = 4;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const int N = 100500;

struct cell {
	ll y, x, yn, xn;

	cell() {
		y = x = yn = xn = 0;
	}

	cell(ll y, ll x, ll yn, ll xn) {
		this->y = y;
		this->x = x;
		this->yn = yn;
		this->xn = xn;
	}

	void out() {
		printf("y = %i, x = %i, yn = %i, xn = %i\n", y, x, yn, xn);
	}
};

int main() {
	int n, q;
	scanf("%i%i", &n, &q);

	vector<vector<int>> a(n, vector<int>(2));

	for(int i = 0; i < n; i++) {
		scanf("%i%i", &a[ i ][ 0 ], &a[ i ][ 1 ]);
	}

	map<pair<ll, ll>, cell> cells;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < motion; j++) {
			int ynew = i + dy[ j ], xnew = dx[ j ];
			if(xnew >= 0 && xnew < 2 && ynew >= 0 && ynew < n) {
				cells[ {a[ i ][ 0 ] + a[ ynew ][ xnew ], i * 0 + ynew * xnew} ] = cell{i, 0, ynew, xnew};
			}
		}

		for(int j = 0; j < motion; j++) {
			int ynew = i + dy[ j ], xnew = 1 + dx[ j ];
			if(xnew >= 0 && xnew < 2 && ynew >= 0 && ynew < n) {
				cells[ {a[ i ][ 1 ] + a[ ynew ][ xnew ], i * 1 + ynew * xnew} ] = cell{i, 1, ynew, xnew};
			}
		}
	}

	vector<vector<int>> ans(n, vector<int>(2));
	int col = 1;

	//printf("??\n");

	for(auto k = cells.end(); k != cells.begin(); k--) {
		if(k == cells.end()) continue;
		if(cells.find({k->fi.fi, k->fi.se}) == cells.end()) continue;

		//printf("{%i: %i} - ", k->fi.fi, k->fi.se);
		//k->se.out();

		/*
		for(auto k: cells) {
			printf("{%i, %i} -- ", k.fi.fi, k.fi.se);
			k.se.out();
		}

		printf("\n=========================\n");*/


		ans[ k->se.y ][ k->se.x ] = col;
		/*for(int i = 0; i < n; i++) {
			printf("%i %i\n", ans[ i ][ 0 ], ans[ i ][ 1 ]);
		}*/
		ans[ k->se.yn ][ k->se.xn ] = col;
		/*
		printf("\n======\n");
		for(int i = 0; i < n; i++) {
			printf("%i %i\n", ans[ i ][ 0 ], ans[ i ][ 1 ]);
		}*/

		++col;

		if(col > q) {
			break;
		}

		for(int j = 0; j < motion; j++) {
			int ynew = k->se.yn + dy[ j ], xnew = k->se.xn + dx[ j ];
			if(xnew >= 0 && xnew < 2 && ynew >= 0 && ynew < n) {
				cells.erase({a[ k->se.yn ][ k->se.xn ] + a[ ynew ][ xnew ], k->se.yn * k->se.xn + ynew * xnew});
			}
		}

		for(int j = 0; j < motion; j++) {
			int ynew = k->se.y + dy[ j ], xnew = k->se.x + dx[ j ];
			if(xnew >= 0 && xnew < 2 && ynew >= 0 && ynew < n) {
				cells.erase({a[ k->se.y ][ k->se.x ] + a[ ynew ][ xnew ], k->se.y * k->se.x + ynew * xnew});
			}
		}

		cells.erase({k->fi.fi, k->fi.se});

		/*
		for(int i = 0; i < n; i++) {
			printf("%i %i\n", ans[ i ][ 0 ], ans[ i ][ 1 ]);
		}*/
	}

	for(int i = 0; i < n; i++) {
		printf("%i %i\n", ans[ i ][ 0 ], ans[ i ][ 1 ]);
	}
}