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 ≤ N ≤ 10^5) và Q (1 ≤ Q ≤ 10^5).
• Dòng thứ hai chứa N số nguyên A_i (-10^9 ≤ A_i ≤ 10^9).
• Q dòng tiếp theo, mỗi dòng chứa số nguyên X_j (-10^9 ≤ X_j ≤ 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