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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.util.Comparator;
import java.io.UnsupportedEncodingException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    DTheUnionOfKSegments solver = new DTheUnionOfKSegments();
    solver.solve(1, in, out);
    out.close();
  }

  static class DTheUnionOfKSegments {

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int n = in.nextInt();
      int k = in.nextInt();
      Event[] events = new Event[n << 1];
      for (int i = 0; i < n; ++i) {
        events[i << 1] = new Event(true, in.nextInt());
        events[i << 1 | 1] = new Event(false, in.nextInt());
      }
      Arrays.sort(events,
          Comparator.comparingInt((Event e) -> e.val).thenComparing(e -> e.enter ? -1 : 1));
      List<Integer> result = new ArrayList<>(n << 1);
      int currentWindow = 0;
      for (int i = 0; i < events.length; ++i) {
        if (events[i].enter) {
          ++currentWindow;
          if (currentWindow == k) {
            result.add(events[i].val);
          }
        } else {
          if (currentWindow == k) {
            result.add(events[i].val);
          }
          --currentWindow;
        }
      }
      assert result.size() % 2 == 0;
      out.println(result.size() >> 1);
      for (int i = 0; i < result.size(); i += 2) {
        out.println(result.get(i) + " " + result.get(i + 1));
      }
    }

    class Event {

      final boolean enter;
      final int val;

      Event(boolean enter, int val) {
        this.enter = enter;
        this.val = val;
      }

      public String toString() {
        return enter ? "Enter event at " + val : "Exit Event at " + val;
      }

    }

  }

  static class OutputWriter extends PrintWriter {

    public OutputWriter(OutputStream os, boolean autoFlush) {
      super(os, autoFlush);
    }

    public OutputWriter(Writer out) {
      super(out);
    }

    public OutputWriter(Writer out, boolean autoFlush) {
      super(out, autoFlush);
    }

    public OutputWriter(String fileName) throws FileNotFoundException {
      super(fileName);
    }

    public OutputWriter(String fileName, String csn)
        throws FileNotFoundException, UnsupportedEncodingException {
      super(fileName, csn);
    }

    public OutputWriter(File file) throws FileNotFoundException {
      super(file);
    }

    public OutputWriter(File file, String csn)
        throws FileNotFoundException, UnsupportedEncodingException {
      super(file, csn);
    }

    public OutputWriter(OutputStream out) {
      super(out);
    }

    public void flush() {
      super.flush();
    }

    public void close() {
      super.close();
    }

  }

  static class InputReader implements FastIO {

    private InputStream stream;
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final int EOF = -1;
    private byte[] buf = new byte[DEFAULT_BUFFER_SIZE];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (this.numChars == EOF) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return EOF;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {
      }

      byte sgn = 1;
      if (c == 45) {
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) {
        res *= 10;
        res += c - 48;
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    public static boolean isSpaceChar(int c) {
      return c == 32 || c == 10 || c == 13 || c == 9 || c == EOF;
    }

  }

  static interface FastIO {

  }
}

