Trong vương quốc TIU, có ~n~ ngôi làng nằm rải rác khắp vùng đất thần tiên. Mỗi ngôi làng chứa đựng một viên ngọc quý giá, và giá trị của viên ngọc ở mỗi ngôi làng đều khác nhau. Ban đầu, ngôi làng thứ ~i~ có viên ngọc có giá trị ~p_i~, và tất cả các giá trị ~p_i~ đều là các số nguyên phân biệt từ ~1~ đến ~n~.

Các ngôi làng trong vương quốc được kết nối liên thông với nhau bằng ~m~ con đường thần bí. Mỗi con đường cho phép bạn di chuyển giữa hai ngôi làng trực tiếp nối với nhau.

Vua của TIU giao cho bạn nhiệm vụ thực hiện một chuỗi ~q~ nhiệm vụ đặc biệt:

1. 1 v: Hãy tìm trong tất cả các ngôi làng có thể đi tới từ ngôi làng ~v~ (bao gồm cả ngôi làng ~v~ ban đầu, dựa trên các con đường hiện có) một ngôi làng ~u~ có viên ngọc quý mang giá trị lớn nhất. Sau khi tìm được ngôi làng đó, hãy lấy viên ngọc ra khỏi làng ~u~ (tức là đặt giá trị của viên ngọc tại đó xuống ~0~) và ghi nhận giá trị của viên ngọc bạn lấy được (để in ra sau).

2. 2 i: Phá hủy con đường thứ ~i~ (theo thứ tự nhập ban đầu, từ ~1~ đến ~m~). Sau khi con đường bị phá hủy, hai ngôi làng mà nó kết nối sẽ không còn được liên thông trực tiếp nữa.

Input

Nhập từ tệp KINGDOM.INP

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, và ~q~ (~1 \le n \le 2 \times 10^5~; ~1 \le m \le 3 \times 10^5~; ~1 \le q \le 5 \times 10^5~).

Dòng thứ hai chứa ~n~ số nguyên phân biệt ~p_1~, ~p_2~, ..., ~p_n~, trong đó ~p_i~ là giá trị của viên ngọc ban đầu ở ngôi làng ~i~ (~1 \le p_i \le n~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ (~1 \le a_i, b_i \le n~, ~a_i \neq b_i~), biểu thị con đường thứ ~i~ kết nối hai ngôi làng ~a_i~ và ~b_i~. Đảm bảo rằng không có con đường nào nối hai ngôi làng giống nhau và tồn tại đường đi giữa mọi cặp ~2~ ngôi làng bất kì ban đầu.

~q~ dòng tiếp theo mô tả các nhiệm vụ của bạn. Mỗi nhiệm vụ có một trong hai dạng sau:

• 1 v: Nhiệm vụ loại thứ nhất, bắt đầu từ ngôi làng ~v~ (~1 \le v \le n~).

• 2 i: Nhiệm vụ loại thứ hai, phá hủy con đường ~i~ (~1 \le i \le m~).

Output

Xuất ra tệp KINGDOM.OUT

Đối với mỗi nhiệm vụ loại thứ nhất 1 v, in ra giá trị của viên ngọc mà bạn thu được (giá trị lớn nhất tìm thấy) trên một dòng riêng biệt.

Subtasks

• Subtask 1 (~20\%~ điểm): ~n, m, q \le 10^3~.

• Subtask 2 (~20\%~ điểm): Vương quốc ban đầu là cây có dạng đường thẳng.

• Subtask 3 (~20\%~ điểm): Vương quốc ban đầu là cây.

• Subtask 4 (~40\%~ điểm): Không có ràng buộc gì thêm.

Sample Input

5 4 6
1 2 5 4 3
1 2
2 3
4 3
4 5
1 1
2 1
2 3
1 1
1 2
1 2

Sample Output

5
1
2
0

Note

Trong một nhiệm vụ loại thứ nhất 1 v, có thể xảy ra trường hợp tất cả các ngôi làng có thể tới từ ngôi làng ~v~ đều không còn viên ngọc nào (giá trị của tất cả các viên ngọc ở các ngôi làng đó là ~0~). Khi này chỉ cần in ra ~0~.