$N$ 頂点の木が与えられます。
木の頂点には $1$ から $N$ までの番号がつけられています。また、 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでおり、長さは $D_i$ です。
この木の上には人が $N$ 人暮らしており、最初、各頂点 $i$ に人 $i$ が立っています。

これから $T$ 日の間、次のような移動が発生します。

• $i$ 日目には、人 $P_i$ が人 $Q_i$ に向かって、最短距離で $V_i$ だけ移動する。

各移動後の人 $P_i$ の位置を出力形式に従って出力してください。
頂点の上ではなく辺の途中で移動を終える可能性があることに注意してください。

与えられるテストケースについて、 $i$ 日目の移動前の状態で人 $P_i$ と人 $Q_i$ の間の距離は $V_i$ 以上であることが保証されています。

部分点

1. ($300$ 点) $D_i = 1$
2. ($400$ 点) 追加の制約なし

• $1 \leq N \leq 5 \times 10^4$
• $1 \leq u_i \lt v_i \leq N$
• $1 \leq D_i \leq 10^9$
• $1 \leq T \leq 5 \times 10^4$
• $1 \leq P_i, Q_i \leq N$
• $1 \leq V_i \leq 10^9$
• $P_i \neq Q_i$
• 入力はすべて整数である
• 与えられるグラフは木である
• $i$ 日目の移動前の状態で、人 $P_i$ と人 $Q_i$ の間の距離は $V_i$ 以上である

入力は以下の形式で標準入力から与えられる。

$T$ 行出力せよ。$i$ 行目には、 $i$ 日目の移動後の人 $P_i$ の位置を出力せよ。

人 $P_i$ が頂点 $x$ の上にいる場合は 1 x を、
$y$ 番目の辺の途中にいる場合は、人 $P_i$ の位置から頂点 $u_y$ までの距離を $d$ として、 2 y d を出力せよ。