#205. [HNOI2012][线段树合并]永无乡

[HNOI2012][线段树合并]永无乡

[HNOI2012] 永无乡

题目描述

永无乡包含 nn 座岛,编号从 11nn ,每座岛都有自己的独一无二的重要度,按照重要度可以将这 nn 座岛排名,名次用 11nn 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。如果从岛 aa 出发经过若干座(含 00 座)桥可以 到达岛 bb ,则称岛 aa 和岛 bb 是连通的。

现在有两种操作:

B x y 表示在岛 xx 与岛 yy 之间修建一座新桥。

Q x k 表示询问当前与岛 xx 连通的所有岛中第 kk 重要的是哪座岛,即所有与岛 xx 连通的岛中重要度排名第 kk 小的岛是哪座,请你输出那个岛的编号。

输入格式

第一行是用空格隔开的两个整数,分别表示岛的个数 nn 以及一开始存在的桥数 mm

第二行有 nn 个整数,第 ii 个整数表示编号为 ii 的岛屿的排名 pip_i

接下来 mm 行,每行两个整数 u,vu, v,表示一开始存在一座连接编号为 uu 的岛屿和编号为 vv 的岛屿的桥。

接下来一行有一个整数,表示操作个数 qq

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

  • opopQ,则表示询问所有与岛 xx 连通的岛中重要度排名第 yy 小的岛是哪座,请你输出那个岛的编号。
  • opopB,则表示在岛 xx 与岛 yy 之间修建一座新桥。

输出格式

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

样例 #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%20\% 的数据,保证 n103n \leq 10^3, q103q \leq 10^3
  • 对于 100%100\% 的数据,保证 1mn1051 \leq m \leq n \leq 10^5, 1q3×1051 \leq q \leq 3 \times 10^5pip_i 为一个 1n1 \sim n 的排列,op{Q,B}op \in \{\texttt Q, \texttt B\}1u,v,x,yn1 \leq u, v, x, y \leq n