Bajtazarは円周率の日に、森（無向非巡回グラフ）をプレゼントとして受け取りました。この森には $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$ から到達可能で、かつ $v_i$ からの距離が $z_i$ 以下のすべての頂点の色を $k_i$ に塗り替えます。ここで、2つの頂点間の距離とは、それらの間の単純パス上の辺の長さの合計を指します。
• $4\ u_i$ – Bajtazarが、頂点 $u_i$ の現在の色を尋ねます。

入力

入力の最初の行には、3つの整数 $n, m, q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$) が含まれており、それぞれ森の頂点数、最初にある辺の数、問い合わせの数を表します。

続く $m$ 行には、森の辺の説明が含まれています。$i$ 番目の行には、3つの整数 $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の問い合わせが現れることが保証されています。

出力

出力には、タイプ4の問い合わせの数と同じ行数を含める必要があります。各行には、Bajtazarが尋ねた頂点の色を表す整数を1つ出力してください。

入出力例

入力 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

小課題

• 一部のテストグループでは、タイプ1およびタイプ2の問い合わせはなく、$m = n - 1$ が成り立ちます。
• 一部のテストグループでは、すべてのタイプ3の問い合わせにおいて $z_i = 10^{15}$ が成り立ちます。

上記の各ケースについて、それを満たすグループが少なくとも1つ存在します。これらのグループは、両方の条件に対して互いに素である場合もそうでない場合もあります。