Problem Description

Given an undirected graph G=(V,E). All vertices are numbered from 1 to N. And every vertex u has a value of $A_u$. Let $S_u$={$A_v$│(u,v)∈E}. Also, F(u) equals MEX(minimum excludant) value of $S_u$. A MEX value of a set is the smallest non-negative integer which doesn’t exist in the set.

There are two types of queries.

Type 1: 1 u x – Change $A_u$ to x (0≤x≤$10^9$).
Type 2: 2 u – Calculate the value of F(u).

For each query of type 2, you should answer the query.

Input

The first line of input contains a single integer T (1≤T≤10) denoting the number of test cases. Each test case begins with a single line containing two integers n (1≤n≤$10^5$), m (1≤m≤$10^5$) denoting the number of vertices and number of edges in the given graph.

The next line contains n integers and $i^{th}$ of them is a value of $A_i$ (0≤$A_i$≤$10^9$).

The next m lines contain edges of the graph. Every line contains two integers u, v meaning there exist an edge between vertex u and v.

The next line contains a single integer q (1≤q≤$10^5$) denoting the number of queries.

The next q lines contain queries described in the description.

Output

For each query of type 2, output the value of F(u) in a single line.

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