Background

我是小 y，数论太难了，我只会树论。

Description

树是指 $n(n ≥ 1$) 个点 $n — 1$ 条边的连通无向图。 我有一棵树 $T (V = {V1, V2 , . . . , Vn}, E)$，树有边权 $ω : E I→ Z+$. 定义$S ≤ E$ 的权值为 $ω(S) = εe∈S ω(e)$. 定义 $R(VI, EI)$ 是 $T$ 的连通子树， 当且仅当 $R$ 是树， $VI ≤ V ，EI ≤ E$， 定义 $R$ 的权值 $ω(R) = ω(EI)$。定义 $S ≤ V$ 的 Steiner 树为 $f(S) = min{ω(R)|S ≤ VI}$，其中 $R(VI, EI)$ 是连通子树.

我有 $q$ 次询问，第 $i$ 次给出 $Li, Ri, ki$，请你给出 $max{f(S)|S ≤ {VLi, VLi+1, . . . , VR i}, |S| = ki}$.

Format

Input

第一行一个整数 $n$。

下面 $n — 1$ 行，每行三个整数 $a,b,z$，表示 $(Va, Vb) ∈ E$，且 $ω[(Va, Vb)] = z$。保证 $1 ≤ z ≤ 109$. 下面一行一个整数 $q$ 。

下面 $q$ 行，第 $i$ 行三个整数 $Li, Ri, ki$. 保证 $1 ≤ Li ≤ Li + ki — 1 ≤ Ri ≤ n$.

Output

$q$ 行，每行一个整数表示答案。

Samples

10
1  2  2
2  3  3
3  4  2
1  5  7
2  6  7
4  7  1
1  8  3
4  9  6
7  10  4
10
5  10  5
4  9  6
10  10  1
2  6  3
6  9  3
6  9  4
7  9  2
1  3  2
1  7  3
3  8  3

35
31
0
21
23
24
16
5
22
22

Limitation

需要注意：在搜集本题目数据时没有config.yaml，以下子任务信息仅供参考
设 $K = max_{ki}$。

对所有数据，保证 $1 ≤ n ≤ 3 × 105$ , $1 ≤ q ≤ 104$, $K ≤ 100$.

$n, q ≤ 10$（ 15 分）；

$n, q ≤ 100$（ 15 分）；

$n, q ≤ 1000$（ 10 分）；

$n, q ≤ 5000$（ 10 分）；

$K = 2$（ 15 分）；

$K = 3$（ 15 分）；

$K ≤ 10$（ 10 分）；

没有特殊性质（10 分）。