GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday 2 October 2022

[Solution] House Planning Codeforces Solution



E. House Planning
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are n houses in your city arranged on an axis at points h1,h2,,hn. You want to build a new house for yourself and consider two options where to place it: points p1 and p2.

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 d1d2di,j=|pihj|, 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 p1p2. But your diary still keeps two arrays — d1d2, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of d1 and d2 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 d1 correspond the distances from p1 to the houses, and in the array d2  — from p2 to the houses.

Also pay attention, that the locations of the houses hi and the considered options pj could match. For example, the next locations are correct: h={1,0,3,3}p={1,1}, that could correspond to already shuffled d1={0,2,1,2}d2={2,2,1,0}.

Check whether there are locations of houses h and considered points p1p2, 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 (1t103) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer n (1n103) — the length of arrays d1d2.

The next two lines consist arrays d1 and d2 (0di,j109) respectively.

It is guaranteed that the sum of n over all test cases doesn't exceed 2103.

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 h1,h2,,hn. In the third line print two integers p1p2.

It must be satisfied that 0hi,p1,p22109. 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.

No comments:

Post a Comment