Find an array that fits a set of sums Consider an array A of length n. The array contains only positive integers.  For example A = (1,1,2,2).  Let us define f(A) as the set of sums of all the non-empty contiguous subarrays of A. In this case f(A) = {1,2,3,4,5,6}.  The steps to produce f(A)  are as follows:

The subarrays of A are (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Their respective sums are 1,1,2,2,2,3,4,4,5,6. The set you get from this list is therefore {1,2,3,4,5,6}.

Task

Given a set of sums S given in sorted order containing only positive integers and an array length n, your task is to output at least one array X such that f(X) = S.

For example, if S = {1,2,3,5,6} and n = 3 then a valid output is X = (1,2,3).

If there is no such array X your code should output any constant value.

Examples

Input: n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13), possible output: X = (3, 5, 1, 4)

Input: n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22), possible output: X = (5, 3, 2, 2, 5, 5)

Input: n=6, S = (2, 4, 6, 8, 10, 12, 16), possible output: X = (4, 2, 2, 2, 2, 4)

Input: n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14), possible output: X = (4, 2, 1, 1, 2, 4)

Input: n=10, S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25), possible output: X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5).

Input: n=15, S = (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31), possible output: X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3).

Input and output format

Your code can take input and give output in any easily human read format you find convenient. However, please show the output of testing it on the examples in the question.

Running time

You must be able to run the code to completion for all the examples in the question. It should in principle be correct for n up to 15 but you do not need to prove it would be fast enough for all inputs.
Husk, 20 bytes

ḟȯ⁰¦ṁ∫ṫ!¡Sof~Λ€∫×:¹g


Try it online!

Returns one solution, or an empty list if it doesn't exist.
The last test case (n=15) finishes in 3.8 seconds on TIO.

Explanation

The program has two parts.
In the first part (¡ and to the right of it), we construct an infinite list whose kth element is a list containing all length-k lists whose slice sums are in S.
We do this inductively, starting from the 1-element slices of S, and at each step prepending each element of S to each list, and keeping those whose prefix sums are in S.
In the second part (! and to the left of it), we take the nth element of the list, which contains length-n lists.
Of these, we select the first one whose slice sums actually contain every element of S.

In the code, let's first replace o and ȯ (which compose two and three functions into one) by parentheses for clarity.

¡S(f~Λ€∫)×:¹g  First part. Input is a list, say S=[1,2,3]
            g  Group equal adjacent elements: [[1],[2],[3]]
¡              Iterate function:
                Argument is a list of lists, say [[1,1],[1,2],[2,1]]
         ×      Mix (combine two lists in all possible ways)
          :     by prepending
           ¹    with the list S: [[1,1,1],[1,1,2],[2,1,1],[1,2,1],[2,1,2],[3,1,1],[2,2,1],[3,1,2],[3,2,1]]
   f            Filter by condition:
        ∫        Cumulative sums: [[1,2,3],[1,2,4],[2,3,4],[1,3,4],[2,3,5],[3,4,5],[2,4,5],[3,4,6],[3,5,6]]
     ~Λ          All of the numbers
 S     €         are elements of S: [[1,1,1]]
                 Only this list remains, since the other cumulative sums contain numbers not from S.
               Result of iteration: [[[1],[2],[3]],[[1,1],[1,2],[2,1]],[[1,1,1]],[],[],[]...

ḟ(⁰¦ṁ∫ṫ)!      Second part. Implicit input, say n=2.
        !      Take nth element of above list: [[1,1],[1,2],[2,1]]
ḟ              Find first element that satisfies this:
                Argument is a list, say [1,2]
      ṫ         Tails: [[1,2],[2]]
    ṁ           Map and concatenate
     ∫          cumulative sums: [1,3,2]
 ȯ ¦            Does it contain all elements of
  ⁰             S? Yes.
               Result is [1,2], print implicitly.


There are some parts that need more explanation.
In this program, the superscripts ⁰¹ both refer to the first argument S.
However, if α is a function, then α¹ means "apply α to S", while ⁰α means "plug S to the second argument of α".
The function ¦ checks whether its first argument contains all elements of the second (counting multiplicities), so S should be its second argument.

In the first part, the function that ¡ uses can be interpreted as S(f~Λ€∫)(×:)¹.
The combinator S behaves like Sαβγ -&gt; (αγ)(βγ), which means that we can simplify it to (f~Λ€∫¹)(×:¹).
The second part, ×:¹, is "mix with S by prepending", and its result is passed to the first part.
The first part, f~Λ€∫¹, works like this.
The function f filters a list by a condition, which in this case is ~Λ€∫¹.
It receives a list of lists L, so we have ~Λ€∫¹L.
The combinator ~ behaves like ~αβγδε -&gt; α(βδ)(γε): the first argument is passed to β, the second to γ, and the results are combined with α.
This means that we have Λ(€¹)(∫L).
The last part ∫L is just the cumulative sums of L, €¹ is a function that checks membership in S, and Λ takes a condition (here €¹) and a list (here ∫L), and checks that all elements satisfy it.
Put simply, we filter the results of the mixing by whether their cumulative sums are all in S.