An assembly line has n stations. Station i multiplies the throughput by a[i]. For each station, an engineer wants to know the combined factor of all the other stations — the product of every value except a[i].
Print these n products. Do it without division (some factors are 0).
Constraints
- 2 ≤ n ≤ 12
- −9 ≤ a[i] ≤ 9
Input and output
- Input
- The first line has n. The second line has n integers.
- Output
- n integers on one line, separated by spaces.
Examples
Input 1
4
2 3 4 5Output
60 40 30 24For index 0: 3×4×5 = 60, and so on.
Input 2
4
1 0 3 4Output
0 12 0 0Every product that includes the 0 is 0.
Show hints
- The product of everything except a[i] = (product of everything to its left) × (product of everything to its right).
- Build the left products in one pass and multiply in the right products in a second pass.
Show the explanation
Division fails as soon as one value is 0, so build the answer from prefix and suffix products instead. After a left-to-right pass, out[i] holds the product of a[0..i-1]; a right-to-left pass multiplies in the product of a[i+1..n-1], kept in a single running variable.
Two passes, O(n) time, and O(1) extra space besides the output.
Original UniCircle question. Last reviewed 22 Oct 2026.