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.