你听说过 Just Odd Inventions, Ltd. 吗？这家公司以其“奇奇怪怪的发明”而闻名。在本题中，我们将其简称为 JOI, Ltd.。

JOI, Ltd. 正在举办一场新年派对。员工们正在一个巨大的金属网上烘烤 $N$ 个汉堡肉。我们将金属网视为一个 $1\,000\,000\,000 \times 1\,000\,000\,000$ 的网格。我们用 $(x, y)$ 表示从左往右第 $x$ 列、从下往上第 $y$ 行的单元格（$1 \le x \le 1\,000\,000\,000$，$1 \le y \le 1\,000\,000\,000$）。

汉堡肉编号为 $1$ 到 $N$。第 $i$ 个汉堡肉（$1 \le i \le N$）放置在左下角顶点为 $(L_i, D_i)$、右上角顶点为 $(R_i, U_i)$ 的矩形区域内。汉堡肉之间可能会重叠。

你是 JOI, Ltd. 的一名新员工。你的任务是在金属网上选择 $K$ 个单元格，并在这些单元格的中心垂直于金属网插入竹签。对于每个汉堡肉，你可以通过在它所在的区域内至少插入一根竹签来确认它是否烤熟。你需要确认所有的汉堡肉。允许在同一个单元格内插入多根竹签，也允许在没有汉堡肉的单元格内插入竹签。

形式化地说，你的任务是找到一个包含 $K$ 个整数对（不一定不同）的元组 $(x_1, y_1), \dots, (x_K, y_K)$，满足以下条件：

• 对于每个 $i$（$1 \le i \le N$），都存在一个 $j$（$1 \le j \le K$），使得 $L_i \le x_j \le R_i$ 且 $D_i \le y_j \le U_i$ 成立。
• 对于每个 $j$（$1 \le j \le K$），均满足 $1 \le x_j \le 1\,000\,000\,000$ 且 $1 \le y_j \le 1\,000\,000\,000$。

编写一个程序，在给定汉堡肉位置和竹签数量的情况下，计算出一种插入竹签的方法。对于本题给定的输入数据，保证存在满足上述条件的单元格元组。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N \ K$ $L_1 \ D_1 \ R_1 \ U_1$ $L_2 \ D_2 \ R_2 \ U_2$ $\vdots$ $L_N \ D_N \ R_N \ U_N$

输出格式

向标准输出打印 $K$ 行。在第 $j$ 行（$1 \le j \le K$）中，输出 $x_j$ 和 $y_j$，中间用空格分隔。

如果存在多种满足条件的插入竹签的方法，输出其中任意一种即可。

数据范围

• $1 \le N \le 200\,000$
• $1 \le K \le 4$
• $1 \le L_i \le R_i \le 1\,000\,000\,000$（$1 \le i \le N$）
• $1 \le D_i \le U_i \le 1\,000\,000\,000$（$1 \le i \le N$）
• 保证存在满足题目条件的 $K$ 个单元格的元组。

子任务

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$

样例

样例输入 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 已烤熟。除了 $(2, 2)$ 和 $(7, 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