Para cada posición \(i\), calcula el producto de todos los elementos del arreglo excepto \(a_i\).

Tu algoritmo debe correr en \(O(n)\) sin usar la división. (El juez no puede verificarlo: es parte del ejercicio.)

Entrada

La primera línea tiene \(n\) \((2 \le n \le 10^5)\) y la segunda los \(n\) enteros \((|a_i| \le 30)\). El producto de cualquier prefijo o sufijo del arreglo cabe en un entero de 32 bits con signo.

Salida

Una línea con los \(n\) productos.

Ejemplo 1

Entrada

4
1 2 3 4

Salida

24 12 8 6

Ejemplo 2

Entrada

5
-1 1 0 -3 3

Salida

0 0 9 0 0

Basado en el problema 238 de LeetCode, Product of Array Except Self, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.