Product of Array Except Self

For every position i, compute the product of all elements except A[i]. Do not use division. (Constraints are kept small so every product fits in a 64-bit integer.)

Input Format

The first line contains an integer N. The second line contains N space-separated integers.

Output Format

Print N space-separated integers, where the i-th value is the product of every element except the i-th.