Description

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 k 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∈S, |x|≥k） f(x, S)

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

Since M ikasa does not know the visual threshold k, please help calculate the conspicuousness g(S) under the q

Input

The first line contains two positive integers n(1 ≤ n ≤ 3 ∗ 10e5) and q(1 ≤ q ≤ 3 ∗ 10e5), 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 M ikasa; In the next q line, each line has a positive integer k(1 ≤ k ≤ n), which represents the visual threshold of Allen.

Output

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

3 2
131
1
2

2
1