ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class DataNode{
    public String s;
    public Integer cnt;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        DataNode dataNode = (DataNode) o;
        return Objects.equals(s, dataNode.s);
    }

    @Override
    public int hashCode() {

        return Objects.hash(s);
    }

    public DataNode(String s, Integer cnt) {
        this.s = s;
        this.cnt = cnt;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int k = sc.nextInt();

        Map<String, DataNode> strMapCnt = new HashMap<>();
        for(int i=0;i<n;i++){
            String s = sc.next();
            if(strMapCnt.containsKey(s)){
                DataNode dataNode = strMapCnt.get(s);
                DataNode newDataNode = new DataNode(s, dataNode.cnt + 1);
                strMapCnt.put(s, newDataNode);
            }else {
                DataNode newDataNode = new DataNode(s, 1);
                strMapCnt.put(s, newDataNode);
            }
        }
        PriorityQueue<DataNode> priorityQueue = new PriorityQueue<>((a,b)->{
            if(a.cnt.equals(b.cnt) && a.s.equals(b.s)){
                return 0;
            }
            if(a.cnt > b.cnt){
                return -1;
            }else if(a.cnt.equals(b.cnt)){
                if(a.s.compareTo(b.s) < 0){
                    return -1;
                }
            }
            return 1;
        });
        for(String key: strMapCnt.keySet()){
            DataNode dataNode = strMapCnt.get(key);
            priorityQueue.offer(dataNode);
        }
        for(int i=0;i<k;i++){
            DataNode dataNode = priorityQueue.poll();
            System.out.println(dataNode.s + " " + dataNode.cnt);
        }
    }

}
/*
输出K行，每行有一个字符串和一个整数。
你需要按照出现出现次数由小到大输出，若出现次数相同时字符串字典序较小的优先输出

4 2
1
2
3
4

1 1
2 1

4 2
1
1
2
3

1 2
2 1
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class DataNode{
    public String s;
    public Integer cnt;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        DataNode dataNode = (DataNode) o;
        return Objects.equals(s, dataNode.s);
    }

    @Override
    public int hashCode() {

        return Objects.hash(s);
    }

    public DataNode(String s, Integer cnt) {
        this.s = s;
        this.cnt = cnt;
    }
}

class DataRecord{
    Map<String, DataNode> strMapCnt;
//    Map<Integer, LinkedList<DataNode>> cntMapStrs;
    PriorityQueue<DataNode> priorityQueue;
    int k;

    DataRecord(int _k){
        k = _k;
        strMapCnt = new HashMap<>();
//        cntMapStrs = new HashMap<>();
        priorityQueue = new PriorityQueue<>((a,b)->{
            if(a.cnt.equals(b.cnt) && a.s.equals(b.s)){
                return 0;
            }
            if(a.cnt < b.cnt){
                return -1;
            }else if(a.cnt.equals(b.cnt)){
                if(a.s.compareTo(b.s) > 0){
                    return -1;
                }
            }
            return 1;
        });
    }

    public void putStr(String s){
        if(strMapCnt.containsKey(s)){
            // 更新cnt
            DataNode oldDataNode = strMapCnt.get(s);
            DataNode newDataNode = new DataNode(s, oldDataNode.cnt + 1);
            strMapCnt.put(s, newDataNode);

//            cntMapStrs.get(oldDataNode.cnt).remove(oldDataNode);
//            if(cntMapStrs.containsKey(newDataNode.cnt)){
//                LinkedList<DataNode> linkedList = cntMapStrs.get(newDataNode.cnt);
//                linkedList.add(newDataNode);
//                cntMapStrs.put(newDataNode.cnt, linkedList);
//            }else {
//                LinkedList<DataNode> linkedList = new LinkedList<>();
//                linkedList.add(newDataNode);
//                cntMapStrs.put(newDataNode.cnt, linkedList);
//            }

            // 调整堆
            if(priorityQueue.contains(oldDataNode)){
                priorityQueue.remove(oldDataNode);
                priorityQueue.add(newDataNode);
            }else {
                if(priorityQueue.size() < k){
                    priorityQueue.offer(newDataNode);
                }else if(priorityQueue.size() == k){
                    DataNode topDataNode = priorityQueue.peek();
                    if(newDataNode.cnt > topDataNode.cnt){
                        priorityQueue.poll();
                        priorityQueue.offer(newDataNode);
                    }else if(newDataNode.cnt.equals(topDataNode.cnt)){
                        if(newDataNode.s.compareTo(topDataNode.s) < 0){
                            priorityQueue.poll();
                            priorityQueue.offer(newDataNode);
                        }
                    }
                }
            }
        }else {
            // 新建一个节点
            DataNode dataNode = new DataNode(s, 1);
            strMapCnt.put(s, dataNode);
//            if(cntMapStrs.containsKey(1)){
//                LinkedList<DataNode> linkedList = cntMapStrs.get(1);
//                linkedList.add(dataNode);
//                cntMapStrs.put(1, linkedList);
//            }else {
//                LinkedList<DataNode> linkedList = new LinkedList<>();
//                linkedList.add(dataNode);
//                cntMapStrs.put(1, linkedList);
//            }
            // 调整堆
            if(priorityQueue.size() < k){
                priorityQueue.offer(dataNode);
            }else if(priorityQueue.size() == k){
                DataNode topDataNode = priorityQueue.peek();
                if(dataNode.cnt > topDataNode.cnt){
                    priorityQueue.poll();
                    priorityQueue.offer(dataNode);
                }else if(dataNode.cnt.equals(topDataNode.cnt)){
                    if(dataNode.s.compareTo(topDataNode.s) < 0){
                        priorityQueue.poll();
                        priorityQueue.offer(dataNode);
                    }
                }
            }
        }
    }

    public void printK(){
        if (strMapCnt == null || strMapCnt.size() == 0){
            return;
        }
        DataNode[] ans = new DataNode[k];
        int index = k - 1;
        Iterator<DataNode> it = priorityQueue.iterator();
        while (it.hasNext()){
            DataNode dataNode = it.next();
//            System.out.println(dataNode.cnt + " " + dataNode.s);
            ans[index --] = dataNode;
        }
        for(int i=index+1;i<k;i++){
            System.out.println(ans[i].s + " " + ans[i].cnt);
        }
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {

       int n = sc.nextInt();
       int k = sc.nextInt();

        DataRecord dataRecord = new DataRecord(k);
        for(int i=0;i<n;i++){
            String s = sc.next();
            dataRecord.putStr(s);
        }
        dataRecord.printK();
    }

}
/*
输出K行，每行有一个字符串和一个整数。
你需要按照出现出现次数由小到大输出，若出现次数相同时字符串字典序较小的优先输出

4 2
1
2
3
4

1 1
2 1

4 2
1
1
2
3

1 2
2 1
 */