P3098 [USACO13DEC] The Bessie Shuffle G

贝西有一种独门的洗牌方法，称为 A 类洗牌法； A 类洗牌法的具体过程：将一堆共 $M$（$2 \le M \le 10 ^ 5$）张从上到下编号 $1, 2, \cdots, M$ 的纸牌，从上到下第 $i$ 张牌洗到位置 $p _ i$。 例如，$M=3，p = \{3, 1, 2\}$，则执行一次 A 类洗牌法后，从上到下将变为 $2, 3, 1$，即牌 $1$ 放到位置 $3$，牌 $2$ 放到位置 $1$，牌 $3$ 放到位置 $2$。 贝西现在要练习另外一种洗牌方法，称为 B 类洗牌法。 B 类洗牌法的具体过程： 有一堆 $N$（$M \le N \le 10 ^ 9$）张编号为 $1, 2, \cdots, N$ 的牌，并按从上到下 $1$ 到 $N$ 的顺序堆放。另有一个牌堆用来辅助洗牌，称为临时堆，开始时为空。 1. 将最上面 $M$ 张牌进行一次 A 类洗牌法； 2. 将最上面的一张牌放到临时堆的最上方； 3. 重复前两个操作，直到原先的堆没有牌为止。 以上过程中，当原先堆的牌不足 $M$ 张的时候，将不进行 A 类洗牌法，而是将最上面的牌依次放到临时堆上。 给定 $N, M$ 和排列 $p$。现在有 $Q$（$1 \le Q \le \min(N, 5000)$）个询问，请求出对其做一次 B 类洗牌法后临时堆中 $q_i$ 位置上的牌的编号。 $50\%$ 的数据中，$N \le 10 ^ 5$。

* 第 $1$ 行：一行包含 $N$、$M$ 和 $Q$，用空格分隔。 * 第 $2$ 行至第 $M+1$ 行：第 $i+1$ 行表示在贝西洗牌中，第 $i$ 张牌距顶部的位置 $P_i(1\le P_i\le M)$。 * 第 $M+2$ 行至第 $M+Q+1$ 行：第 $M+i+1$ 行包含一个整数 $q_i$ 对于第 $i$ 个查询。你需要计算从顶部起第 $q_i$ 个位置 $(1\le q_i\le N)$ 的卡片上的编号。

* 第 $1$ 行至第 $Q$ 行：在第 $i$ 行，打印一个整数，表示从顶部开始第 $q_i$ 张牌的编号。

贝西的五张牌刚开始顺序为 [1, 2, 3, 4, 5]。她一次洗三张牌，效果是将第一张牌放到底部。以上五个问题询问了每一张牌的位置。 洗牌的顺序是: ```plain [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]