Aqua Hoshino gives you a tree $T(V=\{V_1,V_2,\ldots,V_n\},E)$ with edge weights $\omega: E \mapsto \mathbb{Z^+}$.

The weight of a subset $S \subseteq E$ is defined as $\omega(S)=\sum_{e \in S} \omega(e)$.

A $\textbf{connected subtree}$ $R(V',E')$ of $T$ is defined such that $R$ is a tree, $V' \subseteq V$, and $E' \subseteq E$.

The weight of $R$ is defined as $\omega(R)=\omega(E')$.

The Steiner tree of a subset $S \subseteq V$ is defined as $f(S)=\min \{\omega(R) \mid S \subseteq V'\}$, where $R(V',E')$ is a connected subtree.

There are $q$ queries. For each query $i$, you are given $L_i, R_i, k_i$. Calculate $\max \{f(S) \mid S \subseteq \{V_{L_i},V_{L_{i}+1},\ldots,V_{R_i}\},|S|=k_i\}$.

Input

The first line contains an integer $n$.

The next $n-1$ lines each contain three integers $a, b, z$, representing an edge $(V_a, V_b) \in E$ with weight $\omega[(V_a, V_b)]=z$. It is guaranteed that $1 \le z \le 10^9$.

The next line contains an integer $q$.

The next $q$ lines each contain three integers $L_i, R_i, k_i$. It is guaranteed that $1 \le L_i \le L_i + k_i - 1 \le R_i \le n$.

Output

Output $q$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

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

Output 1

35
31
0
21
23
24
16
5
22
22

Subtasks

Idea: nzhtl1477, Solution: rushcheyo & nzhtl1477, Code: rushcheyo, Data: rushcheyo

This problem uses subtask evaluation.

Let $K=\max\{k_i\}$.

For all test cases, it is guaranteed that $1 \le n \le 3 \times 10^5, 1 \le q \le 10^4, K \le 100$.

1. $n, q \le 10$ (15 points);
2. $n, q \le 100$ (15 points);
3. $n, q \le 1000$ (10 points);
4. $n, q \le 5000$ (10 points);
5. $K=2$ (15 points);
6. $K=3$ (15 points);
7. $K \le 10$ (10 points);
8. No special properties (10 points).