Note

The time limit for this problem is $3$ seconds.

Problem Statement

I-wate has $N$ towns, $N-1$ railway lines, and $K$ airlines.

Railway line $i(1 \le i < N)$ connects town $A_i$ and town $B_i$; by paying $C_i$ yen, you can travel between town $A_i$ and town $B_i$ in either direction. Also, any two towns can reach each other using railway lines alone.

Airline $i(1 \le i \le K)$ has airports in $M_i$ towns $X_{i,1},X_{i,2},\dots,X_{i,M_i}$; by paying $P_i$ yen, you can travel from any town to any other town among the $M_i$ towns where airline $i$ has airports.

Vil, who plans to take a trip to I-wate next spring, cannot decide which of his current candidate travel plans to choose. To select a plan, for each of the $Q$ pairs of towns $(U_1,V_1),(U_2,V_2),\dots,(U_Q,V_Q)$, he wants to know the minimum amount of money required to travel from one to the other. Vil is not good at calculations, so please compute these on his behalf.

Input

$N\ K$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_{N-1}\ B_{N-1}\ C_{N-1}$
$M_1\ P_1$
$X_{1,1}\ X_{1,2}\ \dots\ X_{1,M_1}$
$M_2\ P_2$
$X_{2,1}\ X_{2,2}\ \dots\ X_{2,M_2}$
$\vdots$
$M_K\ P_K$
$X_{K,1}\ X_{K,2}\ \dots\ X_{K,M_K}$
$Q$
$U_1\ V_1$
$U_2\ V_2$
$\vdots$
$U_Q\ V_Q$

• All input values are integers.
• $2 \le N \le 10^5$
• $0 \le K \le 10$
• $1 \le A_i < B_i \le N$
• $1 \le C_i \le 10^9$
• Any two towns can reach each other using railway lines alone.
• $2 \le M_i \le N$
• $\displaystyle \sum_{i=1}^{K}M_i \le 10^5$
• $1 \le P_i \le 10^9$
• $1 \le X_{i,j} \le N$
• If $j \neq k$, then $X_{i,j} \neq X_{i,k}$.
• $1 \le Q \le 10^5$
• $1 \le U_i < V_i \le N$

Output

Output $Q$ lines.

On line $i(1 \le i \le Q)$, output the minimum amount of money required to travel from town $U_i$ to town $V_i$, followed by a newline.

Sample

5 1
1 4 6
3 5 12
1 2 8
2 3 2
4 10
2 4 5 3
3
1 3
1 4
1 5

10
6
16

7 2
4 7 2
2 5 5
3 6 14
1 2 16
2 3 6
2 4 17
3 1
5 7 3
3 3
3 7 2
6
4 7
1 2
1 3
2 6
1 5
3 7

2
16
19
17
20
1