Codeforces Round 824 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

graph matchings

greedy

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. House Planning

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Example

Input

4155210 125 20210 3326 6940 2 1 22 2 1 0

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.

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/17/2024 09:46:14 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|