Trong một giải võ Karate toàn quốc có ~n~ vận động viên (cả nam lẫn nữ) đứng thành một hàng ngang, đánh số từ ~1~ đến ~n~. Vận động viên thứ ~i~ có sức mạnh là số nguyên ~a_i~.

Các trận đấu được tổ chức theo quy tắc sau:

• Hai vận động viên chỉ đấu với nhau khi cùng giới tính.
• Mỗi vận động viên lần lượt đấu với những người đứng trước mình, từ người gần nhất ra xa dần, và dừng lại ngay khi thua một trận. Vận động viên ~i~ chỉ thắng vận động viên ~j~ khi ~a_i > a_j~.

Yêu cầu: với mỗi vận động viên, hãy cho biết họ thắng tổng cộng bao nhiêu vận động viên theo quy tắc trên.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~) là số vận động viên.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i, b_i~ (~0 < a_i \le 10^9~, ~0 \le b_i \le 1~) lần lượt là sức mạnh và giới tính của vận động viên thứ ~i~.

Kết quả

In ra một dòng duy nhất gồm ~n~ số nguyên, số thứ ~i~ là số vận động viên mà vận động viên thứ ~i~ thắng.

Ví dụ

KARATE.INP

10
9 0
18 1
11 0
12 0
3 0
12 1
2 0
2 1
7 1
6 0

KARATE.OUT

0 0 1 2 0 0 0 0 1 2

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 5 \times 10^3~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.