Product of Array Except Self

Medium#arrays #prefix-sums· solved by 0 · time limit 2.0 s

For each position print the product of all other elements — without using division (zeros make division fail).

Input

$n$ , then $n$ integers.

$n$ products.

$2 \le n \le 10^5$ ; every answer fits in a 64-bit integer.

Input

4
1 2 3 4

Output

24 12 8 6

Input

5
-1 1 0 -3 3

Output

0 0 9 0 0