EIU Programming Practices and Exams

Công ty B đang triển khai một hệ thống wifi mới, tuy nhiên do đang trong giai đoạn thử nghiệm nên hệ thống phát sinh khá nhiều lỗi. Công ty cần phát triển một phần mềm ghi nhận lỗi từ khách hàng để thống kê và báo cáo cho nhóm phát triển sửa lỗi. Khi hoạt động, hệ thống sẽ nhận vào thông báo lỗi hoặc trả lời số lượng lỗi theo yêu cầu. Bạn được yêu cầu xây dựng chức năng của phần mềm trên, yêu cầu khai báo và hiện thực class ErrorStatistic, và viết chương trình kiểm tra. Class ErrorStatistic hỗ trợ các phương thức sau:

1. addError(int errorType, int errorId): Thông báo lỗi xảy ra với tham số loại lỗi (errorType) và mã lỗi (errorId).

2. countError(int errorType): Tính tổng số lỗi của một loại (từ khi bắt đầu hoạt động).

3. countError(int errorType, int nError): Tính tổng số lỗi của một loại (errorType) trong số nError lỗi gần nhất.

4. getErrors(int errorType, int nError): Trả về danh sách nError lỗi gần nhất của một loại (errorType).

Input

Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁵) - số yêu cầu hệ thống sẽ nhận.

Mỗi dòng trong n dòng tiếp theo mô tả một yêu cầu. Số đầu tiên của dòng cho biết loại của yêu cầu (1 ≤ t ≤ 4).

• Nếu t = 1, tiếp theo sẽ có 2 số nguyên x và y: Thông báo cho hệ thống thêm vào lỗi loại x, mã lỗi là y (addError).
• Nếu t = 2, tiếp theo sẽ có số nguyên k: Yêu cầu in ra tổng số lỗi loại k (countError) từ khi bắt đầu hoạt động.
• Nếu t = 3, tiếp theo sẽ có 2 số nguyên x và n (n ≤ 100): Yêu cầu in ra tổng số lỗi loại x trong số n lỗi gần nhất.
• Nếu t = 4, tiếp theo sẽ có 2 số nguyên x và n (n ≤ 100): Yêu cầu in ra danh sách n lỗi gần nhất của loại x theo thứ tự gần nhất đến xa nhất.

Output

 Với mỗi truy vấn thuộc loại 2, 3 hoặc 4 in ra kết quả tương ứng, mỗi kết quả trên một hàng.

Example

Input: 

7

1 2 1

1 2 3

2 2

3 3 2

1 3 2

3 3 2

4 2 2

Output:

2

0

1

3

1

* Giải thích:

- Truy vấn 2 2: Có hai lỗi loại 2 đã thêm vào (mã số 1, 3)

- Truy vấn 3 3 2: Chưa có lỗi loại 3 trong hệ thống

- Truy vấn 3 3 2: Có một lỗi loại 3 trong số 2 lỗi cuối cùng mới thêm vào (3, 2)

- Truy vấn 4 2 2: Xuất ra 2 lỗi loại 2 theo thứ tự gần nhất đến xa nhất