OI题库

【题目描述】

Bessie正在练习牌技，她已经熟练地掌握了一种Bessie洗牌法，就是把M(2<=M<=100,000)张牌重新组织，使从上面数的第i张牌变成第P[i]张牌。

现在Bessie正在一张大台子上洗牌，她的这副牌共有N(M<=N<=1,000,000,000)张,编号分别为1～N。她先取最上面的M张，并按照Bessie洗牌法洗过后再放回那撂牌的最上面，然后她把最上面那张牌拿走，正面朝下放在台子上。她将重复这个过程，并不断地将最上面的牌拿走放到另一撂上去，直到无牌可洗为止。当Bessie剩余的牌不足M张时，他将不再进行Bessie洗牌法，而是持续地拿走最上面的牌放到另一摞上去。

Bessie知道这副牌起初是按顺序排放的，即1号牌在最上面，下面是2号牌，……，最底下一张是N号牌。给你Bessie洗牌法的规则，请帮Bessie计算出洗牌完毕后这摞牌中Q(1<=Q<=N,Q<=5,000)个不同位置上牌的编号。

有50%的数据保证N<=100,000。

【输入格式】

第1行有三个数，分别由一个空格隔开，即N,M,Q；

接下来有M行，其中第i行为Bessie洗牌法中第i张牌的新位置P[i]（1<=p[i]<=M）；

最后有Q行，其中第i行有一个整数q_i，表示第i个询问，你需要计算出从上往下数第q_i个位置上牌的编号，(1<=q_i<=N)。

【输出格式】

输出共有Q行，其中第i行有一个整数，表示从上面数第q_i个位置上牌的编号。

【样例输入】

5 3 5
3
1
2
1
2
3
4
5

【样例输出】

4



5



3



1



2

【提示】

输出解释：

洗牌过程如下 ：

[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (2号牌被拿出，面朝下放置)

[3, 1, 4, 5] -> [1, 4, 3, 5] (1号牌被拿出，面朝下放置)

[4, 3, 5] -> [3, 5, 4] (3号牌被拿出，面朝下放置)

[5, 4] (5号牌被拿出，面朝下放置)

[4] (4号牌被拿出，面朝下放置)

最终的顺序为（从上往下） 4, 5, 3, 1, 2

【来源】

在此键入。