Dados $n$ vectores bidimensionales $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$.

Puedes asignar a cada vector una dirección $c_i \in \{-1, +1\}$, y obtener la fuerza resultante $S = \sum\limits_{i=1}^n c_i (x_i, y_i)$.

Sea $S = (S_x, S_y)$, se define el cuadrado de la magnitud de la fuerza resultante como $|S|^2 = S_x^2 + S_y^2$.

Debes encontrar un conjunto de $c_i$ tal que $|S|^2 \leq 1.2 \sum\limits_{i=1}^n (x_i^2 + y_i^2)$, es decir, el cuadrado de la magnitud de la fuerza resultante no sea mayor que $1.2$ veces la suma de los cuadrados de las magnitudes de los vectores.

Se puede demostrar que bajo las restricciones de este problema siempre hay solución.

Restricciones

• $1 \leq n \leq 3 \times 10^5$
• Cada componente de todos los vectores es un entero cuyo valor absoluto no supera $10^9$.

Entrada

La primera línea de la entrada contiene un entero positivo $n$.

Las siguientes $n$ líneas contienen dos enteros cada una, que representan un vector bidimensional.

Salida

Debes imprimir una línea con $n$ enteros, que representan la dirección asignada a cada vector. Si la dirección es $+1$, imprime "1"; si la dirección es $-1$, imprime "-1" (sin comillas).

Ejemplos

Entrada 1

3
1 0
0 1
1 1

Salida 1

1 1 -1