No tag edit access

D. The Union of k-Segments

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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* ≤ 10^{6}) — the number of segments and the value of *k*.

The next *n* lines contain two integers *l*_{i}, *r*_{i} ( - 10^{9} ≤ *l*_{i} ≤ *r*_{i} ≤ 10^{9}) 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 *a*_{j}, *b*_{j} (*a*_{j} ≤ *b*_{j}) — 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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2017 11:52:09 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|