#3272. 「JOISC 2020 Day1」汉堡肉

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: ksyx

题目描述

题目译自 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 。如果有多解,输出任意一个。

样例

样例输入 1

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

样例输出 1

2 2
7 4

样例解释 1

(2,~2) 处插一根竹签,可以确定汉堡肉 1 2 的煮熟情况,在 (7,~4) 处插一根竹签,可以确定汉堡肉 (3,4) 的煮熟情况。

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

样例输入 2

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

样例输出 2

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) ,且数据保证有解。

各子任务限制如下:

子任务编号 分值 附加限制
1
1
N\le 2000,~K=1
2 1 N\le 2000,~K=2
3
3
N\le 2000,~K=3
4 6 N\le 2000,~K=4
5 1 K=1
6 3 K=2
7 6 K=3
8 79 K=4