#include <bits/stdc++.h>
#define int long long
using namespace std;

bool v[4][4] = {
    {1, 0, 1, 1},
    {1, 0, 1, 1},
    {0, 1, 0, 0},
    {1, 0, 1, 1}
};

bool valid(int mcur, int mprev) {
    int m1, m2;
    if (mcur==15) {
        m1 = 3, m2 = 3;
    }
    else m1 = mcur / 3, m2 = mcur % 3;
    int m3 = mprev / 4, m4 = mprev % 4;
    return (v[m1][m3] && v[m2][m4]);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int dp[n + 1][k + 1][4][4] = {};
    memset(dp, -100, sizeof dp);
    dp[0][0][0][0] = 0;
    pair<int, int> from[n + 1][k + 1][4][4] = {};
    int arr[n + 1][2] = {}, ans[n + 1][2] = {};
    for (int i = 1; i <= n; i++) {
        cin >> arr[i][0] >> arr[i][1];
        arr[i][0] += INT_MAX;
        arr[i][1] += INT_MAX;
    }
    for (int i = 1; i <= n; i++) {
        for (int d = 0; d <= k; d++) {
            for (int mcur = 0; mcur < 9; mcur++) {
                for (int mprev = 0; mprev < 16; mprev++) {
                    if ((mprev % 4 == 3 && mprev / 4 != 3) || (mprev / 4 != 3 && mprev % 4 == 3)) continue;
                    int m1 = mcur / 3, m2 = mcur % 3;
                    int add = (m1 == 2) + (m2 == 2);
                    if (add > d) continue;
                    int s = 0;
                    if (m1) s += arr[i][0];
                    if (m2) s += arr[i][1];
                    if (valid(mcur, mprev)) {
                        if (dp[i - 1][d - add][mprev / 4][mprev % 4] + s > dp[i][d][m1][m2]) {
                            from[i][d][m1][m2] = {d - add, mprev};
                            dp[i][d][m1][m2] = dp[i - 1][d - add][mprev / 4][mprev % 4] + s;
                        }
                    }
                }
            }
            for (int mprev = 0; mprev < 16; mprev++) {
                if ((mprev % 4 == 3 && mprev / 4 != 3) || (mprev / 4 != 3 && mprev % 4 == 3)) continue;
                if (!d) continue;
                if (valid(15, mprev)) {
                    if (dp[i - 1][d - 1][mprev / 4][mprev % 4] + arr[i][0] + arr[i][1] > dp[i][d][3][3]) {
                        from[i][d][3][3] = {d - 1, mprev};
                        dp[i][d][3][3] = dp[i - 1][d - 1][mprev / 4][mprev % 4] + arr[i][0] + arr[i][1];
                    }
                }
            }

        }
    }
    int maxans = 0;
    pair<int, int> start;
    for (int i = 0; i < 16; i++) {
        if (i % 4 == 1 || i / 4 == 1) continue;
        if (dp[n][k][i / 4][i % 4] > maxans) {
             maxans = dp[n][k][i / 4][i % 4];
             start = {k, i};
        }
    }
    int q = 1;
    int qty = start.first, msk = start.second;
    if (msk / 4 == 2) ans[n][0] = ans[n - 1][0] = q, q++;
    if (msk / 4 == 3) ans[n][0] = ans[n][1] = q, q++;
    if (msk % 4 == 2) ans[n][1] = ans[n - 1][1] = q, q++;
    for (int i = n - 1; i >= 1; i--) {
        start = from[i + 1][qty][msk / 4][msk % 4];
        qty = start.first, msk = start.second;
        if (msk / 4 == 2) ans[i][0] = ans[i - 1][0] = q, q++;
        if (msk / 4 == 3) ans[i][0] = ans[i][1] = q, q++;
        if (msk % 4 == 2) ans[i][1] = ans[i - 1][1] = q, q++;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i][0] << " " << ans[i][1] << "\n";
    }
}