#include <bits/stdc++.h>

using namespace std;

int main(){

    long int n, k;

    cin >> n >> k;

    long int c = k;

    long int A[4][20001];
    short int mask[4][20001] = {0};

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

    while (c > 0){

        long int imax = 1;
        long int jmax = 1;

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= 2;j++){
                if (A[i][j] > A[imax][jmax]){
                    imax = i;
                    jmax = i;
                }
            }
        }
        mask[imax][jmax] = k - c + 1;
        A[imax][jmax] = 0;

        if (jmax == 1){
            long int a = A[imax - 1][jmax];
            long int b = A[imax][jmax + 1];
            long int c = A[imax + 1][jmax];

            if ((a >= b) && (a >= c)){
                mask[imax - 1][jmax] = mask[imax][jmax];
                A[imax - 1][jmax] = 0;
            }

            if ((b >= c) && (b >= a)){
                mask[imax][jmax + 1] = mask[imax][jmax];
                A[imax][jmax + 1] = 0;
            }

            if ((c >= b) && (c >= a)){
                mask[imax + 1][jmax] = mask[imax][jmax];
                A[imax + 1][jmax] = 0;
            }
        }

        if (jmax == 2){
            long int a = A[imax - 1][jmax];
            long int b = A[imax][jmax - 1];
            long int c = A[imax + 1][jmax];

            if ((a >= b) && (a >= c)){
                mask[imax - 1][jmax] = mask[imax][jmax];
                A[imax - 1][jmax] = 0;
            }

            if ((b >= c) && (b >= a)){
                mask[imax][jmax - 1] = mask[imax][jmax];
                A[imax][jmax - 1] = 0;
            }

            if ((c >= b) && (c >= a)){
                mask[imax + 1][jmax] = mask[imax][jmax];
                A[imax + 1][jmax] = 0;
            }
        }

        c--;
    }

    for (long int i = 1; i <= n; i++){
        cout << mask[i][1] << " " << mask[i][2] << endl;
    }


    return 0;
}