#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef LOCAL
    FILE *f = freopen("input", "r", stdin);\
    freopen("output", "w", stdout);
#endif
    int n, k;
    cin >> n >> k;


    int grid[2][n];
    for (int i = 0; i < n; ++i) {
        cin >> grid[0][i] >> grid[1][i];
    }

    if (k == 0) {
        for (int i = 0; i < n; ++i) {
            cout << "0 0\n";
        }
    } else {
        ll dp[n][k + 1][4];
        int p[n][k + 1][4];
        memset(p, -1, sizeof(p));

        for (int i = 0; i <= k; ++i) {
            for (int j = 0; j < 4; ++j) {
                for (int q = 0; q < n; ++q)
                    dp[q][i][j] = 2e18;
                p[0][i][j] = -1;
            }
        }

        dp[0][0][3] = grid[0][0] + grid[1][0];
        for (int i = 1; i < n; ++i) {
            dp[i][0][3] = dp[i - 1][0][3] + grid[0][i] + grid[1][i];
        }
        dp[0][1][0] = 0;

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                for (int kk = 0; kk < 4; ++kk) {
                    tie(dp[i][j][0], p[i][j][0]) = min(make_pair(dp[i - 1][j - 1][kk], kk),
                                                       {dp[i][j][0], p[i][j][0]});
                }
                for (int kk: {2, 3}) {
                    tie(dp[i][j][1], p[i][j][1]) = min(make_pair(dp[i - 1][j - 1][kk], kk),
                                                       {dp[i][j][1], p[i][j][1]});
                }
                dp[i][j][1] += grid[1][i] - grid[0][i - 1];
                for (int kk: {1, 3}) {
                    tie(dp[i][j][2], p[i][j][2]) = min(make_pair(dp[i - 1][j - 1][kk], kk),
                                                       {dp[i][j][2], p[i][j][2]});
                }
                dp[i][j][2] += grid[0][i] - grid[1][i - 1];
                for (int kk: {0, 1, 2, 3}) {
                    tie(dp[i][j][3], p[i][j][3]) = min(make_pair(dp[i - 1][j][kk], kk),
                                                       {dp[i][j][3], p[i][j][3]});
                }
                dp[i][j][3] += grid[0][i] + grid[1][i];
            }
        }

        int res[2][n];
        memset(res, 0, sizeof(res));

        int ind = n - 1, now, sum;
        tie(sum, now) = min(make_pair(dp[n - 1][k][0], 0),
                            min({dp[n - 1][k][1], 1},
                                min(make_pair(dp[n - 1][k][2], 2),
                                    {dp[n - 1][k][3], 3})));

        int cnt = 1;
        while (now != -1) {
            if (now == 0)
                res[0][ind] = cnt, res[1][ind] = cnt;
            if (now == 1)
                res[0][ind] = cnt, res[0][ind - 1] = cnt;
            if (now == 2)
                res[1][ind] = cnt, res[1][ind - 1] = cnt;
            int pcnt = cnt;
            if (now == 3)
                cnt--;
            cnt++;
            now = p[ind][k - pcnt + 1][now];
            ind--;
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 2; ++j) {
                cout << res[j][i] << " ";
            }
            cout << "\n";
        }
    }

    return 0;
}