题目背景

JOISC2020 Day 1 T2

由于数据点较多，本题只评测其中的部分数据。

下面的题意是简要题意。

题目描述

有一个 $10^9\times 10^9$ 的金属网格，其中 $(x,y)$ 表示从左往右第 $x$ 列，从上往下第 $y$ 行的格子。（$1\leq x,y\leq 10^9$）。在这些网格上放了 $N$ 块汉堡肉，依次编号为 $1,\cdots,N$，其中第 $i$ 块汉堡肉放在以 $(L_i,D_i)$ 为左下角，$(R_i,U_i)$ 为右上角的矩形区域内，并且汉堡肉可以重叠。

你需要检查所有的汉堡肉是否煮熟。你可以选择金属网上的 $K$ 个格子，并且垂直地在这个格子中间插一根竹签。对于每一块汉堡肉来说，你可以通过在它所处的格子中插一根竹签来确认这块汉堡肉是否煮熟。当然，你也可以在一个格子里面插多根竹签或者是在没有汉堡肉的格子插竹签，尽管这很不必要。

形式上说，你需要找到 $K$ 组 $(x_1,y_1),\cdots,(x_k,y_k)$，满足以下条件：

• 对于所有 $i$，存在一个 $j$ 满足 $L_i\leq x_j\leq R_i,D_i\leq y_j\leq U_i$。

• 对于所有 $j$，$1\leq x_j,y_j\leq 10^9$。

你需要写一个程序来找出这 $K$ 组 $(x_j,y_j)$，数据保证有解。

输入格式

第一行两个的整数 $N,K$，含义见题面描述。

接下来 $n$ 行，每行四个整数 $L_i,D_i,R_i,U_i$，描述一块汉堡肉。

输出格式

$K$ 行，每行两个整数 $x_j$ 和 $y_j$。

如果有多解，输出任意一个均可。

4 2
2 1 3 3 
1 2 4 3 
6 1 7 4
5 3 7 5

2 2
7 4

3 3
1 1 1 1
1 2 1 2
1 3 1 3

1 1
1 2
1 3

提示

样例 1 解释

在 $(2,2)$ 处插一根竹签，可以确定前两块汉堡肉是否煮熟，在 $(7,4)$ 处插一根竹签，可以确定后两块汉堡肉是否煮熟。

另一种可行方案是，在 $(3,3)$ 和 $(6,4)$ 处分别插一根竹签。

子任务

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5,1\leq k\leq 4,1\leq L_i\leq R_i\leq 10^9,1\leq D_i\leq U_i\leq 10^9$，数据保证有解。