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.util.*;
import java.io.*;
public class Red {
    static FastScanner f;
    static PrintWriter pw = new PrintWriter(System.out);
    static long mod = 1000_000_007;
    static int oo = (int)2e9;

    static class Event implements Comparable<Event> {
        int len;
        boolean op;
        
        public Event(int len , boolean op) {
            this.len = len;
            this.op = op;
        }

        @Override
        public int compareTo(Event e) {
            if (len == e.len) {
                if (op == e.op) return 0;
                if (op) return -1;
                else return 1;
            }
            return Integer.compare(len , e.len);
        }
    }

    public static void solve()throws IOException {
        int n = f.ni(); int k = f.ni();
        
        Event e[] = new Event[n << 1];
        int itr = 0;
        
        for (int i = 0; i < n; ++i) {
            e[itr++] = new Event(f.ni() , true);
            e[itr++] = new Event(f.ni() , false);
        }

        Arrays.sort(e);

        int currSeg = 1 , s = k == 1 ? 0 : -1 , count = 0;
        StringBuffer ans = new StringBuffer("");

        for (int i = 1; i < e.length; ++i) {
            if (e[i].op) ++currSeg;
            else --currSeg;
            if (currSeg >= k) {
                if (s == -1) s = i;
            }
            else {
                if (s != -1) {
                    ++count;
                    ans.append(e[s].len + " " + e[i].len + "\n");
                    s = -1;
                }
            }
        }

        if (s != -1) {
            ++count;
            ans.append(e[s].len + " " + e[e.length - 1].len + "\n");
        }
        pn(count);
        p(ans);
    }   

    public static void main(String args[])throws IOException {
        go();
        boolean test_cases = false;
        int t = test_cases ? f.ni() : 1;
        while (t --> 0) solve();
        pw.flush();
        pw.close(); 
    }

    public static void go()throws IOException {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            f = new FastScanner("");
        }
        else f = new FastScanner(System.in);
    }

    public static class FastScanner {
        StringTokenizer st;
        BufferedReader br;
 
        public FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public FastScanner(String str) {
            try {
                br = new BufferedReader(new FileReader("inp.txt"));
            }
            catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public String next()throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        public int ni() throws IOException {return Integer.parseInt(next());}
 
        public long nl() throws IOException {return Long.parseLong(next());}
 
        public String nextLine() throws IOException {return br.readLine();}

        public double nd() throws IOException {return Double.parseDouble(next());}
    }

    public static long mul(long a , long b) {
        return ((a % mod) * (b % mod)) % mod;
    }

    public static void sort(int a[]) {
        ArrayList<Integer> x = new ArrayList<>();
        for (int i : a) x.add(i);
        Collections.sort(x);
        for (int i = 0; i < a.length; ++i) a[i] = x.get(i);
    }
    
    public static void sort(long a[]) {
        ArrayList<Long> x = new ArrayList<>();
        for (Long i : a) x.add(i);
        Collections.sort(x);
        for (int i = 0; i < a.length; ++i) a[i] = x.get(i);
    }

    public static void sort(ArrayList<Integer> arr) {Collections.sort(arr);}

    public static void pn(Object o){pw.println(o);}
        
    public static void p(Object o){pw.print(o);}
        
    public static void pni(Object o){pw.println(o);pw.flush();}

    static int gcd(int x , int y) {
        if (y == 0) return Math.abs(x);
        return gcd(y , x % y);
    }
}