One day, Mikasa found a password consisting of numbers from $1-9$. She wants to know how conspicuous this password is to Allen. Allen has a visual threshold of $k$, and only the number whose length is not less than kkk can be noticed by him.

We define $f(x,S)$ as the number of occurrences of the number $x$ in the password $S$.

Then we define the conspicuousness $g(S)$ of a password $S$:

$g(S) = \max_{x \in S, \ |x|≥k}{f(x,S)}$

Noticed: $x \in S$ means number $x$ is a subnumber of the password $S$. For example, $23 \in 1234$ is true and $24 \in 1234$ is not.

Since Mikasa does not know the visual threshold $k$, please help calculate the conspicuousness $g(S)$ under the $q$ kinds of situations.

The first line contains two positive integers $n(1\leq n\le3e5)$ and $q(1\leq q\le3e5)$, indicating the length of the password and the number of situations;

The second line contains a number with a length of $n$, which represents the password discovered by Mikasa;

In the next $q$ line, each line has a positive integer $k(1\leq k \le n)$, which represents the visual threshold of Allen.

The output should contain $q$ lines, each representing the conspicuousness $g(S)$ in different situations.