[AdditionalFile5215.zip](file://AdditionalFile5215.zip?type=additional_file)

#5215. 「UOI 2024 Stage 4 Day2」足球

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day2 T2. Футбол

一支足球队有 $n$ 名球员，编号为从 $1$ 到 $n$ 的整数。编号为 $i$ 的球员的比赛水平用整数 $c_i$ 表示。

球员们围成一个圆圈，排列顺序为：对于编号为 $i$ $(1 \le i < n)$ 的球员，右侧相邻的球员编号为 $i+1$；对于编号为 $n$ 的球员，右侧相邻的球员编号为 $1$。

我们定义一个由整数数组 $k=[k_0, k_1, k_2, \ldots, k_{m-1}]$ 描述的比赛组合的力量如下：

• 初始时，球在编号为 $1$ 的球员手中；
• 球员们按顺序无限传递球：在第 $i$ 次传递时，当前持有球的球员将球传给圆圈上右侧第 $x$ 个位置的球员，其中 $x = k_{((i-1) \bmod m)}$；
• 比赛组合的力量定义为在上述过程中曾经持有过球的所有球员的比赛水平中的最小值。

给定一个整数数组 $a_0, a_1, \ldots, a_{q-1}$。对于每个 $i$（从 $0$ 到 $q-1$），计算由数组 $[a_0, a_1, \ldots, a_i]$ 描述的比赛组合的力量。

输入格式

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

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

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

输出格式

输出 $q$ 个整数，表示所求的比赛组合力量值。

样例

输入

6 3
6 3 5 4 2 1
3 1 2

输出

4 1 2

在样例中，比赛组合的球传递过程如下所示：

数据范围与提示

详细子任务附加限制及分值如下表所示：