問題文

パ研王国には N 個の街があり、 1,2,3,\ldots,N と番号がついています。

王国には N-1 本の道路があり、 i 本目の道路は街 A_i と街 B_i を結んでいて、C_i という重みが定まっています。パ研王国のすべての街は道路を使って行き来することができます。

パ研王国の K 国王は変わっているので、 Q 個の街の組をあなたに言い渡し、各組 (S_i,T_i)(1 \leq i \leq Q) について街 S_i から街 T_i へのパス上の道路の重みの中央値を求めたいと言いました。召使のあなたは K 国王の代わりに王が求めたい値を求めてあげてください。

(2023/03/27 15:36追記:) 数列 X に対する中央値は、要素数が偶数の場合は要素を昇順に並べた列を X_1,X_2,...,X_n とするとき、(X_{n/2} + X_{n/2+1}) / 2 で定義されます。 奇数の場合は、要素を昇順に並べた列を X_1,X_2,...,X_n とするとき、X_{(n+1)/2} で定義されます。

制約

• 2 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq N (1 \leq i \leq N-1)
• 2 \leq C_i \leq 2 \times 10^5 (1 \leq i \leq N-1)
• C_i はすべて偶数(1 \leq i \leq N-1)
• 1 \leq Q \leq 5 \times 10^4
• 1 \leq S_i,T_i \leq N (1 \leq i \leq Q)
• S_i \neq T_i (1 \leq i \leq Q)

入力例 1

5
1 2 50
2 3 100
1 4 20
4 5 30
1
3 5

出力例 1

40

入力例 2

3
1 2 100
2 3 50
1
1 3

出力例 2

75