let n;
while (n = parseInt(readline())) {
    let flag = parseInt(readline());
    let score = [];
    for (let i = 0; i < n; i++) {
        let item = readline().trim().split(' ');
        score.push({
            name: item[0],
            point: Number(item[1]),
            index: i
        });
    }
    // 排序
    score.sort((a, b) => {
        if (a.point === b.point) {
            return a.index - b.index;
        } else if (flag === 0) {
           return b.point - a.point;
        } else if (flag === 1) {
           return a.point - b.point;
        }
    });
    for (let i = 0; i < n; i++) {
        const item = JSON.parse(JSON.stringify(score[i]));
        print(item.name + ' ' + item.point);
    }
}