← 返回题目列表

Codeforces · 1028/C

C. 矩形

中文机器翻译题面 查看原题

给你一个平面上的 $$$n$$$ 个矩形,以及它们的左下点和右上角点的坐标。给定的 $$$n$$$ 矩形中的某些 $$$(n-1)$$$ 有一些共同点。如果一个点严格位于矩形内部或属于其边界,则该点属于矩形。

查找具有整数坐标且至少属于 $$$(n-1)$$$ 给定矩形的任何点。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 132\,674$$$) — 给定矩形的数量。

接下来的 $$$n$$$ 行包含四个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$ 和 $$$y_2$$$ ($$$-10^9 \le x_1 < x_2 \le 10^9$$$、$$$-10^9 \le y_1 < y_2 \le 10^9$$$) — 矩形左下角和右上角的坐标。

输出

打印两个整数 $$$x$$$ 和 $$$y$$$ — 属于至少 $$$(n-1)$$$ 给定矩形的任何点的坐标。

示例

输入 #1

3
0 0 1 1
1 1 2 2
3 0 4 1

输出 #1

1 1

输入 #2

3
0 0 1 1
0 1 1 2
1 0 2 1

输出 #2

1 1

输入 #3

4
0 0 5 5
0 0 4 4
1 1 4 4
1 1 4 4

输出 #3

1 1

输入#4

5
0 0 10 8
1 2 6 7
2 3 5 6
3 4 4 5
8 1 9 2

输出#4

3 4

注意

下图显示了第一个和第二个示例中的矩形。可能的答案已突出显示。

下图显示了第三个和第四个示例中的矩形。