Xếp hạng và mã hóa mức điểm

Bối cảnh và bài toán

Một hệ thống nhận n hồ sơ thi đấu. Mỗi hồ sơ có score và penalty; ID hồ sơ chính là thứ tự nhập từ 1 đến n. Khi xuất báo cáo, hồ sơ phải được sắp theo score giảm dần, nếu bằng nhau thì penalty tăng dần, nếu vẫn bằng thì ID tăng dần.

Đồng thời hệ thống cần lưu score dưới dạng mã compact: score nhỏ nhất nhận mã 0, score phân biệt tiếp theo nhận 1, ...; các score bằng nhau có cùng mã.

Yêu cầu

In các hồ sơ theo thứ tự xếp hạng; trên mỗi dòng in id compressed_score.

Input

• Dòng 1: n.
• n dòng tiếp: score penalty của hồ sơ theo ID 1..n.

Output

In n dòng theo thứ tự xếp hạng, mỗi dòng gồm ID gốc và mã score đã nén.

Ràng buộc

• 1 <= n <= 2 * 10^5
• |score| <= 10^9
• 0 <= penalty <= 10^9

Chấm điểm

Ví dụ 1

Input

5
100 30
200 50
100 20
300 80
200 40

Output

4 2
5 1
2 1
3 0
1 0

Giải thích. Các score phân biệt là 100,200,300 nên mã lần lượt 0,1,2. Thứ tự ranking là 300 trước, rồi hai hồ sơ 200 theo penalty, sau đó hai hồ sơ 100.

Ví dụ 2

Input

3
10 5
10 5
20 9

Output

3 1
1 0
2 0

Giải thích. Hai hồ sơ đầu hòa cả score và penalty nên ID nhỏ hơn đứng trước.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.