#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <iomanip>
#include <string>

#define ll long long
#define pii pair<int,int>

using namespace std;

struct Tuple {
	int val;
	pii i, j;
	Tuple() {
		val = 0;
		i = j = { 0,0 };
	}
	Tuple(int _val, pii _i, pii _j) {
		val = _val;
		i = _i;
		j = _j;
	}
};

bool operator < (Tuple &a, Tuple &b) {
	return a.val < b.val;
}

int main()
{
	int n, k;
	cin >> n >> k;
	vector<Tuple> pairs;
	vector<vector<int>> field(n, vector<int>(2));
	vector<vector<bool>> used(n, vector<bool>(2));
	vector<vector<int>> ans(n, vector<int>(2));
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		field[i][0] = a;
		field[i][1] = b;

		pairs.push_back(Tuple(a + b, { i, 0 }, { i, 1 }));
		if (i > 0) {
			pairs.push_back(Tuple(field[i - 1][0] + field[i][0], { i - 1, 0 }, { i, 0 }));
			pairs.push_back(Tuple(field[i - 1][1] + field[i][1], { i - 1, 1 }, { i, 1 }));
		}
	}

	sort(pairs.begin(), pairs.end());

	for (int i = 0; i < k; i++)
	{
		if (pairs.empty())
			break;
		auto p = pairs.back();
		pairs.pop_back();
		if (used[p.i.first][p.i.second] || used[p.j.first][p.j.second])
		{
			i--;
			continue;
		}

		used[p.i.first][p.i.second] = used[p.j.first][p.j.second] = true;
		ans[p.i.first][p.i.second] = ans[p.j.first][p.j.second] = i + 1;
	}

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