题目描述

贝西正在练习她的洗牌方法。她已经掌握了一种针对 $m$ 张牌（$2 \le m \le 10^5$）的贝西洗牌法——这种洗牌会让原本从上往下第 $i$ 张牌变成从上往下第 $p_i$ 张牌。

现在贝西要在更大的牌堆上练习洗牌。她有一副标号为 $1 \sim n$ 的 $n$ 张牌（$m \le n \le 10^5$）。她的洗牌方式是：每次取出最上面的 $m$ 张牌进行贝西洗牌，然后将洗好的牌放回牌堆顶部。接着她移除最上面的一张牌并面朝下放置。她重复这个过程，将顶部的牌依次叠放，直到牌堆用完。当剩余牌数不足 $m$ 张时，她不再进行贝西洗牌，但仍会将最上面的牌叠放到其他牌上。

已知牌堆初始是按升序排列的（$1$ 在最上面，$n$在最下面）。给定贝西洗牌法的描述，请帮助贝西计算最终牌堆中 $Q$ 个指定位置（$1 \le Q \le N$ 且 $Q \le 5000$）上的牌面数字。

输入格式

第 $1$ 行三个空格分隔的整数 $n,m,Q$。

接下来 $m$ 行分别表示贝西洗牌中第 $i$ 张牌的新位置 $p_i$（从上往下数，$1 \le p_i \le m$）。

最后 $Q$ 行，每行包含一个整数 $q_i$，表示查询第 $q_i$ 张牌上最后得到的数字（从上往下数，$1 \le q_i \le N$）。

输出格式

输出一共 $Q$ 行，对于每组数据，输出第 $q_i$ 张牌上最后得到的数字。

5 3 5 
3 
1 
2 
1 
2 
3 
4 
5 

4 
5 
3 
1 
2 

提示

贝西有一副初始顺序为 $[1,2,3,4,5]$ 的 $5$ 张牌。她的洗牌针对 $3$ 张牌，效果是将顶牌移到底部。共有 $5$ 个查询分别询问牌堆的每个位置。

洗牌过程如下：

$[1,2,3,4,5] \to [2,3,1,4,5]$（将 $2$ 面朝下放置）
$[3,1,4,5] \to [1,4,3,5]$（将 $1$ 面朝下放置）
$[4,3,5] \to [3,5,4]$（将 $3$ 面朝下放置）
$[5,4]$（将 $5$ 面朝下放置）
$[4]$（将 $4$ 面朝下放置）

最终牌堆顺序为 $[4,5,3,1,2]$。

Translate by