Conspicuousness

题号：NC222866
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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$ :

$\\ \\ \displaystyle 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  and , indicating the length of the password and the number of situations;

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

In the next  line, each line has a positive integer , which represents the visual threshold of .

输出描述:

The output should contain  lines, each representing the conspicuousness  in different situations.

示例1

输入

复制

输出

复制

2
1

示例2

输入

复制

输出

复制

1
2