P7216 [JOISC 2020] 美味しい美味しいハンバーグ

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$。 如果有多解，输出任意一个均可。

#### 样例 1 解释 在 $(2,2)$ 处插一根竹签，可以确定前两块汉堡肉是否煮熟，在 $(7,4)$ 处插一根竹签，可以确定后两块汉堡肉是否煮熟。 另一种可行方案是，在 $(3,3)$ 和 $(6,4)$ 处分别插一根竹签。 #### 子任务 | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $N\leq 2000,K=1$ | $1$ | | $2$ | $N\leq 2000,K=2$ | $1$ | | $3$ | $N\leq 2000,K=3$ | $3$ | | $4$ | $N\leq 2000,K=4$ | $6$ | | $5$ | $K=1$ | $1$ | | $6$ | $K=2$ | $3$ | | $7$ | $K=3$ | $6$ | | $8$ | $K=4$ | $79$ | 对于 $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$，数据保证有解。