Finding a Sequence from a Sign Matrix

For an integer sequence a1, a2, ..., an, define its sign matrix S as follows. For every interval 1 <= i <= j <= n, Sij is "+" if ai + ... + aj is positive, "-" if it is negative, and "0" if it is zero.

For the sequence (-1, 5, -4, 2), the sign matrix is:

We say that this sequence generates the sign matrix. A sign matrix is valid if some integer sequence can generate it.

Given a valid sign matrix, find one integer sequence that generates it. More than one sequence may generate the same sign matrix. Every output integer may be any value from -10 through 10.

The first line contains the length n of the sequence (1 <= n <= 10). The second line contains a string of length n(n+1)/2. The string lists the upper-triangular part of the sign matrix in row order: the first n characters are the first row, the next n-1 characters are the second row, and so on, ending with the single character for the n-th row.

Print one line containing a sequence of n integers that generates the given sign matrix. If several sequences are possible, print any one of them. Every integer must be between -10 and 10, inclusive.