Bajtazar는 파이 데이(π-day)를 맞아 $n$개의 정점으로 구성된 숲(무방향 비순환 그래프)을 선물로 받았습니다. 이 숲에서 정점들은 $1$부터 $n$까지 번호가 매겨져 있으며, 간선에는 양의 정수 가중치가 할당되어 있습니다. 또한 각 정점은 정수로 표현되는 색상을 가집니다. 처음에 모든 정점의 색상은 $0$입니다.

당신이 Bajtazar에게 이 선물을 준 사람이므로, 이제 이 숲에 대한 Bajtazar의 질의에 답해야 합니다. 각 질의는 다음 유형 중 하나입니다.

• $1 \ a_i \ b_i \ d_i$ – Bajtazar가 숲에 정점 $a_i$와 $b_i$를 잇는 가중치 $d_i$인 무방향 간선을 추가합니다. 이 간선을 추가한 후에도 그래프는 여전히 순환을 포함하지 않음이 보장됩니다.
• $2 \ a_i \ b_i$ – Bajtazar가 숲에서 정점 $a_i$와 $b_i$를 잇는 간선을 제거합니다.
• $3 \ v_i \ z_i \ k_i$ – Bajtazar가 정점 $v_i$로부터 도달 가능하고 거리가 $z_i$ 이하인 모든 정점의 색상을 $k_i$로 변경합니다. 여기서 두 정점 사이의 거리는 두 정점 사이의 유일한 경로에 있는 간선 가중치의 합을 의미합니다.
• $4 \ u_i$ – Bajtazar가 현재 정점 $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$개의 간선은 올바른 숲을 형성하며, 각 수정 후에도 그래프는 올바른 숲 상태를 유지하고, 현재 숲에 존재하지 않는 간선을 제거하라는 질의는 주어지지 않음이 보장됩니다. 또한, 네 번째 유형의 질의가 최소 한 번 이상 등장함이 보장됩니다.

출력

출력은 네 번째 유형의 질의 수만큼의 줄로 구성되어야 합니다. 각 줄에는 Bajtazar가 질문한 정점의 색상을 나타내는 정수 하나를 포함해야 합니다.

예제

입력 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

출력 1

0
5
3
0
0

서브태스크

• 일부 테스트 그룹에서는 첫 번째나 두 번째 유형의 질의가 없으며 $m = n - 1$을 만족합니다.
• 일부 테스트 그룹에서는 모든 세 번째 유형의 질의에 대해 $z_i = 10^{15}$를 만족합니다.

위에서 언급한 각 경우에 대해 이를 만족하는 그룹이 최소 하나 이상 존재합니다. 두 조건에 대한 그룹은 서로소일 수도 있고 아닐 수도 있습니다.