Sign Normalization

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given an integer array $A=(a_0,a_1,\ldots,a_{n-1})$, replace each value by its sign:

$$s_i=\begin{cases} -1,&a_i<0,\\ 0,&a_i=0,\\ 1,&a_i>0. \end{cases}$$

Print $S=(s_0,s_1,\ldots,s_{n-1})$.

Input

• The first line contains $n$.
• The second line contains $n$ integers $a_i$.

Output

Print one line containing $n$ values from $\{-1,0,1\}$ separated by single spaces.

Subtasks

Subtask 1 (100 points): $1\le n\le10^5$ and $-10^{18}\le a_i\le10^{18}$.

Examples

Input

7
-5 0 8 -1 1 0 20

Output

-1 0 1 -1 1 0 1

Explanation

Negative values -5 and -1 become -1; zeros remain 0; positive values 8, 1, and 20 become 1.