Trả lời Q truy vấn tần suất trên miền nhỏ

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $a$ gồm $n$ số nguyên thuộc miền cố định

Với mỗi giá trị $x\in[0,1000]$, định nghĩa tần suất

Có $Q$ truy vấn $x_1,x_2,\ldots,x_Q$. Với mỗi truy vấn $x_j$, hãy in $f(x_j)$.

Mục tiêu là tiền xử lý một mảng freq[1001] một lần, sau đó trả lời mỗi truy vấn trong thời gian $O(1)$.

Input

Dòng đầu chứa $n$ và $Q$. Dòng thứ hai chứa $n$ số nguyên $a_i$. Dòng thứ ba chứa $Q$ số nguyên truy vấn $x_j$, tất cả thuộc $[0,1000]$.

Output

Với mỗi truy vấn, in tần suất tương ứng trên một dòng, theo đúng thứ tự truy vấn.

Subtask

Subtask 1 (20 điểm): $1\le n,Q\le10$.

Subtask 2 (30 điểm): $1\le n,Q\le5000$.

Subtask 3 (50 điểm): $1\le n,Q\le2\cdot10^5$.

Ví dụ

Input

8 5
2 5 2 0 5 5 7 2
5 2 1 0 7

Output

3
3
0
1
1

Giải thích

Ta có $f(5)=3$, $f(2)=3$, $f(1)=0$, $f(0)=1$, $f(7)=1$.