← 返回题目列表

Codeforces · 2096/D

D. 很棒的灯泡

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

您是无限大灯泡网格的自豪拥有者,该网格由笛卡尔坐标系表示。最初,除了你埋藏着你最引以为豪的宝藏的一个灯泡外,所有灯泡都被关闭。

为了隐藏你的宝藏位置,你执行以下操作任意次数(可能为零):

  • 选择两个 整数 数字 $$$x$$$ 和 $$$y$$$,并在 $$$(x, y)$$$、$$$(x, y + 1)$$$、$$$(x + 1, y - 1)$$$ 和 $$$(x + 1, y)$$$ 处切换 $$$4$$$ 灯泡的状态。换句话说,对于每个灯泡,如果它关闭,则将其打开,如果打开,则将其关闭。请注意,有 无限制 在 $$$x$$$ 和 $$$y$$$ 上。

最后,坐标$$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$处打开了$$$n$$$个灯泡。不幸的是,你已经忘记了你把宝藏埋在哪里了,所以现在你必须找出宝藏的一个可能位置。祝你好运!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) - 打开的灯泡数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$\color{red}{-10^8} \le x_i, y_i \le \color{red}{10^8}$$$) — 第 $$$i$$$ 个灯泡的坐标。保证所有坐标都是不同的。

附加约束: 至少存在一个位置$$$(s, t)$$$ ($$$\color{red}{-10^9} \le s, t \le \color{red}{10^9}$$$),这样如果位置$$$(s, t)$$$的灯泡一开始是打开的,那么执行任意次数的操作(可能为零)后,我们将得到给定的配置的灯泡。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出两个整数 $$$s$$$ 和 $$$t$$$ ($$$-10^9 \le s, t \le 10^9$$$) - 埋藏宝藏的一个可能位置。如果有多个解决方案,请打印其中任何一个。

对于这个问题,黑客被禁用。

示例

输入
复制

4
1
2 3
3
-2 -1
-1 -2
-1 -3
7
7 26
6 27
6 28
7 27
8 26
8 27
7 28
11
70 9
69 8
69 0
73 5
70 -1
70 5
71 7
70 4
73 4
71 3
72 3

输出
复制

2 3
-2 -2
7 27
72 7

注意

对于第一个测试用例,一种可能的情况是您将宝藏藏在位置 $$$(2, 3)$$$ 处。然后,您没有进行任何操作。

最后,只有$$$(2, 3)$$$处的灯泡亮了。

对于第二个测试用例,一种可能的情况是您将宝藏藏在位置$$$(-2, -2)$$$。然后,您使用 $$$x = -2$$$、$$$y = -2$$$ 执行 $$$1$$$ 操作。

该操作在 $$$(-2, -2)$$$、$$$(-2, -1)$$$、$$$(-1, -3)$$$ 和 $$$(-1, -2)$$$ 处切换 $$$4$$$ 灯泡的状态。

最后,$$$(-2, -1)$$$、$$$(-1, -2)$$$ 和 $$$(-1, -3)$$$ 处的灯泡打开。