Product Array Except Self

Given an array of integers, the task is to output a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i. You are not allowed to use division in your solution.

Input Format: The first line contains an integer n, the number of elements. The second line contains n space-separated integers.

Output Format: Print the resulting array as space separated integers in one line.

Example

Input: 4 1 2 3 4

Output: 24 12 8 6

Note: Use the two-pass algorithm to compute the product of all elements to the left and right of each index.

inputFormat

The input consists of two lines:

• The first line contains a single integer n, representing the number of elements in the array.
• The second line contains n space-separated integers.

outputFormat

Output a single line containing n integers where the ith integer is the product of all the numbers in the input array except the number at index i.

## sample

4
1 2 3 4

24 12 8 6