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.