题目描述

题目译自 JOISC 2020 Day1 T2「美味しい美味しいハンバーグ / Hamburg Steak」

你听说过奇异物品公司（Just Odd Inventions, Ltd.）吗？这家公司以生产奇异物品出名。在本题中，我们简称它为 JOI 公司。

JOI 公司将要举办一场盛大的年会，主厨正在一块由 $10^9\times 10^9$ 个网格组成的超大的网格形烤架上烤着 $N$ 块汉堡肉。为了方便，我们用 $(x,~y)$ 表示从左往右数第 $x$ 列，从下往上数第 $y$ 行的网格。

我们将汉堡肉编号为 $1\ldots N$，其中第 $i$ 块汉堡覆盖了左下角 $(L_i,~D_i)$ 到右上角 $(R_i,~U_i)$ 的矩形区域，注意这些区域可能重叠。

你是 JOI 公司的萌新，现在你有 $K$ 根竹签，你只要把竹签插到一个格子里就可以知道那格的肉有没有熟，你的任务是检查所有的肉是否已经煮熟。你可以把竹签插到一个没有肉的格子里，也可以把几根竹签插到同一格里。

形式化地说，你的任务是寻找一个由 $K$ 个二元组 $(x_1,y_1),\ldots,(x_n,y_n)$ 组成的 $K$ 元组（其中元素可以重复），使得：

• 对于任意 $i\in[1,N]$，存在 $j$ 使得 $L_i\le x_j\le R_i$ 且 $D_i\le y_j\le U_i$ 成立。
• 对于任意 $j\in[1,K]$，有 $1\le x_j,~y_j \le 10^9$。

编写一个程序，给出汉堡肉覆盖的区域和竹签的数量，找出一个插竹签的方法。数据保证有解。

输入格式

第一行两个空格分隔的整数 $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

数据范围与提示

对于 $100\%$ 的数据，有 $1\le N\le 2\times 10^5,~$$1\le K\le 4,~$$1\le L_i\le R_i\le 10^9~(1\le i\le N),~$$1\le D_i\le U_i\le 10^9~(1\le i\le N)$，且数据保证有解。

各子任务限制如下：