有一次,四位罗马商人在一座罗马宅邸里开会讨论他们的贸易计划。他们面临着这样的问题:他们交易的是同一种商品,如果在同一个城市交易,必然会产生损失。他们决定划分他们之间进行贸易的城市。
在这个问题中,罗马地图可以表示为一个平面,上面标有某些点——罗马帝国的城市。
商家决定选择某个分割点$$$(x_0, y_0)$$$。然后,在坐标为 $$$(x_i, y_i)$$$ 的城市中,
- 如果 $$$x_0 \le x_i$$$ 和 $$$y_0 \le y_i$$$ 则第一个商人出售商品;
- 如果 $$$x_0 > x_i$$$ 且 $$$y_0 \le y_i$$$,则第二个商人出售商品;
- 如果 $$$x_0 \le x_i$$$ 且 $$$y_0 > y_i$$$,则第三个商人出售商品;
- 如果 $$$x_0 > x_i$$$ 且 $$$y_0 > y_i$$$,则第四个商人出售商品。
商家希望选择 $$$(x_0, y_0)$$$,以最大化他们获得的城市数量最少(即尽可能公平)。请为他们找到这样的一个点。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 10^5$$$) — 地图上的城市数量。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i, y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — 城市的坐标。
请注意,某些点可能会重合。这是因为有些城市可能非常接近,以至于无法在给定比例的地图上区分它们。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在第一行中打印一个整数 $$$k$$$ ($$$0 \le k \le \frac{n}{4}$$$) — 每个商家至少可以获得的最大可能城市数。
在第二行中,打印两个整数 $$$x_0$$$ 和 $$$y_0$$$ ($$$|x_0|, |y_0| \le 10^9$$$) – 分割点的坐标。如果有多个合适的点,则打印其中任意一个。
示例
输入 #1
4 4 1 1 1 2 2 1 2 2 4 0 0 0 0 0 0 0 0 8 1 2 2 1 2 -1 1 -2 -1 -2 -2 -1 -2 1 -1 2 7 1 1 1 2 1 3 1 4 2 1 3 1 4 1
输出 #1
1 2 2 0 0 0 2 1 0 0 0 0