Cho mảng A gồm N số nguyên và Q truy vấn. Với mỗi truy vấn \(X_j\), hãy đếm số lần \(X_j\) xuất hiện trong A.

Sử dụng hash map (bảng băm) để lưu tần số của từng giá trị, sau đó trả lời mỗi truy vấn trong \(O(1)\).

Đầu vào

• Dòng đầu tiên chứa hai số nguyên N (\(1 \le N \le 10^5\)) và Q (\(1 \le Q \le 10^5\)).
• Dòng thứ hai chứa N số nguyên \(A_i\) (\(-10^9 \le A_i \le 10^9\)).
• Q dòng tiếp theo, mỗi dòng chứa số nguyên \(X_j\) (\(-10^9 \le X_j \le 10^9\)).

Đầu ra

Với mỗi truy vấn, in ra số lần xuất hiện của \(X_j\) trong A trên một dòng riêng.

Ví dụ

Input:
8 4
3 1 4 1 5 9 2 6
1
3
7
4

Output:
2
1
0
1

Ràng buộc & Subtasks