Leaving the Bar

벡터 $\vec{v}$ = (x, y)에 대해 |v| = √{$x^2$ + $y^2$}로 정의한다.

Allen은 원점에 있는 술집에서 술을 조금 지나치게 많이 마셨다. n개의 벡터 $\vec{v_1}$, $\vec{v_2}$, ⋅⋅⋅, $\vec{v_n}$가 있다. Allen은 n번 이동한다. As Allen's의 방향 감각은 흐려져서, i-th번째 이동에서 $\vec{v_i}$ 방향 또는 -$\vec{v_i}$ 방향으로 이동한다. 다시 말해, 현재 위치가 p = (x, y)라면 p + $\vec{v_i}$ 또는 p - $\vec{v_i}$로 이동한다.

Allen은 집에서 너무 멀리 헤매고 싶지 않다. 공교롭게도 집은 술집이기도 하다. Allen이 안전하게 지낼 수 있도록, 최종 위치 p가 |p| ≤ 1.5 ⋅ $10^6$을 만족하게 하는 이동 순서, 즉 벡터에 붙일 부호의 순서를 찾도록 도와야 한다.

첫 번째 줄에 이동 횟수를 나타내는 하나의 정수 n가 주어진다 (1 ≤ n ≤ $10^5$).

이어지는 각 줄에는 공백으로 구분된 두 정수 $x_i$와 $y_i$가 주어지며, 이는 $\vec{v_i}$ = ($x_i$, $y_i$)임을 의미한다. 모든 i에 대해 |$v_i$| ≤ $10^6$이다.

각각 1 또는 -1인 n개의 정수 $c_1$, $c_2$, ⋅⋅⋅, $c_n$을 한 줄에 출력한다. p = ∑_{i = 1}^n $c_i$ $\vec{v_i}$의 값이 |p| ≤ 1.5 ⋅ $10^6$을 만족하면 정답으로 인정된다.

주어진 제한 조건에서 해가 항상 존재함을 보일 수 있다.