Product of all except self

Problem

In a hostel board game, each of n players holds a card with a whole number on it. A number can be negative or zero.

A player's bonus is the product of the numbers on all the other players' cards. Print the bonus of every player, in order.

Input: The first line has one integer n. The second line has n integers: the card numbers.
Output: One line with n integers separated by single spaces: the bonus of each player.
Constraints: 2 ≤ n ≤ 10^5
−10^9 ≤ card ≤ 10^9
Every bonus fits in a long (between −9 × 10^18 and 9 × 10^18)

Example 1

Input

4
1 2 3 4

Output

24 12 8 6

Player 1 gets 2 × 3 × 4 = 24, player 2 gets 1 × 3 × 4 = 12, and so on.

Example 2

Input

5
-1 1 0 -3 3

Output

0 0 9 0 0

Every player except the one holding 0 gets 0. That player gets −1 × 1 × −3 × 3 = 9.

Try the problem first. Open one hint at a time.

Hint 1

Multiplying all others for each player is O(n²). Can you reuse work between players?

Hint 2

Dividing the total product by the player's card fails as soon as a card is 0.

Hint 3

A player's bonus is (product of everything to the left) × (product of everything to the right).

Hint 4

Fill the left products in one pass from the start, then walk back from the end with a running right product. Use long for everything.

Write your Java code, run it on the examples and submit it to hidden tests.