足球队中有 $n$ 名球员，编号为 $1$ 到 $n$。第 $i$ 号球员的球技水平由整数 $c_i$ 描述。

球员们按顺序围成一个圆圈，使得对于第 $i$ 号球员（$1 \leqslant i < n$），其右侧的下一位是第 $i+1$ 号球员，而第 $n$ 号球员的下一位是第 $1$ 号球员。

我们定义一个由整数数组 $k = [k_0, k_1, k_2, \dots, k_{m-1}]$ 表征的“游戏组合”的强度如下： 初始时，球在第 $1$ 号球员手中； 球员们轮流传球，过程无限进行：在进行第 $i$ 次传球时，当前持球的球员将球传给顺时针方向第 $x$ 个位置的球员，其中 $x = k_{(i-1) \pmod m}$； * 游戏组合的强度定义为在上述过程中所有曾经触球的球员中，球技水平的最小值。

给定一个整数数组 $a_0, a_1, \dots, a_{q-1}$。对于每个 $i$（从 $0$ 到 $q-1$），求出由数组 $[a_0, a_1, \dots, a_i]$ 表征的游戏组合的强度。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \leqslant n, q \leqslant 3 \cdot 10^5$)，分别表示球员数量和数组 $a$ 的长度。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \leqslant c_i \leqslant n$)，表示球员的球技水平。

第三行包含 $q$ 个整数 $a_0, a_1, \dots, a_{q-1}$ ($1 \leqslant a_i \leqslant n-1$)，表示数组 $a$ 的元素。

输出格式

输出 $q$ 个整数，即各游戏组合的强度值。

子任务

1. (10 分): $n, q \leqslant 100$;
2. (4 分): 所有 $a_i$ 的值相同;
3. (11 分): $n$ 为质数;
4. (12 分): $n, q \leqslant 1000$;
5. (16 分): $n, q \leqslant 1.5 \cdot 10^5$, $n = 2^k$（对于某个整数 $k$）;
6. (25 分): $n, q \leqslant 10^5$;
7. (22 分): 无附加限制。

样例

输入 1

6 3
6 3 5 4 2 1
3 1 2

输出 1

4 1 2

说明

样例中传球过程的示意图如下：

$k = [3]$

$k = [3, 1]$

$k = [3, 1, 2]$