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.

The first line contains two integers n and k (1≤k≤n≤10⁶) − the number of segments and the value of k.

The next n lines contain two integers l_i,r_i (-10⁹≤l_i≤r_i≤10⁹) each − the endpoints of the i-th segment. The segments can degenerate and intersect each other. The segments are given in arbitrary order.

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.