#OJ1632. Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

小K穿越到了一个很远古的时代。在这个时代一共有n个皇城,每个皇城都有个防御值w,皇城之间通过御路相连。小K所在的皇城要寻求其他皇城的帮助(防御值要大于自己的皇城),而御路会经常被拆除,请你来帮小K寻求帮助。

Input

多组数据 每组第一行:一个正整数n(2<=n<=10000),表示有n个皇城(编号为0——n-1) 每组第二行:n个皇城的防御值(按编号的增序) 每组第三行:一个正整数m(0<=m<=20000),表示有m条御路 每组第4至m+3行:每行两个数x,y,表示x和y皇城有一条御路相连 每组第m+4行:一个正整数q(0<=q<=40000),表示有q个操作 每组第m+5至m+q+4行:有两种查询,如下: 第一个整数为0,后面接一个正整数u,表示小K从u皇城出发寻求帮助 第一个整数为1,后面接两个正整数u,v,表示拆除u,v皇城之间的御路

Output

对每次寻求帮助输出一行,包含一个正整数,表示小K从所在皇城出发,能够寻求到的最大帮助的皇城的编号,若不能寻求到帮助,输出-1 数据保证不会出现重边,且答案唯一

Sample Input

2
10 20
1
0 1
5
0 0
0 1
1 0 1
0 0
0 1

Sample Output

1
-1
-1
-1

HINT

Append Code

Source