Product of Array Except Self

Given an array of integers, compute a new array such that each element at index (i) is the product of all the elements in the original array except the one at (i).

Formally, if the input array is (arr) with (n) elements, you are required to compute an output array (output) where [ output_i = \prod_{\substack{0 \leq j < n \ j \neq i}} arr_j ]

Note: You must solve the problem without using division.

inputFormat

The input is read from standard input and consists of two lines. The first line contains an integer (n), which denotes the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Print to standard output a single line with (n) space-separated integers, where the (i)-th integer is the product of all elements in the input array except the one at index (i).## sample

4
1 2 3 4

24 12 8 6