Product of Array Except Self

Given an array nums consisting of n integers, compute an output array where each element output[i] is equal to the product of all the numbers in nums except nums[i]. You must solve this problem in O(n) time without using division. The result of the product is defined as:

\(output[i] = \prod_{j=0, j\neq i}^{n-1} nums[j]\)

Read the input from stdin and write your result to stdout as a single line with the numbers separated by spaces.

inputFormat

The first line contains an integer n which denotes the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single line containing n space-separated integers, where the i-th integer is the product of all the elements of the input array except the element at index i.## sample

4
1 2 3 4

24 12 8 6