Minimum Positive Linear Combination

Given an integer sequence (A) of length (n) with elements (A_1, A_2, \dots, A_n), find an integer sequence (X) of the same length such that (S = \sum_{i=1}^n A_i \times X_i > 0) and (S) is as small as possible. By Bézout's identity the minimum positive (S) that can be obtained is [ \gcd(A_1, A_2, \dots, A_n), ] so you are required to output a sequence (X) satisfying [ \sum_{i=1}^n A_i \times X_i = \gcd(A_1, A_2, \dots, A_n)] Note that the (X_i)'s may be negative, zero, or positive.

inputFormat

The input consists of two lines. The first line contains a single integer (n) ((1 \le n \le 10^5)), the number of elements in the sequence. The second line contains (n) space-separated integers (A_1, A_2, \dots, A_n). It is guaranteed that not all (A_i) are zero.

outputFormat

Output a single line containing (n) space-separated integers (X_1, X_2, \dots, X_n) such that (S = \sum_{i=1}^n A_i \times X_i) is positive and as small as possible, i.e. equal to (\gcd(A_1, A_2, \dots, A_n)).

sample

2
4 6

-1 1