Answer Q Frequency Queries on a Small Domain

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $n$ integers with $0\le a_i\le1000$, define

For each of $Q$ queries $x_j\in[0,1000]$, print $f(x_j)$. Precompute one frequency array and answer each query in $O(1)$.

Input

The first line contains $n$ and $Q$. The second line contains the array. The third line contains $Q$ query values, all in $[0,1000]$.

Output

For each query, print its frequency on a separate line in query order.

Subtask

Subtask 1 (20 points): $1\le n,Q\le10$.

Subtask 2 (30 points): $1\le n,Q\le5000$.

Subtask 3 (50 points): $1\le n,Q\le2\cdot10^5$.

Example

Input

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

Output

3
3
0
1
1

Explanation

The result follows directly from the mathematical definition above.