Product Array Puzzle

Given an array of integers, you are required to output a new array where the element at each index is the product of all the elements in the input array except the one at that index. Formally, given an input array a = [a₀, a₁, ..., aₙ₋₁], you need to compute an output array p such that [ p_i = \prod_{\substack{0 \leq j < n \ j \neq i}} a_j ] for every index i (0 (\leq) i < n). Note that even if the input contains zeros, the calculation should be done in a straightforward manner. Assume that the product fits in a 64-bit integer for the given constraints.

inputFormat

The input is read from STDIN. The first line contains a single integer n (0 (\leq) n (\leq) 10⁵) representing the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Print to STDOUT a single line containing n space-separated integers where the i-th integer is the product of all the input numbers except the one at the i-th index.## sample

4
1 2 3 4

24 12 8 6