Tại câu lạc bộ võ Karate, cả nam lẫn nữ có tất cả ~ n ~ võ sinh được xếp thành một hàng đánh số từ 1 đến ~ n ~. Võ sinh thứ ~ i ~ có năng lực chiến đấu là một số nguyên ~ a_i ~. Huấn luyện viên muốn cho các võ sinh của mình đấu giao hữu với nhau theo nguyên tắc như sau:

• Chỉ thi đấu với nhau khi cùng giới tính.
• Mỗi võ sinh sẽ được đấu với các võ sinh đứng trước họ từ gần đến xa, đến khi nào thua trận thì thôi. (Võ sinh thứ ~ i ~ thắng võ sinh thứ ~ j ~ nếu ~ j<i ~ và ~ a_j<a_i ~).

Yêu cầu: Hãy cho biết, mỗi võ sinh thắng bao nhiêu võ sinh khác theo nguyên tắc trên.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~ n (n ≤ 10^6) ~ là số lượng võ sinh.

• ~ n ~ dòng sau, mỗi dòng chứa hai số nguyên, dòng thứ ~ i+1 ~ chứa số nguyên ~ a_i ~ và ~ b_i ~, trong đó ~ a_i ~ là năng lực chiến đấu, ~ b_i ~ là giới tính của võ sinh thứ ~ i (1≤ a_i ≤ 10^9, b_i ∈ {0,1}) ~.

Kết quả:

• Ghi một dòng duy nhất gồm ~ n ~ số nguyên, số thứ ~ i ~ là số lượng võ sinh mà võ sinh thứ ~ i ~ đấu thắng.

Ví dụ:

Input

10
5 0
18 1
11 0
12 0
4 0
12 1
3 0
2 1
7 1
6 0 

Output

0 0 1 2 0 0 0 0 1 2 

Ràng buộc:

• 40% số test với ~ n ≤ 10^3 ~
• 60% số test với ~ n ≤ 10^6 ~