색깔 있는 숲

바이타자르는 π의 날을 맞아 정점이 $n$개인 숲(무방향 비순환 그래프)을 선물로 받았다. 정점은 1부터 $n$까지 번호가 매겨져 있고, 각 간선에는 양의 정수 길이가 주어진다. 각 정점에는 정수 색도 있으며, 처음에는 모든 정점의 색이 0이다.

이 선물을 준 당신은 이제 바이타자르의 질의에 답해야 한다. 질의는 다음 네 가지 중 하나다.

• 1 a b d: 바이타자르가 정점 $a$와 $b$를 길이 $d$인 무방향 간선으로 잇는다. 간선을 추가한 뒤에도 그래프에 사이클이 생기지 않음이 보장된다.
• 2 a b: 바이타자르가 정점 $a$와 $b$를 잇는 간선을 제거한다.
• 3 v z k: 바이타자르가 정점 $v$에서 거리가 $z$ 이하인 도달 가능한 모든 정점을 색 $k$로 칠한다. 두 정점 사이의 거리는 그 사이 단순 경로 위 간선 길이의 합이다.
• 4 u: 바이타자르가 정점 $u$의 현재 색을 묻는다.

첫 줄에 정수 $n$, $m$, $q$가 주어진다($2 \le n \le 200000$, $0 \le m \le n - 1$, $1 \le q \le 200000$). 각각 정점 수, 처음 숲에 있는 간선 수, 질의 수다.

이어지는 $m$개의 줄에는 정수 $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$개의 간선은 올바른 숲을 이루며, 매 수정 후에도 그래프는 올바른 숲으로 남는다. 현재 숲에 없는 간선을 제거하라는 질의는 나오지 않는다.

네 번째 유형의 질의가 적어도 하나 있음이 보장된다.

네 번째 유형의 질의마다 요청된 정점의 색을 한 줄에 하나씩 출력한다.

일부 테스트 그룹에는 첫 번째 또는 두 번째 유형의 질의가 없고, $m = n - 1$을 만족한다.

일부 테스트 그룹에서는 세 번째 유형의 모든 질의에서 $z_i = 10^{15}$이다.

위의 각 조건을 만족하는 테스트 그룹이 적어도 하나씩 있다. 두 조건에 해당하는 그룹은 겹칠 수도, 겹치지 않을 수도 있다.