CF2068H Statues

The mayor of a city wants to place $ n $ statues at intersections around the city. The intersections in the city are at all points $ (x, y) $ with integer coordinates. Distances between intersections are measured using Manhattan distance, defined as follows: $ $$$ \text{distance}((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|. $ $

The city council has provided the following requirements for the placement of the statues:

• The first statue is placed at $ (0, 0) $ ;
• The $ n $ -th statue is placed at $ (a, b) $ ;
• For $ i = 1, \\dots, n-1 $ , the distance between the $ i $ -th statue and the $ (i+1) $ -th statue is $ d\_i $ .

It is allowed to place multiple statues at the same intersection.

Help the mayor find a valid arrangement of the $ n$$$ statues, or determine that it does not exist.

The first line contains an integer $ n $ ( $ 3 \le n \le 50 $ ) — the number of statues. The second line contains two integers $ a $ and $ b $ ( $ 0 \le a, b \le 10^9 $ ) — the coordinates of the intersection where the $ n $ -th statue must be placed. The third line contains $ n-1 $ integers $ d_1, \dots, d_{n-1} $ ( $ 0 \le d_i \le 10^9 $ ) — the distance between the $ i $ -th statue and the $ (i+1) $ -th statue.

Print $ \texttt{YES} $ if there is a valid arrangement of the $ n $ statues. Otherwise, print $ \texttt{NO} $ . If there is a valid arrangement, print a valid arrangement in the following $ n $ lines. The $ i $ -th of these lines must contain two integers $ x_i $ and $ y_i $ — the coordinates of the intersection where the $ i $ -th statue is placed. You can print any valid arrangement if multiple exist.

In the first sample, there is no valid arrangement of the 3 statues. In the second sample, the sample output is shown in the following picture. Note that this is not the only valid arrangement of the 4 statues.