Rời quán bar

Cho $n$ vector $\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n}$ trên mặt phẳng. Bạn bắt đầu tại gốc tọa độ $(0,0)$ và thực hiện $n$ bước di chuyển. Ở bước thứ $i$, bạn được chọn một dấu $c_i\in \{-1,+1\}$ rồi cộng vector $c_i·\overrightarrow{v_i}$ vào vị trí hiện tại.

Gọi vị trí cuối cùng là $\overrightarrow{p}={\sum }_{i=1}^n{c}_i·\overrightarrow{v_i}$. Hãy tìm một dãy dấu $c_1,c_2,\dots ,c_n$ sao cho

$$|\overrightarrow{p}|\le 1.5·{10}^6,$$

trong đó $|\overrightarrow{v}|=\sqrt{x^2+y^2}$ là độ dài Euclid của vector.

Có thể chứng minh rằng với mọi dữ liệu thỏa mãn ràng buộc, luôn tồn tại ít nhất một dãy dấu hợp lệ. Nếu có nhiều đáp án, bạn được phép in ra bất kỳ đáp án nào.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số vector.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$ — tọa độ của vector $\overrightarrow{v_i}=(x_i,y_i)$.

Dữ liệu ra

In ra $n$ số $c_1,c_2,\dots ,c_n$ trên một dòng, mỗi số bằng $1$ hoặc $-1$, sao cho vector tổng $\overrightarrow{p}=\sum c_i\overrightarrow{v_i}$ thỏa $|\overrightarrow{p}|\le 1.5·{10}^6$.

Nếu có nhiều đáp án hợp lệ, in ra bất kỳ đáp án nào trong số đó.

Ràng buộc

• $1\le n\le {10}^5$
• $|\overrightarrow{v_i}|\le {10}^6$ với mọi $i$
• Tọa độ $x_i,y_i$ là các số nguyên

Ví dụ