Migrated from Lutece 2563 采集物资

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

光孕众生，众生随影 光涤吾魂，影庇吾体 以道制欲，乐而不淫 宁残体肤，不弃光影 故，我在

为了灯塔上的所有人类，猎荒者小队外出采集生存物资。他们来到了 $\texttt{R-49}$ 星际飞船遗址。不幸的是，因为 $\texttt{4068}$ 的失误，惊动了一只脊蛊，然后惊动了一个脊蛊群。随后猎荒者还遭受到了泛生型噬极兽 $\textrm I$ 型的攻击。

现在马克队长想知道怎样最高效的采集完所有的物资，然后撤离。地面有 $n$ 个采集点，编号 $1 \sim n$，每个采集点有一个危险值。马克呼叫灯塔航行控制室，可以请求把 $x$ 和 $y$ 采集点间覆盖通信连接；也可以请求获取与编号为 $x$ 的采集点具有通信连接的所有采集点中，危险值为第 $k$ 小的采集点是哪一个。灯塔可以为采集点间建立通信连接，但是无法求出危险值为第k大的采集点是哪一个，于是光影会向光影之主寻求真解。你，作为光影之主，请帮帮他们。

Input

第 $1$ 行是用空格隔开的两个整数，分别表示采集点的个数 $n$ 以及一开始存在的通信连接数 $m$ 。

第 $2$ 行有 $n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的采集点的危险值 $R_i$ 。

接下来 $m$ 行，每行两个整数 $u, v$，表示一开始存在编号为 $u$ 的采集点和编号为 $v$ 的采集点之间的通信连接。

接下来一行有一个整数，表示马克的呼叫次数 $Q$。

接下来 $Q$ 行，每行描述一个操作。每行首先有一个字符 $op$，表示操作类型，然后有两个整数 $x, y$ 。

• 若 $op$ 为 Q，请求获取与编号为 $x$ 的采集点具有通信连接的所有采集点中，危险值为第 $y$ 小的采集点是哪一个。
• 若 $op$ 为 B，则表示在采集点 $x$ 与采集点 $y$ 之间建立通信连接。

Output

每次马克呼叫灯塔航行控制室，请求获取与编号为 $x$ 的采集点具有通信连接的所有采集点中，危险值为第 $k$ 小的采集点是哪一个的时候，光影会向你寻求真解，请输出一行一个整数，代表所求的采集点的编号。

如果不存在，输出 $-1$ 。

Samples

3 1
2 3 1
1 2
1
Q 1 2

2

Constraints

$1 \leq m \leq n \leq 10^5, 1 \leq Q \leq 3 \times 10^5$，$R_i$ 为一个 $1 \sim n$ 的排列，$op \in\{\texttt Q,\texttt B \}$，$1 \leq u, v, x, y \leq n$

Resources

2021 UESTC ICPC Training for Data Structures