Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is the product of all elements except nums[i]. Solve in O(n) without using division. Algorithm: Two passes - left products then right products. Example: [1,2,3,4] → [24,12,8,6] (24=2*3*4, 12=1*3*4, 8=1*2*4, 6=1*2*3)

Input

Line 1: n. Line 2: n space-separated integers.

Output

n space-separated integers (products except self).

Sample

4
1 2 3 4

Expected

24 12 8 6