House Planning

3000ms

262144K

Description:

There are $$$n$$$ houses in your city arranged on an axis at points $$$h_1, h_2, \ldots, h_n$$$. You want to build a new house for yourself and consider two options where to place it: points $$$p_1$$$ and $$$p_2$$$.

As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays $$$d_1$$$, $$$d_2$$$: $$$d_{i, j} = \left|p_i - h_j\right|$$$, where $$$|x|$$$ defines the absolute value of $$$x$$$.

After a long time of inactivity you have forgotten the locations of the houses $$$h$$$ and the options $$$p_1$$$, $$$p_2$$$. But your diary still keeps two arrays — $$$d_1$$$, $$$d_2$$$, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of $$$d_1$$$ and $$$d_2$$$ may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array $$$d_1$$$ correspond the distances from $$$p_1$$$ to the houses, and in the array $$$d_2$$$ — from $$$p_2$$$ to the houses.

Also pay attention, that the locations of the houses $$$h_i$$$ and the considered options $$$p_j$$$ could match. For example, the next locations are correct: $$$h = \{1, 0, 3, 3\}$$$, $$$p = \{1, 1\}$$$, that could correspond to already shuffled $$$d_1 = \{0, 2, 1, 2\}$$$, $$$d_2 = \{2, 2, 1, 0\}$$$.

Check whether there are locations of houses $$$h$$$ and considered points $$$p_1$$$, $$$p_2$$$, for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.

Input:

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the length of arrays $$$d_1$$$, $$$d_2$$$.

The next two lines contain $$$n$$$ integers each: arrays $$$d_1$$$ and $$$d_2$$$ ($$$0 \le d_{i, j} \le 10^9$$$) respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^3$$$.

Output:

For each test case, output a single line "NO" if there is no answer.

Otherwise output three lines. The first line must contain "YES". In the second line, print $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$. In the third line print two integers $$$p_1$$$, $$$p_2$$$.

It must be satisfied that $$$0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$$$. We can show that if there is an answer, then there is one satisfying these constraints.

If there are several answers, output any of them.

Sample Input:

Sample Output:

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

Note:

In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim.

In test case $$$1$$$, the first planned house is located at point $$$0$$$, the second at point $$$10$$$. The existing house is located at point $$$5$$$ and is at a distance of $$$5$$$ from both planned houses.

$\text{[math]}$

It can be shown that there is no answer for test case $$$2$$$.

$\text{[math]}$

In test case $$$3$$$, the planned houses are located at points $$$33$$$ and $$$69$$$.

$\text{[math]}$

Note that in test case $$$4$$$, both plans are located at point $$$1$$$, where one of the existing houses is located at the same time. It is a correct placement.

$\text{[math]}$

Informação

Provedor Codeforces

Código CF1735E