Finding a Sequence from a Sign Matrix

Time limit2sMemory limit128 MB

Summary

Given the sign pattern of all subarray sums of a hidden integer sequence, reconstruct one integer sequence (values -10 to 10) that produces the same sign matrix.

Level: Medium6 of 10
Topics: Prefix sum, Math, Sorting, Array
Solved: No attempts yet

Problem

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:

	1	2	3	4
1	-	+	0	+
2		+	+	+
3			-	-
4				+

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.

Input

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.

Output

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.

Examples3

Example 1
Input
```
4
-+0++++--+
```
Expected output
```
-2 5 -3 1
```
Example 2
Input
```
2
+++
```
Expected output
```
3 4
```
Example 3
Input
```
5
++0+-+-+--+-+--
```
Expected output
```
1 2 -3 4 -5
```