Giải thi đấu võ Karate, cả nam lẫn nữ có tất cả n vận động viên được xếp thành một hàng ngang đánh số từ 1 đến n. Vận động viên thứ i có năng lực chiến đấu là một số nguyên ai.

Trưởng ban tổ chức muốn chọn ra một số vận động viên đại diện cho tỉnh mình để tham gia giải đấu toàn quốc nhưng ông ta chưa biết chọn thế nào, đành cho các vận động viên của mình đấ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ận động viên sẽ được đấu với các vận động viên đứng trước họ từ gần đến xa, đến khi nào thua trận thì thôi. (Vận động viên thứ i chỉ đấu thắng vận động viên thứ j nếu ai > aj).

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

Input:

-Dòng 1: Chứa số nguyên dương n<=10^6 là số lượng võ sỹ nhà dế mèn.

-n dòng sau: Mỗi dòng chứa hai số nguyên, dòng thứ i+1 chứa số nguyên ai, bi là năng lực chiến đấu và giới tính của võ sĩ i (0 < ai ≤ 10^9, 0 ≤ bi ≤ 1).

Output:

Môt dòng gồm n số nguyên số thứ i là số lượng vận động viên mà vận động viên thứ i sẽ được chiến đấu với vận động viên i thắng trận.

Sample Input

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

Sample Output

0 0 1 2 0 0 0 0 1 2