$n$개의 2차원 벡터 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$가 주어집니다.

각 벡터에 $c_i \in \{-1, +1\}$인 방향을 할당하여 최종 합력 $S = \sum\limits_{i=1}^n c_i (x_i, y_i)$을 얻을 수 있습니다.

$S = (S_x, S_y)$라 할 때, 합력 크기의 제곱을 $|S|^2 = S_x^2 + S_y^2$로 정의합니다.

$|S|^2 \leq 1.2 \sum\limits_{i=1}^n (x_i^2 + y_i^2)$, 즉 합력 크기의 제곱이 벡터 길이 제곱의 합의 $1.2$배 이하가 되도록 하는 $c_i$의 집합을 찾아야 합니다.

이 문제의 제약 조건 하에서는 항상 해가 존재함을 증명할 수 있습니다.

제한

• $1 \leq n \leq 3 \times 10^5$
• 모든 벡터의 각 성분은 절댓값이 $10^9$을 넘지 않는 정수입니다.

입력

입력의 첫 번째 줄에는 양의 정수 $n$이 주어집니다. 다음 $n$개의 줄에는 각각 두 개의 정수가 주어지며, 이는 하나의 2차원 벡터를 나타냅니다.

출력

$n$개의 정수를 한 줄에 출력해야 합니다. 이는 각 벡터에 할당한 방향을 나타냅니다. 방향이 $+1$이면 "1"을, $-1$이면 "-1"을 출력합니다 (따옴표 제외).

예제

입력 1

3
1 0
0 1
1 1

출력 1

1 1 -1