Football

There are $n$ players in a football team, numbered with integers from $1$ to $n$. The skill level of player with number $i$ is described by the integer $c_i$.

The players are arranged in a circle in such a way that the player with number $i$ has the player with number $i+1$ on their right side (for $1\le i<n$), and for the player with number $n$, the next player is the one with number $1$.

Let's define the strength of a game combination, characterized by an array of integers $k=[k_0,k_1,k_2,\dots ,k_{m-1}]$, as follows:

• initially, the ball is with the player with number $1$;

• the players pass the ball in turns indefinitely: when performing the pass with number $i$, the player who currently has control of the ball passes it to the player located $x$ positions to the right in the circle, where $x=k_{((i-1)\mathrm{mod}m)}$;

• the strength of the game combination is considered to be the minimum skill level among the skills of all players who had the ball at some point during the described process.

An array of integers $a_0,a_1,\dots ,a_{q-1}$ is given. For each $i$ from $0$ to $(q-1)$, find the strength of the game combination characterized by the array $[a_0,a_1,\dots ,a_i]$.

Input

The first line contains two integers $n$ and $q$ $(1\le n,q\le 3\cdot {10}^5)$ — the number of players and the length of the array $a$.

The second line contains $n$ integers $c_1,c_2,\dots ,c_n$ $(1\le c_i\le n)$ — the skill levels of the players.

The third line contains $q$ integers $a_0,a_1,\dots ,a_{q-1}$ $(1\le a_i\le n-1)$ — the elements of the array $a$.

Output

Output $q$ integers — the sought values of the strengths of game combinations.

Examples

Note

In the example of passing the ball for game combinations, it looks as follows:

$k=[3]$

$k=[3,1]$

$k=[3,1,2]$

Scoring

1. ($10$ points): $n,q\le 100$;

2. ($4$ points): all values of $a_i$ are the same;

3. ($11$ points): $n$ is a prime number;

4. ($12$ points): $n,q\le 1000$;

5. ($16$ points): $n,q\le 1.5\cdot {10}^5$, $n=2^k$ for some integer $k$;

6. ($25$ points): $n,q\le {10}^5$;

7. ($22$ points): without additional constraints.