#P18827. [Croatian CPC2018] Ghost leg

[Croatian CPC2018] Ghost leg

[Croatian CPC2018] Ghost leg

题目描述

Ghost leg(Amidakuji)是一种抽签游戏,nn 名玩家各获得 nn 件奖品中的一件。

游戏板上有 nn 条竖线,从左到右编号为 11 至 nn。最初还有 mm 条横杆,位于互不相同的高度,从上到下编号为 11 至 mm。第 jj 条横杆连接相邻的两条竖线 pjp_j 和 pj+1p_j+1。

第 jj 名玩家位于第 jj 条竖线顶部,第 jj 件奖品位于第 jj 条竖线底部。要确定玩家 jj 获得哪件奖品,从他的起点沿竖线向下走;遇到横杆时,必须沿横杆走到相邻竖线,再继续向下走。最终到达的竖线编号就是奖品编号。

给出游戏板和依次发生的 qq 个事件,每个事件属于以下一种:

  • A i:移除编号为 ii 的横杆。
  • B j:询问此时玩家 jj 会获得哪件奖品。

请回答所有 B 类询问。

输入格式

第一行包含两个整数 n,mn,m(2≤n≤1062\le n\le10^6,1≤m≤1061\le m\le10^6)。

第二行包含 mm 个整数 p1,p2,…,pmp_1,p_2,\ldots,p_m(1≤pi≤n−11\le p_i\le n-1),按横杆从上到下的顺序描述它们的位置。

第三行包含一个整数 qq(1≤q≤1061\le q\le10^6)。

接下来 qq 行,每行形如 A i(1≤i≤m1\le i\le m)或 B j(1≤j≤n1\le j\le n)。同一条横杆不会被移除两次,且至少有一次 B 类询问。横杆移除后,其他横杆的编号保持不变。

输出格式

按询问顺序,对每个 B 类事件输出一行一个整数,表示对应奖品的编号。

样例 1

输入

6 5
2 1 5 3 2
10
B 1
B 2
B 6
A 3
B 6
B 3
A 1
B 2
B 3
B 4

输出

3
4
5
6
1
1
4
2

样例说明

下图为初始游戏板。玩家 1 经过横杆 2、横杆 5 后获得奖品 3。

初始游戏板