Reconstructing a Non‐decreasing Array from Contiguous Subarray Sums

You are given a multiset of nonnegative integers S that consists of the sums of all contiguous subarrays of an unknown non‐decreasing array a of length n (i.e. a₁, a₂, ..., a_n with a_i \le a_i+1 for all i). Formally,

\[ S = \left\{\sum_{k=l}^{r} a_k \;\bigg|\; 1 \le l \le r \le n\right\}\,. \]

The multiset S is given in an unordered manner. It is guaranteed that the size of S is m = n(n+1)/2, and note that S is a multiset (i.e. duplicate values may appear).

Your task is to restore the original array a.

Input Format

The input consists of two lines:

• The first line contains a single integer m (the number of contiguous subarray sums). Note that m = n(n+1)/2 for some positive integer n.
• The second line contains m space‐separated nonnegative integers — the elements of the multiset S.

Output Format

Output n space‐separated nonnegative integers representing the original non‐decreasing array a.

Explanation

For example, if n = 3 and a = [1, 2, 4], then all contiguous subarray sums are:

[ {1, 2, 4, 1+2=3, 2+4=6, 1+2+4=7} = {1, 2, 3, 4, 6, 7}. ]

These values may be given in any order. From these, you should reconstruct the array a.

inputFormat

The input begins with an integer m on the first line, which satisfies m = n(n+1)/2 for an unknown positive integer n. The next line contains m space‐separated nonnegative integers, representing the unordered multiset of contiguous subarray sums.

outputFormat

Output the original array a as n space‐separated nonnegative integers in one line. It is guaranteed that there is a valid array a which produces the given multiset S.

sample

1
5

5

</p>