**House Planning solution codeforces** – There are 𝑛n houses in your city arranged on an axis at points ℎ1,ℎ2,…,ℎ𝑛h1,h2,…,hn. You want to build a new house for yourself and consider two options where to place it: points 𝑝1p1 and 𝑝2p2.

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 𝑑1d1, 𝑑2d2: 𝑑𝑖,𝑗=∣∣𝑝𝑖−ℎ𝑗∣∣di,j=|pi−hj|, where |𝑥||x| defines the absolute value of 𝑥x.

Table of Contents

## [Solution] House Planning solution codeforces

After a long time of inactivity you have forgotten the locations of the houses ℎh and the options 𝑝1p1, 𝑝2p2. But your diary still keeps two arrays — 𝑑1d1, 𝑑2d2, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of 𝑑1d1 and 𝑑2d2 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 𝑑1d1 correspond the distances from 𝑝1p1 to the houses, and in the array 𝑑2d2 — from 𝑝2p2 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: ℎ={1,0,3,3}h={1,0,3,3}, 𝑝={1,1}p={1,1}, that could correspond to already shuffled 𝑑1={0,2,1,2}d1={0,2,1,2}, 𝑑2={2,2,1,0}d2={2,2,1,0}.

Check whether there are locations of houses ℎh and considered points 𝑝1p1, 𝑝2p2, for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.

## [Solution] House Planning solution codeforces

The first line of the input contains a single integer 𝑡t (1≤𝑡≤1031≤t≤103) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer 𝑛n (1≤𝑛≤1031≤n≤103) — the length of arrays 𝑑1d1, 𝑑2d2.

The next two lines consist arrays 𝑑1d1 and 𝑑2d2 (0≤𝑑𝑖,𝑗≤1090≤di,j≤109) respectively.

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 2⋅1032⋅103.

## [Solution] House Planning solution codeforces

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 ℎ1,ℎ2,…,ℎ𝑛h1,h2,…,hn. In the third line print two integers 𝑝1p1, 𝑝2p2.

It must be satisfied that 0≤ℎ𝑖,𝑝1,𝑝2≤2⋅1090≤hi,p1,p2≤2⋅109. 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.

## [Solution] House Planning solution codeforces

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

## [Solution] House Planning solution codeforces

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 11, the first planned house is located at point 00, the second at point 1010. The existing house is located at point 55 and is at a distance of 55 from both planned houses.