Байтазар в честь дня числа $\pi$ получил в подарок лес (неориентированный ациклический граф) с $n$ вершинами. В этом лесу вершины пронумерованы числами от $1$ до $n$, а ребрам присвоены положительные целые веса. Кроме того, каждая вершина имеет цвет, описываемый целым числом. Изначально все вершины имеют цвет $0$.

Поскольку именно вы подарили Байтазару этот подарок, ваша задача — отвечать на запросы Байтазара, касающиеся этого леса. Каждый запрос относится к одному из следующих типов:

• $1\ a_i\ b_i\ d_i$ — Байтазар добавляет в лес неориентированное ребро длиной $d_i$, соединяющее вершины $a_i$ и $b_i$. Гарантируется, что после добавления этого ребра граф по-прежнему не будет содержать циклов.
• $2\ a_i\ b_i$ — Байтазар удаляет из леса ребро, соединяющее вершины $a_i$ и $b_i$.
• $3\ v_i\ z_i\ k_i$ — Байтазар перекрашивает в цвет $k_i$ все вершины, достижимые из вершины $v_i$ и находящиеся от нее на расстоянии не более $z_i$. Расстоянием между двумя вершинами здесь называется сумма длин ребер на единственном простом пути между ними.
• $4\ u_i$ — Байтазар спрашивает вас о текущем цвете вершины $u_i$.

Входные данные

В первой строке входных данных содержатся три целых числа $n$, $m$ и $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$), обозначающие количество вершин в лесу, количество изначально присутствующих в нем ребер и количество запросов соответственно.

В следующих $m$ строках содержатся описания ребер леса. В $i$-й из этих строк находятся три целых числа $a_i$, $b_i$ и $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$), означающие, что вершины $a_i$ и $b_i$ соединены ребром длиной $d_i$.

В следующих $q$ строках содержатся описания запросов в формате, указанном в условии задачи. Во всех запросах выполняются условия $1 \le a_i, b_i, v_i, u_i \le n$, $1 \le d_i \le 10^9$, $0 \le z_i \le 10^{15}$ и $1 \le k_i \le 10^9$.

Гарантируется, что заданные $m$ ребер описывают корректный лес, граф остается корректным лесом после каждой модификации, и никогда не появится запрос на удаление ребра, которого в данный момент нет в лесу.

Также гарантируется, что будет задан по крайней мере один запрос четвертого типа.

Выходные данные

На выходе должно быть столько строк, сколько было запросов четвертого типа во входных данных. Каждая строка должна содержать одно целое число — цвет вершины, о которой спросил Байтазар.

Примеры

Пример 1

4 2 9
1 2 2
3 2 5
4 2
3 2 2 5
4 1
3 2 4 3
4 1
4 3
2 2 1
1 1 4 1
4 4

0
5
3
0
0

Подзадачи

• В некоторых группах тестов отсутствуют запросы первого и второго типов, а также выполняется условие $m = n - 1$.
• В некоторых группах тестов во всех запросах третьего типа выполняется условие $z_i = 10^{15}$.

Для каждого из вышеперечисленных случаев существует по крайней мере одна группа тестов, которая его удовлетворяет. Группы для обоих условий могут пересекаться или не пересекаться.