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

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

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

Изначально вам дается неориентированный граф с $n$ вершинами и $m$ ребрами. У каждой вершины $v$ есть значение $a_v$. Предлагается произвести над этим графом $q$ операций. Операции могут быть четырех типов:

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

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

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

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

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

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

На каждый запрос типа 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