You are given n segments on the coordinate axis Ox and the number k. The point is satisfied if it belongs to at least k segments. Find the smallest (by the number of segments) set of segments on the coordinate axis Ox which contains all satisfied points and no others.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 106) — the number of segments and the value of k.

The next n lines contain two integers li, ri ( - 109 ≤ li ≤ ri ≤ 109) each — the endpoints of the i-th segment. The segments can degenerate and intersect each other. The segments are given in arbitrary order.

Output

First line contains integer m — the smallest number of segments.

Next m lines contain two integers aj, bj (aj ≤ bj) — the ends of j-th segment in the answer. The segments should be listed in the order from left to right.

Examples

Input

3 2
0 5
-3 2
3 8


Output

2
0 2
3 5


Input

3 2
0 5
-3 3
3 8


Output

1
0 5
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class TheUnionOfKSegments {
    InputStream is;
    PrintWriter out;
    String INPUT = "";

    long mod = 1000000007;

    void solve() {
        int n = ni();
        int k = ni();
        List<Node> li = new ArrayList();
        for (int i = 0; i < n; i++) {
            Node n1 = new Node();
            n1.i = ni();
            n1.isStart = true;
            li.add(n1);

            Node n2 = new Node();
            n2.i = ni();
            n2.isStart = false;
            li.add(n2);
        }

        int stack = 0;
        int prev = 0;
        List<Pair> result = new ArrayList();
        Collections.sort(li, (n1, n2) -> {
            if (n1.i != n2.i) {
                return n1.i - n2.i;
            } else {
                if (n1.isStart == n2.isStart) return 0;
                return n1.isStart ? -1 : 1;
            }
        });
        for (int i = 0; i < 2 * n; i++) {
            Node curr = li.get(i);
            if (curr.isStart == false) {
                if (stack == k) {
                    Pair p = new Pair();
                    p.a = prev;
                    p.b = curr.i;
                    result.add(p);
                }
                stack--;
            } else {
                if (stack == k - 1) {
                    prev = curr.i;
                }
                stack++;
            }
        }
        List<Pair> fi = new ArrayList();
        int last = 0;
        int lastStart = 0;
        for (int i = 0; i < result.size(); i++) {
            if (i > 0 && result.get(i).a == last) {
                last = result.get(i).b;
            } else {
                if (i > 0) {
                    Pair p = new Pair();
                    p.a = lastStart;
                    p.b = last;
                    fi.add(p);
                }

                lastStart = result.get(i).a;
                last = result.get(i).b;
            }
        }
        if (result.size() > 0) {
            Pair p = new Pair();
            p.a = lastStart;
            p.b = last;
            fi.add(p);
        }

        out.println(fi.size());
        for (int i = 0; i < fi.size(); i++) {
            out.println(fi.get(i).a + " " + fi.get(i).b);
        }
    }

    class Pair {
        int a;
        int b;
    }

    class Node {
        int i;
        boolean isStart;
    }

    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);

        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");
    }

    public static void main(String[] args) throws Exception {
        new TheUnionOfKSegments().run();
    }

    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private static void tr(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
}
