[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$n$ houses in your city arranged on an axis at points h1,h2,…,hn$h_1,h_2,\dots ,h_n$. You want to build a new house for yourself and consider two options where to place it: points p1$p_1$ and p2$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 d1$d_1$, d2$d_2$: di,j=|pi−hj|$d_{i,j}=|p_i-h_j|$, where |x|$|x|$ defines the absolute value of x$x$.

After a long time of inactivity you have forgotten the locations of the houses h$h$ and the options p1$p_1$, p2$p_2$. But your diary still keeps two arrays — d1$d_1$, d2$d_2$, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of d1$d_1$ and d2$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 d1$d_1$ correspond the distances from p1$p_1$ to the houses, and in the array d2$d_2$  — from p2$p_2$ to the houses.

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

Check whether there are locations of houses h$h$ and considered points p1$p_1$, p2$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$t$ (1≤t≤103$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$n$ (1≤n≤103$1\le n\le {10}^3$) — the length of arrays d1$d_1$, d2$d_2$.

The next two lines consist arrays d1$d_1$ and d2$d_2$ (0≤di,j≤109$0\le d_{i,j}\le {10}^9$) respectively.

It is guaranteed that the sum of n$n$ over all test cases doesn't exceed 2⋅103$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$n$ integers h1,h2,…,hn$h_1,h_2,\dots ,h_n$. In the third line print two integers p1$p_1$, p2$p_2$.

It must be satisfied that 0≤hi,p1,p2≤2⋅109$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.