Problem Description

You are given an undirected graph consisting of $ N $ vertices numbered $1, 2, 3, \ldots, N$ and $ M $ undirected edges numbered $1, 2, 3, \ldots, M$. Edge $ i $ connects vertices $ u_i $ and $ v_i $ bidirectionally.

Each vertex can be painted in a color, and initially, vertex $ i $ is painted in color $ c_i $ (in this problem, colors are represented by integers between $ 1 $ and $ 10^5 $ inclusive).

Each vertex has a sprinkler installed. When the sprinkler at vertex $ i $ is activated, the color of all adjacent vertices to vertex $ i $ is replaced with the color of vertex $ i $ at the time of activation.

Process $ Q $ queries $s_1, s_2, \ldots, s_Q$ given in the following format sequentially:

• Output the current color of vertex $ x $. Then, activate the sprinkler at vertex $ x $. Given in the format 1 x.
• Output the current color of vertex $ x $. Then, overwrite the color of vertex $ x $ with $ y $. Given in the format 2 x y.

Input Format

Input is given from standard input in the following format:

$ N $ $ M $ $ Q $ $ u_1 $ $ v_1 $ $\vdots$ $ u_M $ $ v_M $ $ c_1 $ $ c_2 $ $\cdots$ $ c_N $ $ s_1 $ $\vdots$ $ s_Q $

Output Format

Output $ Q $ lines. The $ i $-th line should contain the current color of vertex $ x $ specified in the $ i $-th query.

Sample Input and Output

Sample Input #1

3 2 3
1 2
2 3
5 10 15
1 2
2 1 20
1 1

Sample Output #1

10
10
20

Sample Input #2

30 10 20
11 13
30 14
6 4
7 23
30 8
17 4
6 23
24 18
26 25
9 3
18 4 36 46 28 16 34 19 37 23 25 7 24 16 17 41 24 38 6 29 10 33 38 25 47 8 13 8 42 40
2 1 9
1 8
1 9
2 20 24
2 26 18
1 20
1 26
2 24 31
1 4
2 21 27
1 25
1 29
2 10 14
2 2 19
2 15 36
2 28 6
2 13 5
1 12
1 11
2 14 43

Sample Output #2

18
19
37
29
8
24
18
25
46
10
18
42
23
4
17
8
24
7
25
16

Notes/Hints

Constraints

• All given inputs are integers.
• $1 \leq N, Q \leq 200$
• $0 \leq M \leq N(N-1)/2$
• $1 \leq u_i, v_i \leq N$
• $1 \leq c_i \leq 10^5$
• $ s_i $ is one of the following formats:
• 1 x $(1 \leq x \leq N)$
• 2 x y $(1 \leq x \leq N, 1 \leq y \leq 10^5)$
• The given graph does not contain multiple edges or self-loops.

Sample Explanation 1

• Initially, vertices $ 1, 2, 3 $ are painted in colors $ 5, 10, 15 $ respectively.
• The first query causes all adjacent vertices to vertex $ 2 $ to be repainted in color $ 10 $. This results in all vertices $ 1, 2, 3 $ being painted in color $ 10 $.
• The second query overwrites the color of vertex $ 1 $ with color $ 20 $.
• The third query causes all adjacent vertices to vertex $ 1 $ to be repainted in color $ 20 $.

见题面 Input 部分

见题面 Output 部分