Description

给定一个无向图 $G = (V, E)$。所有顶点编号从 $1$ 到 $n$。每个顶点 $u$ 都有一个权值 $f(u)$。令 $S(u) = \{ f(v) \mid (u, v) \in E \}$。另外，$g(u)$ 等于集合 $S(u)$ 的 MEX（minimum excludant）值。一个集合的 MEX 值是指不出现于该集合中的最小非负整数。

有两种类型的操作：

• 类型 1：1 u x —— 将 $f(u)$ 修改为 $x$（$0 \leq x \leq 10^9$）。
• 类型 2：2 u —— 计算 $g(u)$ 的值。

对于每个类型 2 的操作，你需要输出对应的答案。

Format

Input

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试数据的组数。每组测试数据的第一行包含两个整数 $n$（$1 \leq n \leq 10^5$）、$m$（$0 \leq m \leq 10^5$），分别表示图中顶点的数量和边的数量。

接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $f(i)$ 的值（$0 \leq f(i) \leq 10^9$）。

接下来 $m$ 行描述图中的边，每行包含两个整数 $u, v$，表示顶点 $u$ 和顶点 $v$ 之间存在一条边。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示操作的数量。

接下来 $q$ 行，每行描述一个如题面所述的操作。

Output

对于每个类型 2 的操作，输出一行一个整数，表示 $g(u)$ 的值。

Samples

1
5 4
0 1 2 0 1
1 2
1 3
2 4
2 5
5
2 2
1 2 2
2 2
1 3 1
2 1

2
2
0