e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Product of Array Except Self

Product of Array Except Self

Given an array in of n integers. Build an array out such that outi is equal to the product of all the elements of in except ini. Solve it in O(n) and constant space complexity.

Input

First line contains number n (1 < n106). Second line contains n integers, each number is not greater than 100 by absolute value.

Output

Print the out array. It is known that all printed values are not greater than 2 *109 by absolute value.

Time limit 2 second
Memory limit 128 MiB
Input example #1
4
1 2 3 4
Output example #1
24 12 8 6
Input example #2
4
2 0 1 4
Output example #2
0 8 0 0