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

The players are lined up in a circle such that the next player to the right of player $i$ is player $i+1$ (for $1 \leqslant i < n$), and for player $n$, the next player is player $1$.

We 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 player $1$; Players take turns passing the ball indefinitely: when performing the $i$-th pass (0-indexed), the player currently controlling the ball passes it to the player located $x$ positions to the right in the circle, where $x = k_{(i \pmod m)}$; * The strength of the game combination is the minimum skill level among the skills of all players who held the ball at any moment during the described process.

You are given an array of integers $a_0, a_1, \dots, a_{q-1}$. 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 \leqslant n, q \leqslant 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 \leqslant c_i \leqslant n$) — the skill levels of the players.

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

Output

Output $q$ integers — the required strength values of the game combinations.

Subtasks

1. (10 points): $n, q \leqslant 100$;
2. (4 points): all values of $a_i$ are equal;
3. (11 points): $n$ is a prime number;
4. (12 points): $n, q \leqslant 1000$;
5. (16 points): $n, q \leqslant 1.5 \cdot 10^5$, $n = 2^k$ for some integer $k$;
6. (25 points): $n, q \leqslant 10^5$;
7. (22 points): no additional constraints.

Examples

Input 1

6 3
6 3 5 4 2 1
3 1 2

Output 1

4 1 2

Note

In the example, the ball passes for the game combinations look as follows:

$k = [3]$

$k = [3, 1]$

$k = [3, 1, 2]$