[HNOI2012] 永无乡

题目描述

永无乡包含 $n$ 座岛,编号从 $1$ 到 $n$ ,每座岛都有自己的独一无二的重要度,按照重要度可以将这 $n$ 座岛排名,名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干座(含 $0$ 座)桥可以 到达岛 $b$ ,则称岛 $a$ 和岛 $b$ 是连通的。 现在有两种操作: `B x y` 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。 `Q x k` 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛,即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座,请你输出那个岛的编号。

输入输出格式

输入格式


第一行是用空格隔开的两个整数,分别表示岛的个数 $n$ 以及一开始存在的桥数 $m$。 第二行有 $n$ 个整数,第 $i$ 个整数表示编号为 $i$ 的岛屿的排名 $p_i$。 接下来 $m$ 行,每行两个整数 $u, v$,表示一开始存在一座连接编号为 $u$ 的岛屿和编号为 $v$ 的岛屿的桥。 接下来一行有一个整数,表示操作个数 $q$。 接下来 $q$ 行,每行描述一个操作。每行首先有一个字符 $op$,表示操作类型,然后有两个整数 $x, y$。 - 若 $op$ 为 `Q`,则表示询问所有与岛 $x$ 连通的岛中重要度排名第 $y$ 小的岛是哪座,请你输出那个岛的编号。 - 若 $op$ 为 `B`,则表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。

输出格式


对于每个询问操作都要依次输出一行一个整数,表示所询问岛屿的编号。如果该岛屿不存在,则输出 $-1$ 。

输入输出样例

输入样例 #1

5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

输出样例 #1

-1
2
5
1
2

说明

### 数据规模与约定 - 对于 $20\%$ 的数据,保证 $n \leq 10^3$, $q \leq 10^3$。 - 对于 $100\%$ 的数据,保证 $1 \leq m \leq n \leq 10^5$, $1 \leq q \leq 3 \times 10^5$,$p$ 为一个 $1 \sim n$ 的排列,$op \in \{\texttt Q, \texttt B\}$,$1 \leq u, v, x, y \leq n$。