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은 집(공교롭게도 술집이기도 하다)에서 너무 멀리 돌아다니고 싶지 않다. 그가 안전하게 지낼 수 있도록, 최종 위치 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$을 만족하면 답은 올바르다.

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