Ridiculous Queries

A sequence of integers $p_1,p_2,\dots ,p_n$ is called a permutation if the sequence contains each integer from $1$ to $n$ exactly once. For example, $[1,5,3,4,2]$ is a permutation. However, $[1,3,4]$ is not a permutation (it doesn't contain $2$ and contains $4$) and $[1,2,2,3]$ is not a permutation as well (it contains $2$ twice and doesn't contain $4$).

You are given a permutation $p_1,p_2,\dots ,p_n$.

Let $p_i^k=\underset{\text{k times}}{\underbrace{p[p[\dots [i]\dots ]]}}$. For example: $p_i^1=p[i]$ and $p_i^2=p[p[i]]$.

Your task is to answer $q$ queries. For a certain number $k$, determine $\underset{1\le i\le n}{\max }(p_i^k+i)$. In other words, determine the maximum value of $p_i^k+i$ where $1\le i\le n$.

Input

The first line contains two integers $n$ and $q$ $(1\le n\le 1000;1\le q\le 10^6)$ — the length of $p$ and the number of queries, respectively.

The next line contains $n$ integers $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$) — elements of the permutation $p$. It is guaranteed that $p$ is a permutation.

Each of the next $q$ lines contains a single integer $k$ $(1\le k\le 10^9)$.

Output

For each query, output the desired maximum.

Examples

Note

In the first example, we have a permutation $p=[4,1,5,2,3]$.

The first query is $k=1$, hence we must find

The second query is $k=2$. The answer is

Scoring

1. ($3$ points): $p=[1,2,\dots ,n]$;

2. ($5$ points): $q\le 10$ and $k\le 100$;

3. ($7$ points): $k\le 100$;

4. ($5$ points): for each pair $1\le i,j\le n$ there exists $k$ that $p_i^k=j$;

5. ($16$ points): $n\le 20$;

6. ($31$ points): $q\le 10^4$;

7. ($33$ points): no additional restrictions.