Thiết bị có độ phủ lỗi lớn nhất

Bối cảnh

Một trung tâm vận hành nhận m bản ghi lỗi, mỗi bản ghi gồm deviceId và errorCode. Một thiết bị có thể phát cùng lỗi nhiều lần hoặc nhiều loại lỗi khác nhau. Khi ưu tiên kiểm tra, đội kỹ thuật muốn chọn thiết bị có độ phủ lỗi lớn nhất, tức số lượng errorCode phân biệt mà thiết bị từng phát. Nếu nhiều thiết bị cùng số loại lỗi, thiết bị có tổng số bản ghi lỗi lớn hơn được ưu tiên; nếu vẫn hòa, chọn deviceId nhỏ hơn.

Sau khi chọn thiết bị, báo cáo phải liệt kê các errorCode phân biệt của nó theo thứ tự tăng dần. B15 chưa có sort, nhưng cấu trúc set đã cung cấp unique + ordered keys. Một representation tự nhiên là map<deviceId, set<errorCode>> để lưu độ phủ và một map khác cho tổng số bản ghi. Bài Advanced khó ở việc sử dụng nested container, đọc đúng ba tiêu chí lựa chọn và không nhầm "số bản ghi" với "số loại lỗi". Đây là mô hình group-by rất gần các bài dữ liệu trong Olympic/ICPC nhập môn.

Một cách tự kiểm tra mô hình dữ liệu là đặt câu hỏi: nếu cùng một thiết bị phát lỗi 10 một trăm lần thì distinct count vẫn chỉ tăng một, nhưng total count tăng một trăm. Nếu hai thiết bị có cùng distinct count nhưng một thiết bị phát lỗi dày đặc hơn, tiêu chí thứ hai mới phân biệt được chúng. Việc tách hai đại lượng này ngay từ representation giúp tránh bug "dùng size của set cho mọi thống kê" và khiến tie-break sau cùng trở nên minh bạch.

Yêu cầu

1. Đọc m cặp deviceId errorCode.
2. Với mỗi thiết bị, lưu tập errorCode phân biệt và tổng số bản ghi.
3. Chọn thiết bị theo: distinct errors lớn nhất → total records lớn nhất → deviceId nhỏ nhất.
4. In deviceId distinctCount totalCount.
5. Dòng 2 in các errorCode phân biệt tăng dần.

Yêu cầu tổ chức code

Không dùng sort; thứ tự error phải đến từ set.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng công cụ của buổi và không vượt prerequisite.

Input

Dòng 1 m; m dòng deviceId errorCode.

Output

Hai dòng như mô tả.

Ràng buộc

1≤m≤10000, |deviceId|,|errorCode|≤10^9.

Ví dụ 1

Input

8
1 10
1 20
1 10
2 5
2 6
2 7
3 1
3 1

Output

2 3 3
5 6 7

Giải thích

Thiết bị 1 có hai loại lỗi phân biệt {10,20} và tổng 3 bản ghi. Thiết bị 2 có ba loại {5,6,7} và tổng 3 bản ghi; thiết bị 3 chỉ có một loại. Vì distinct count của thiết bị 2 lớn nhất tuyệt đối, nó được chọn. Dòng đầu là 2 3 3; set của thiết bị 2 duyệt tăng dần nên dòng hai là 5 6 7.

Ví dụ 2

Input

6
5 1
5 1
4 2
4 3
6 9
6 8

Output

4 2 2
2 3

Giải thích

Thiết bị 5 có 1 loại lỗi và 2 bản ghi. Thiết bị 4 có 2 loại, 2 bản ghi; thiết bị 6 cũng có 2 loại, 2 bản ghi. Distinct và total hòa giữa 4 và 6 nên tie cuối chọn deviceId nhỏ hơn là 4. Các lỗi của 4 là 2 và 3, nên output 4 2 2 rồi 2 3.

Thông tin học tập

• Module: M05
• Buổi: B15
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: map, set, nested containers, distinct per key, frequency, multi-level tie-break
• Giới hạn kiến thức: B01-B15
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100