Prefix Relay Log

Time limit: 3000 msMemory limit: 256 MB

A communication log is represented by a string $S$ of length $N$ , indexed from $1$ through $N$ . Relays may begin whenever the start of the log appears again.

Choose a nonempty prefix length $L$ , where $1 \le L \le N$ . A position $i$ , where $1 \le i \le N-L+1$ , is an occurrence start for this prefix if

S_iS_{i+1}\ldots S_{i+L-1}=S_1S_2\ldots S_L.

Write all occurrence starts in increasing order as

p_1 < p_2 < \ldots < p_k.

The prefix itself always occurs at the beginning, so $p_1=1$ . Append a terminal marker $p_{k+1}=N+1$ . This marker is not another occurrence; it represents the moment immediately after the log ends.

The relay gap of prefix length $L$ is

G_L=\max_{1 \le r \le k}(p_{r+1}-p_r).

Each query gives a tolerance $D$ . A prefix length $L$ qualifies for that query when $G_L \le D$ . Determine the largest qualifying prefix length. If no nonempty prefix qualifies, the answer is $0$ .

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N, Q \le 2 \cdot 10^5$ ), the length of the log and the number of queries.

Output

For each of the $Q$ queries, print one integer: the largest prefix length $L$ satisfying $G_L \le D_j$ for that query. If no nonempty prefix satisfies the condition, print .

Samples

Sample 1

Input

5 4
ababa
1
2
3
5

Output

For $D=1$ , no nonempty prefix qualifies. For $D=2$ , $D=3$ , and $D=5$ , the longest qualifying prefixes have lengths , , and , respectively.

Prefix Relay Log

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2