Codeforces Round 824 (Div. 2) |
---|
Finished |
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.
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$$$.
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.
4155210 125 20210 3326 6940 2 1 22 2 1 0
YES 5 0 10 NO YES 0 43 33 69 YES 1 0 3 3 1 1
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.
It can be shown that there is no answer for test case $$$2$$$.
In test case $$$3$$$, the planned houses are located at points $$$33$$$ and $$$69$$$.
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.
Name |
---|