Республиканская олимпиада по информатике 2019 года за 10 класс | Казахстанские олимпиады

Задача A. Занимательная игра

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

Недавно Айдос изучая культуру древних народов горных местностей, обнаружил одну очень занимательную игру. Как верили создатели этой игры, она играла очень важную роль в культуре и помогала развивать дедуктивное мышление людей всех возрастов. Айдос проникся интересностью игры и решил перевести ее на современный лад. Вот, что у него получилось.

Изначально вам дается неориентированный граф с nn вершинами и mm ребрами. У каждой вершины vv есть значение ava_v. Предлагается произвести над этим графом qq операций. Операции могут быть четырех типов:

Формат входного файла

Первая строка входных данных содержит три целых чисел n,m,qn, m, q через пробел — количество вершин, ребер и операций (1<=n,m,q<=2105)(1 <= n, m, q <= 2 \cdot 10^5).

Вторая строка содержит nn целых чисел a1,a2,...,ana_1, a_2, ..., a_n через пробел — значения вершин (1<=ai<=109)(1 <= a_i <= 10^9).

Следующие mm строк содержат описания ребер графа, по два целых числа u,vu, v в каждой строке — неориентированное ребро между вершинами uu и vv (1<=u,v<=n)(1 <= u, v <= n).

В каждой из следующих qq строк содержатся описания запросов. Каждое описание соответствует одному из следующих видов:

Формат выходного файла

На каждый запрос типа 4 выведите в новой строке номер вершины согласно требованиям в запросе.

Примеры

Вход

3 2 8
3 1 2
1 2
2 3
4 2 1
4 2 2
1 1 3
4 3 2
3 1 2
4 3 2
2 1 3
4 3 1

Выход

3
1
1
1
2
Решение

Здесь могут быть решения задач с LaTeX\LaTeX