31705번 - Kolorowy las 다국어

문제

Bajtazar z okazji dnia liczby π otrzymał w prezencie las (nieskierowany graf acykliczny) z n wierzchołkami. W lesie tym wierzchołki ponumerowane są liczbami od 1 do n, a krawędzie mają przypisane całkowite dodatnie długości. Dodatkowo każdy wierzchołek ma kolor opisany liczbą całkowitą. Początkowo wszystkie wierzchołki mają kolor 0.

Ponieważ to Ty jesteś osobą, która podarowała Bajtazarowi ten prezent, Twoim zadaniem jest teraz odpowiadać na zapytania Bajtazara dotyczące tego lasu. Każde zapytanie jest jednego z następujących typów:

• 1 a_i b_i d_i – Bajtazar dodaje do lasu nieskierowaną krawędź o długości di łączącą wierzchołki a_i oraz b_i. Gwarantowanym jest, że graf po dodaniu tej krawędzi nadal nie będzie zawierał cyklu.
• 2 a_i b_i – Bajtazar usuwa z lasu krawędź łączącą wierzchołki a_i oraz b_i.
• 3 v_i z_i k_i – Bajtazar przemalowuje na kolor k_i wszystkie wierzchołki osiągalne z wierzchołka v_i i odległe od niego o co najwyżej z_i. Odległością między dwoma wierzchołkami nazywamy tutaj sumę długości krawędzi na ścieżce prostej pomiędzy nimi.
• 4 u_i – Bajtazar pyta Cię o aktualny kolor wierzchołka u_i.

입력

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite n, m oraz q (2 ≤ n ≤ 200 000; 0 ≤ m ≤ n − 1; 1 ≤ q ≤ 200 000), oznaczające odpowiednio liczbę wierzchołków w lesie, liczbę krawędzi początkowo się w nim znajdujących oraz liczbę zapytań.

W kolejnych m wierszach wejścia znajdują się opisy krawędzi lasu. W i-tym z tych wierszy znajdują się trzy liczby całkowite a_i, b_i oraz d_i (1 ≤ a_i, b_i ≤ n; 1 ≤ d_i ≤ 10⁹) oznaczające, że wierzchołki a_i oraz b_i są połączone krawędzią długości d_i.

W kolejnych q wierszach wejścia znajdują się opisy zapytań w formacie podanym w treści zadania. We wszystkich zapytaniach zachodzi 1 ≤ a_i, b_i, v_i, u_i ≤ n, 1 ≤ d_i ≤ 10⁹, 0 ≤ z_i ≤ 10¹⁵ oraz 1 ≤ k_i ≤ 10⁹.

Gwarantowanym jest, że podane m krawędzi opisuje poprawny las, graf pozostaje poprawnym lasem po każdej modyfikacji oraz nigdy nie pojawi się zapytanie nakazujące usunięcie krawędzi, której aktualnie nie ma w lesie.

Gwarantowanym jest również, że pojawi się co najmniej jedno zapytanie czwartego typu.

출력

Na wyjściu powinno znaleźć się tyle wierszy, ile na wejściu było zapytań czwartego typu. Każdy z nich powinien zawierać jedną liczbę całkowitą – kolor wierzchołka, o który zapytał Bajtazar.

제한

노트

• W niektórych grupach testów nie ma zapytań pierwszego ani drugiego typu oraz zachodzi m = n − 1.
• W niektórych grupach testów we wszystkich zapytaniach trzeciego typu zachodzi z_i = 10¹⁵.

Dla każdego wyżej wymienionego przypadku istnieje co najmniej jedna grupa, która go spełnia. Grupy te dla obu warunków mogą być rozłączne lub nie.