Given an array in of n integers. Build an array out such that outi is equal to the product of all the elements of in except ini. Solve it in O(n) and constant space complexity.

Input

First line contains number n (1 < n ≤ 106). Second line contains n integers, each number is not greater than 100 by absolute value.

Output

Print the out array. It is known that all printed values are not greater than 2 *109 by absolute value.