// 部分正确！
//

#include "stdafx.h"
#include<iostream>
#include<string>
#include<utility>
#include<vector>
#include<algorithm>


using namespace std;



int main()
{
    unsigned n, k;
    cin >> n >> k;

    //读取输入数据
    string tmp_name;
    unsigned tmp_high;
    vector<pair<string, unsigned>> data;
    for (unsigned i = 0; i < n; ++i)
    {
        cin >> tmp_name >> tmp_high;
        data.push_back(make_pair(tmp_name, tmp_high));
    }

    //根据身高和姓氏排序
    //sort(data.begin(), data.end(), [](pair<string, unsigned> lh, pair<string, unsigned> rh) {return lh.first < rh.first; });
    stable_sort(data.begin(), data.end(), [](pair<string, unsigned> lh, pair<string, unsigned> rh) {return lh.second < rh.second; });

//对输入的数据进行切片
    vector<vector<pair<string, unsigned>>> format_data;
    unsigned m = floor(n*1.0 / k*1.0);
    unsigned last_m = n - m*(k - 1);
    auto beg = data.begin();
    for (size_t i = 0; i < k;++i)
    {
        if (i != (k - 1))
        {
            vector<pair<string, unsigned>> tmp(beg, beg + m);
            sort(tmp.begin(), tmp.end(), [](pair<string, unsigned> lh, pair<string, unsigned> rh) {return lh.first < rh.first; });
            stable_sort(tmp.begin(), tmp.end(), [](pair<string, unsigned> lh, pair<string, unsigned> rh) {return lh.second > rh.second; });
            format_data.push_back(tmp);
            beg = beg + m;
        }
        else
        {
            vector<pair<string, unsigned>> tmp(beg, data.end());
            sort(tmp.begin(), tmp.end(), [](pair<string, unsigned> lh, pair<string, unsigned> rh) {return lh.first < rh.first; });
            stable_sort(tmp.begin(), tmp.end(), [](pair<string, unsigned> lh, pair<string, unsigned> rh) {return lh.second > rh.second; });
            format_data.push_back(tmp);
            beg = beg + m;
        }
        
    }

    //根据规则排序
    vector<vector<string>> out_format(k-1, vector<string>(m," "));
    out_format.push_back(vector<string>(last_m,""));

    unsigned now_middle;
    int change_r_l = 0;
    int r_l = 0;


    for (size_t i = 0; i < format_data.size(); ++i)
    {
        now_middle = format_data[i].size()/2+1;
        for (size_t j = 0; j < format_data[i].size(); ++j)
        {
            out_format[i][now_middle - 1] = format_data[i][j].first;
            now_middle = now_middle- pow(-1, j)*(j + 1);
        }
    }

    for (int i=out_format.size()-1;i>=0;--i)
    {
        for (size_t j = 0; j < out_format[i].size(); ++j)
        {
            cout << out_format[i][j];
            if (j != (out_format[i].size() - 1))
                cout << " ";
        }
        if(i!=0)
            cout << endl;
    }

    system("pause");
    return 0;
}