Product Array Puzzle

You are given an array A of N non-negative integers. Your task is to construct a new array R, where the element at index i is equal to the product of all the numbers in A except the one at index i.

Note: For an array with a single element, the product of the empty set is defined as 1. Also, be careful when the array contains one or more zeros.

Example 1:

Input: 5
       1 2 3 4 5
Output: 120 60 40 30 24

Example 2:

Input: 3
       3 2 1
Output: 2 3 6

Solve this problem using the most efficient method possible.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer N, the number of elements in the array. (0 ≤ N ≤ 10^5)
• If N > 0, the second line contains N space-separated non-negative integers representing the array A.

outputFormat

Output on standard output (stdout) a single line with N space-separated integers, where the i-th integer is the product of all elements of A except A[i]. If N is 0, output nothing.

## sample

5
1 2 3 4 5

120 60 40 30 24