您是无限大灯泡网格的自豪拥有者,该网格由笛卡尔坐标系表示。最初,除了你埋藏着你最引以为豪的宝藏的一个灯泡外,所有灯泡都被关闭。
为了隐藏你的宝藏位置,你执行以下操作任意次数(可能为零):
- 选择两个 整数 数字 $$$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$$$) - 埋藏宝藏的一个可能位置。如果有多个解决方案,请打印其中任何一个。
对于这个问题,黑客被禁用。
示例
输入复制
412 33-2 -1-1 -2-1 -377 266 276 287 278 268 277 281170 969 869 073 570 -170 571 770 473 471 372 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)$$$ 处的灯泡打开。