← 返回题目列表

Codeforces · 1735/E

E. 房屋规划

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

您的城市中有 $$$n$$$ 房屋排列在轴上的点 $$$h_1、h_2、\ldots、h_n$$$ 处。您想为自己建造一座新房子,并考虑放置它的两个选项:点 $$$p_1$$$ 和 $$$p_2$$$。

由于您喜欢拜访朋友,因此您提前计算了这两个选项到所有现有房屋的距离。更正式地说,您计算了两个数组 $$$d_1$$$、$$$d_2$$$: $$$d_{i, j} = \left|p_i - h_j\right|$$$,其中 $$$|x|$$$ 定义 $$$x$$$ 的绝对值。

长时间不活动后,您忘记了房屋 $$$h$$$ 的位置以及选项 $$$p_1$$$、$$$p_2$$$。但你的日记仍然保留着两个数组——$$$d_1$$$、$$$d_2$$$,你怀疑它们的真实性。另外,每个数组内的值可以被打乱,因此$$$d_1$$$和$$$d_2$$$相同位置的值可能对应于不同的房子。请注意,一个数组中的值无法到达另一个数组中,换句话说,数组 $$$d_1$$$ 中的所有值对应于从 $$$p_1$$$ 到房屋的距离,而数组 $$$d_2$$$ 中的所有值对应于从 $$$p_2$$$ 到房屋的距离。

另请注意,房屋 $$$h_i$$$ 的位置和考虑的选项 $$$p_j$$$ 可以匹配。例如,接下来的位置是正确的:$$$h = \{1, 0, 3, 3\}$$$,$$$p = \{1, 1\}$$$,可能对应于已经打乱的$$$d_1 = \{0, 2, 1, 2\}$$$,$$$d_2 = \{2, 2, 1, 0\}$$$。

检查是否存在房屋 $$$h$$$ 的位置和考虑的点 $$$p_1$$$、$$$p_2$$$,对于这些位置,所建立的距离数组是正确的。如果可能的话,找到合适的房屋位置并考虑选择。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^3$$$) — 数组 $$$d_1$$$、$$$d_2$$$ 的长度。

接下来的两行分别包含 $$$n$$$ 个整数:分别是数组 $$$d_1$$$ 和 $$$d_2$$$ ($$$0 \le d_{i, j} \le 10^9$$$)。

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

输出

对于每个测试用例,如果没有答案,则输出单行“NO”。

否则输出三行。第一行必须包含“YES”。在第二行中,打印 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$。在第三行中打印两个整数$$$p_1$$$,$$$p_2$$$。

必须满足 $$$0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$$$。我们可以证明,如果有一个答案,那么就有一个满足这些约束。

如果有多个答案,则输出其中任何一个。

示例

输入 #1

4
1
5
5
2
10 12
5 20
2
10 33
26 69
4
0 2 1 2
2 2 1 0

输出 #1

YES
5 
0 10
NO
YES
0 43 
33 69
YES
1 0 3 3
1 1

注意

在下图中您可以看到示例解决方案。规划中的房屋以明亮的颜色显示:粉色和紫色。现有房屋昏暗。

在测试用例 $$$1$$$ 中,第一个计划的房屋位于点 $$$0$$$,第二个位于点 $$$10$$$。现有房屋位于 $$$5$$$ 点,与两栋规划房屋的距离为 $$$5$$$。

可以看出测试用例$$$2$$$没有答案。

在测试用例 $$$3$$$ 中,规划的房屋位于 $$$33$$$ 和 $$$69$$$ 点。

请注意,在测试用例 $$$4$$$ 中,两个计划都位于点 $$$1$$$,其中一栋现有房屋同时位于该点。这是一个正确的放置位置。