Tần suất bằng map

Bối cảnh

Một hệ thống ghi nhận các mã lỗi. Nhiều mã có thể xuất hiện lặp lại và bạn cần trả lời tần suất của từng mã được hỏi.

map<value,count> mô tả trực tiếp quan hệ mã lỗi → số lần xuất hiện.

Yêu cầu

1. Đếm tần suất n số bằng map.
2. Đọc q truy vấn x.
3. Mỗi truy vấn in x count.

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

Ưu tiên find()/count() trong phần truy vấn để luyện tránh side effect của operator[].

Online Judge chấm output. Với bài nhạy về cấu trúc lời giải, giảng viên có thể review source code để xác nhận học viên luyện đúng năng lực.

Input

Dòng 1 n; dòng 2 n số; dòng 3 q; q dòng, mỗi dòng một x.

Output

q dòng x count.

Ràng buộc

1≤n,q≤2000, |x|≤10^9.

Ví dụ 1

Input

5
5 1 5 2 1
4
1
5
3
2

Output

1 2
5 2
3 0
2 1

Giải thích

Từ dãy 5 1 5 2 1, map tần suất nhận các cặp 1→2, 2→1, 5→2. Truy vấn 1 trả 2, truy vấn 5 trả 2. Giá trị 3 không có trong map nên trả 0, còn 2 xuất hiện một lần. Vì thế bốn dòng output lần lượt là 1 2, 5 2, 3 0, 2 1.

Ví dụ 2

Input

1
7
2
7
8

Output

7 1
8 0

Giải thích

Dữ liệu chỉ có một mã 7, vì vậy freq[7]=1. Khi truy vấn 7, chương trình tìm thấy key và in 7 1. Truy vấn 8 không tồn tại; dùng find() giúp kiểm tra mà không vô tình tạo key mới, nên kết quả là 8 0.

Thông tin học tập

• Module: M05
• Buổi: B15
• Loại bài: LAB
• Độ khó: Easy
• Concepts: map, frequency, key-value, query
• Giới hạn kiến thức: B01-B15
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100