eolymp
bolt
Try our new interface for solving problems
Problems

Product of Array Except Self

Product of Array Except Self

Time limit 1 second
Memory limit 128 MiB

Given an array in of n integers. Build an array out such that out_i is equal to the product of all the elements of in except in_i.

Input data

The first line contains number n~(1 < n \le 10^6). The second line contains n integers, each number is not greater than 100 by absolute value.

Output data

Print the out array. It is known that all printed values are not greater than 2 \cdot 10^9 by absolute value.

Examples

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
Input example #11
10
-3 2 1 -1 1 -2 1 -1 1 -1
Output example #11
4 -6 -12 12 -12 6 -12 12 -12 12