Giải bài trực tuyến

Để khoe khoang sự giàu có của mình, các thương gia đã dem các toà biệt thự ra so sánh. Sau khi họp bàn và tranh luận căng thẳng, các thương gia chọn ra 2 tiêu chí được xem là quan trọng nhất cho mỗi toà nhà đó là khoảng cách tới mặt đường (nhà mặt phố hiển nhiên có giá trị hơn nhà trong ngõ) và số tầng cao của toà nhà. Ngôi nhà của thương nhân A được coi là hoành tráng hơn ngôi nhà của thương nhân B nếu nó gần mặt đường hơn và có nhiều tầng hơn. Các thương gia tiến hành phân loại các ngôi nhà như sau: Toà nhà A là toà nhà loại 1 nếu không có toà nhà nào hoành tráng hơn A; sau khi loại bỏ các toà nhà loại 1, toà nhà B là toà nhà loại 2 nếu không có toà nhà nào hoành tráng hơn B; sau khi bỏ đi các toà nhà loại 1 và loại 2, toà nhà C là toà nhà loại 3 nếu không có toà nhà nào hoành tráng hơn C,... Việc phân loại tiếp tục cho đến khi mọi toà nhà đều được xếp hạng.

Các thương gia rất nóng lòng muốn biết toà nhà của minh bỏ bạc tỷ ra xây được xếp hạng bao nhiêu. Do đó bạn được thuê với số tiền là 1.000.000 $ để viết một chương trình xếp loại các toà nhà không quá 1 giây.

Input

- Dòng đầu là số nguyên dương n (n≤30000).

- Dòng thứ i trong n dòng tiếp theo ghi hai số nguyên dương di, hi (0

Output

Gồm n dòng, dòng thứ i ghi một số nguyên dương là loại của toà nhà thứ i.

Example

Input:
3

1 2

2 1

1 3

Output:

1

2

1