The party began, the greasy uncle was playing cards, the fat otaku was eating, and the little beauty was drawing.

After the party for so long, why haven't you seen YHH? Oh, we almost forgot, a little beauty is drawing here! YHH watched her quietly and occasionally handed her a paintbrush.

However, your focus is quite strange: you have just found some rules about the colour of the brush, and now you want to use these rules to write out all the colour of the brushes that YHH handed to the little beauty. The rules are as following:

There are N areas on the little beauty's painting, some areas are adjacent, in order to make the adjacent areas can be distinguished, their colours need to be different, there are M adjacent relations in total;

Because the colour of some areas in the initial painting is wrong, or the colour of other adjacent areas is the same, the little beauty needs to make some adjustments. YHH does not need to care whether the other places are correct, but only need to meet the requirements of the little beauty every time.

The little beauty's brushes are arranged in rows, numbered starting from 0 according to the colour. Every time the little beauty needs to draw an area, YHH will pass a brush. And the colour of this brush is different from all colours of the adjacent area, and in order to be faster, YHH will take the closest one (the one with the smallest number);

Sometimes the little beauty is not satisfied with the colour of a particular area, so she will specify a colour to colour this area.

Now given two numbers N, M, representing the number of areas and the number of adjacent relationships on little beauty's painting. The next line contains N numbers, representing the initial colour of each area. And then M lines, each line contains two integers u, v represent the two adjacent areas.

Then given a number Q, representing the number of queries. In the following Q lines, each line includes a query. There are two forms of inquiry:

Type 1: 1 u x (0 ≤ x ≤ ) – Change the colour of area u to x.

Type 2: 2 u – At this time, the little beauty wants to draw area u, YHH will pass a brush according to the above rules, which number is what you should print.

Each input file only contains one test case.

The first line contains two integers N, M (1 ≤ N, M ≤ ), indicating the number of areas and the number of adjacent relationships on the little beauty's painting.

The next line contains N integers  ,  ,……,  (0 ≤  ≤ ), indicating the initial color of area i.

Then following next M lines, each line contains two integers u, v (1 ≤ u, v ≤ N), indicating the two areas which are adjacent.

After that, the next line contains an integer Q (1≤ Q ≤ ), indicating the number of queries.

Then following Q lines contain queries described in the description.

For each query of type 2, print an integer, indicating the number of brush that YHH passed to little beauty.

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