Rectangular Polyline
Contest: Codeforces Round 680 (Div. 1, based on Moscow Team Olympiad)
Difficulty rating: 2900
Tags: constructive algorithms, dp, geometry

One drew a closed polyline on a plane, that consisted only of vertical and horizontal segments (parallel to the coordinate axes). The segments alternated between horizontal and vertical ones (a horizontal segment was always followed by a vertical one, and vice versa). The polyline did not contain strict self-intersections, which means that in case any two segments shared a common point, that point was an endpoint for both of them (please consult the examples in the notes section).

Unfortunately, the polyline was erased, and you only know the lengths of the horizonal and vertical segments. Please construct any polyline matching the description with such segments, or determine that it does not exist.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 200$$$) —the number of test cases.

The first line of each test case contains one integer $$$h$$$ ($$$1 \leq h \leq 1000$$$) — the number of horizontal segments. The following line contains $$$h$$$ integers $$$l_1, l_2, \dots, l_h$$$ ($$$1 \leq l_i \leq 1000$$$) — lengths of the horizontal segments of the polyline, in arbitrary order.

The following line contains an integer $$$v$$$ ($$$1 \leq v \leq 1000$$$) — the number of vertical segments, which is followed by a line containing $$$v$$$ integers $$$p_1, p_2, \dots, p_v$$$ ($$$1 \leq p_i \leq 1000$$$) — lengths of the vertical segments of the polyline, in arbitrary order.

Test cases are separated by a blank line, and the sum of values $$$h + v$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case output Yes, if there exists at least one polyline satisfying the requirements, or No otherwise. If it does exist, in the following $$$n$$$ lines print the coordinates of the polyline vertices, in order of the polyline traversal: the $$$i$$$-th line should contain two integers $$$x_i$$$ and $$$y_i$$$ — coordinates of the $$$i$$$-th vertex.

Note that, each polyline segment must be either horizontal or vertical, and the segments should alternate between horizontal and vertical. The coordinates should not exceed $$$10^9$$$ by their absolute value.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case of the first example, the answer is Yes — for example, the following picture illustrates a square that satisfies the requirements:

In the first test case of the second example, the desired polyline also exists. Note that, the polyline contains self-intersections, but only in the endpoints:

In the second test case of the second example, the desired polyline could be like the one below:

Note that the following polyline is not a valid one, since it contains self-intersections that are not endpoints for some of the segments:

Example input:
2
2
1 1
2
1 1

2
1 2
2
3 3

Example output:
Yes
1 0
1 1
0 1
0 0
No

Example input:
2
4
1 1 1 1
4
1 1 1 1

3
2 1 1
3
2 1 1

Example output:
Yes
1 0
1 1
2 1
2 2
1 2
1 1
0 1
0 0
Yes
0 -2
2 -2
2 -1
1 -1
1 0
0 0

Editorial:
First, note that in a correct polyline, since the horizontal and vertical segments alternate, $$$h=v$$$: if this equality does not hold, the answer is negative. Now let's fix a vertex and go around the polyline in some direction. Then in the process of traversin, we will move in one of four possible directions: up, down, right or left. Since the polyline is closed, this means that we will move to the left in total by the same distance as we will move to the left in total. The same is true for moving up and down.
This means that if we split all the segments into four sets named $$$Up$$$, $$$Down$$$, $$$Left$$$, $$$Right$$$, then the total length of the segments in $$$Up$$$ will be equal to the total length of the segments in $$$Down$$$, and the total length of the segments in $$$Right$$$ will be equal to the total length of the segments in $$$Left$$$. But it means that the set of lengths of all horizontal segments can be divided into two sets with the same sum. The same should hold for vertical segments.
Let's check whether it is possible to divide the set of lengths of horizontal segments into two sets of the same sum. This classic problem can be solved by applying the dynamic programming method to solve the backpack problem. The complexity of this solution will be $$$ \mathcal O\left({nC^2}\right)$$$ If it is impossible to split horizontal or vertical lengths into two sets of equal length, the answer is "No". Now we will show how to construct a correct answer if such divisions exist.
Let us divide all horizontal lengths into two sets of equal total length. We denote the smaller set as $$$R$$$, and the larger set as $$$L$$$. We will do the same with the set of lengths of vertical segments: we will denote the smaller set as $$$D$$$, and the larger one as $$$U$$$. Since $$$|R| \leq |L|$$$, $$$ |R| \leq h / 2 = v / 2$$$. Similarly, we have $$$v / 2 \leq |U|$$$, which follows that $$$|R| \leq |U/$$$, $$$|D| \leq |L|$$$.
Now let's divide all the segments into pairs as follows: each segment of $$$R$$$, we match with a segment from $$$U$$$. All remaining segments of $$$L$$$ are matched with one of the remaining vertical segments. Thus, we have divided all these segments into three sets of pairs: in the first one, a segment from $$$R$$$ is paired with a segment from $$$U$$$. In the second set a segment from $$$L$$$ is paired with a segment from $$$U$$$. In the third set a segment from $$$D$$$ is paired with a segment from $$$L$$$.
From the first set of pairs, we make up the set of vectors directed up and to the right (from the pair (r, u), we construct the vector (r, u)). This way we can construct a set of vectors $$$A$$$. We will do the same with the second set of pairs (constructing a set of vectors $$$B$$$) and the third set of pairs (constructing a set of vectors $$$C$$$). for a better understanding, see the picture above. Note that the set $$$B$$$ may be empty, while the other two can not.
Let's make a convex polyline from the vectors of $$$A$$$. In order to do this, sort them in ascending order by the polar angle and make a polyline from them in this order (see the picture below).
Now we will replace each of the vectors of our polyline with two vectors: one vector directed to the right and one vector directed upwards.
We will do the same for vectors from $$$C$$$: sort them in ascending order by the polar angle and make a convex polyline from them:
Let's combine these two polylines so that the first one goes from the point $$$O$$$ to the point $$$A$$$ and the second one goes from the point $$$B$$$ to the point $$$O$$$:
We don't have much left to do: we hate to connect the points $$$A$$$ and $$$B$$$ using vectors from the set $$$B$$$. Let's take these vectors (directed up and to the left) in any arbitrary order, then, since the sum of all vectors is 0, the resulting polyline, if you draw it with the beginning at the point $$$A$$$, will end at the point $$$B$$$. Since the first two polylines were convex, this means that none of the points of the first two polylines will lie strictly inside the angle $$$AOB$$$, which means that if you replace each of the vectors of the third polyline with two vectors, one directed to the left and one directed upwards, the resulting closed polyline will not contain self-intersections.
It is easy to show that the resulting polyline will be closed and will satisfy all the conditions of the problem: