Một doanh nghiệp có ~n~ nhân viên được đánh thứ tự từ ~1~ đến ~n~, nhân viên thứ ~i~ có một chỉ số ~t_i~, cho biết thời gian ra quyết định của nhân viên là thời gian trung bình mà nhân viên thứ ~i~ này cần có để đưa ra quyết định sau khi nhận được thông tin. Chỉ số này gắn với con người, không gắn với vị trí làm việc, điều đó nghĩa là khi một nhân viên được điều chuyển sang vị trí khác, thời gian ra quyết định của nhân viên đó không thay đổi. Hiện doanh nghiệp đang có một sơ đồ quản lý và nhân viên thứ ~i~ đang ở vị trí ~i~ trong sơ đồ quản lý này. Sơ đồ quản lý này thể hiện phân cấp quản lý của các nhân viên, trong đó mỗi nhân viên có thể quản lý trực tiếp một hoặc nhiều nhân viên khác. Nếu nhân viên ở vị trí ~i~ quản lý trực tiếp nhân viên ở vị trí ~j~ và nhân viên ở vị trí ~j~ quản lý trực tiếp hoặc gián tiếp nhân viên ở vị trí ~k~, thì nhân viên ở vị trí ~i~ cũng được coi là quản lý gián tiếp nhân viên ở vị trí ~k~. Không có nhân viên nào quản lý chính bản thân mình.

Để phục vụ việc luân chuyển nhân viên ở các vị trí, quản lý doanh nghiệp cần xử lý hai loại truy vấn:

• Truy vấn loại 1: ~1~ ~u~ ~v~ – hoán đổi vị trí của nhân viên ~u~ và nhân viên ~v~.
• Truy vấn loại 2: ~2~ ~e~ – tìm thời gian ra quyết định nhỏ nhất trong số tất cả các quản lý (trực tiếp hoặc gián tiếp) của nhân viên ~e~. Nếu nhân viên ~e~ không có ai quản lý, kết quả là ~0~.

Trong quá trình luân chuyển, các quan hệ trong sơ đồ quản lý được xác định theo vị trí và hoàn toàn cố định trong suốt quá trình, chỉ có con người di chuyển giữa các vị trí.

Yêu cầu: Hãy xác định kết quả cho mỗi truy vấn loại ~2~.

INPUT

Dòng đầu chứa ba số nguyên ~n, m, q~ (~n \le 10^3~, ~m, q \le 10^5~) cho biết số nhân viên, số quan hệ quản lý trực tiếp và số truy vấn.

Dòng thứ hai chứa ~n~ số nguyên dương ~t_1, t_2, ..., t_n~, các số có giá trị không vượt quá ~10^9~ lần lượt cho biết thời gian ra quyết định của ~n~ nhân viên.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ cho biết vị trí ~x~ quản lý trực tiếp vị trí ~y~ (~x ≠ y~, ~1 ≤ x, y ≤ n~).

~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng đã nêu.

OUTPUT

Gồm nhiều dòng, mỗi dòng ghi một số nguyên cho biết kết quả tìm được tương ứng với truy vấn loại ~2~ ở dữ liệu vào.

SUBTASKS

SAMPLE INPUT

7 8 10
20 33 33 19 42 22 25
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7
2 7
1 2 4
2 7
2 5
1 1 4
2 7
1 4 7
2 2
1 3 6
2 6

SAMPLE OUTPUT

19
20
19
19
0
25