Thị trưởng

Xem dạng PDF

Gửi bài giải

Điểm: 1,04 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Russian Training / vCoder.08
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một đất nước có ~N~ thành phố, vị trí của mỗi thành phố được thể hiện bởi một điểm trên mặt phẳng tọa độ. Tổng thống vừa đắc cử muốn bổ nhiệm mỗi thành phố một thị trưởng. Tổng thổng muốn bổ nhiệm cả các thị trưởng nam và nữ. Với mỗi đường thẳng ngang hoặc dọc (song song với trục tọa độ), gọi độ bình đẳng giới là trị tuyệt đối của hiệu giữa số thị trưởng nam và thị trưởng nữ của các thành phố nằm trên đường thẳng đó.

Để chứng tỏ tinh thần bình đẳng giới của đất nước, tổng thống muốn bổ nhiệm các thị trưởng sao cho tổng độ bình đẳng giới đối với các đường thẳng ngang và dọc là nhỏ nhất.

Bạn hãy viết chương trình giúp tổng thống thực hiện nhiệm vụ này.

Input

  • Dòng đầu tiên chứa ~N~ ~(1 \leq N \leq 20000)~, số thành phố của đất nước.
  • Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa hai số nguyên ~x_{i}~, ~y_{i}~ là tọa độ của thành phố thứ ~i~ ~(x_{i}~, ~y_{i}~ thuộc phạm vi số nguyên ~32~ bit).

Output

  • In ra ~N~ dòng, dòng thứ ~i~ chứa số nguyên ~0~ hoặc ~1~ tương ứng với việc cần bổ nhiệm thị trưởng nam hay nữ cho thành phố.

Sample Input

5
0 0
0 1
1 0
1 1
1 2

Sample Output

0
1
1
0
1

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.