Cho $n$ vector hai chiều $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$.

Bạn có thể gán cho mỗi vector một hướng $c_i \in \{-1, +1\}$ và cuối cùng thu được hợp lực $S = \sum\limits_{i=1}^n c_i (x_i, y_i)$.

Đặt $S = (S_x, S_y)$, định nghĩa bình phương độ lớn của hợp lực là $|S|^2 = S_x^2 + S_y^2$.

Bạn cần tìm một bộ $c_i$ sao cho $|S|^2 \leq 1.2 \sum\limits_{i=1}^n (x_i^2 + y_i^2)$, tức là bình phương độ lớn của hợp lực không lớn hơn $1,2$ lần tổng bình phương độ dài các vector.

Có thể chứng minh rằng trong các ràng buộc của bài toán, luôn tồn tại nghiệm.

Giới hạn

$1 \leq n \leq 3 \times 10^5$

Tất cả các tọa độ của các vector đều là số nguyên có trị tuyệt đối không vượt quá $10^9$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào là một số nguyên dương $n$. $n$ dòng tiếp theo, mỗi dòng hai số nguyên biểu diễn một vector hai chiều.

Dữ liệu ra

Bạn cần in ra một dòng gồm $n$ số nguyên, thể hiện hướng bạn gán cho các vector. Nếu hướng là $+1$, in ra "1"; nếu hướng là $-1$, in ra "-1" (cả hai đều không có dấu ngoặc kép).

Ví dụ

Dữ liệu vào 1

3
1 0
0 1
1 1

Dữ liệu ra 1

1 1 -1