Factories

The kingdom of IOI has $N$ cities numbered $0$ through $N-1$. The cities are joined by $N-1$ two-way roads, and you can travel from any city to any other city along a few of these roads.

Many companies in the kingdom make special products. Each company makes exactly one kind of product, and no two companies make the same kind. Every company owns one or more factories, and each factory is built in one of the cities. Several companies may own factories in the same city.

Sometimes a company $C_A$ needs the product of another company $C_B$ ($C_A \ne C_B$). The product is then carried from one factory of $C_B$ to one factory of $C_A$. The two companies choose the pair of factories that makes the distance between them as small as possible.

You are first given the number of cities and the roads of the kingdom, then $Q$ queries. Query $j$ reads as follows. Company $U_j$, which owns factories in cities $X_{j,0}, \dots, X_{j,S_j-1}$, needs the product of company $V_j$, which owns factories in cities $Y_{j,0}, \dots, Y_{j,T_j-1}$. For each query, report the smallest distance needed to carry the product.

The first line contains two integers $N$ and $Q$ separated by a space. The kingdom has $N$ cities and your program is given $Q$ queries.

Line $i+1$ of the next $N-1$ lines ($0 \le i \le N-2$) contains three integers $A_i$, $B_i$, $D_i$ separated by spaces. There is a road of length $D_i$ between city $A_i$ and city $B_i$.

The next $3Q$ lines hold the queries. The information of query $j$ ($0 \le j \le Q-1$) occupies lines $3j+1$ through $3j+3$.

Line $3j+1$ contains two integers $S_j$ and $T_j$ separated by a space. Company $U_j$ owns factories in $S_j$ cities and company $V_j$ owns factories in $T_j$ cities.

Line $3j+2$ contains the $S_j$ integers $X_{j,0}, \dots, X_{j,S_j-1}$ separated by spaces. Company $U_j$ owns factories in these cities.

Line $3j+3$ contains the $T_j$ integers $Y_{j,0}, \dots, Y_{j,T_j-1}$ separated by spaces. Company $V_j$ owns factories in these cities.

Every input satisfies the following conditions.

• $2 \le N \le 500\,000$
• $1 \le Q \le 100\,000$
• $0 \le A_i \le N-1$, $0 \le B_i \le N-1$, $A_i \ne B_i$ ($0 \le i \le N-2$)
• $1 \le D_i \le 100\,000\,000$ ($0 \le i \le N-2$)
• You can reach every other city from any city along the roads.
• $1 \le S_j \le N-1$, $1 \le T_j \le N-1$ ($0 \le j \le Q-1$)
• $0 \le X_{j,k} \le N-1$ ($0 \le k \le S_j-1$), $0 \le Y_{j,k} \le N-1$ ($0 \le k \le T_j-1$)
• Within one query, $X_{j,0}, \dots, X_{j,S_j-1}, Y_{j,0}, \dots, Y_{j,T_j-1}$ are pairwise different.
• $S_0 + S_1 + \dots + S_{Q-1} \le 1\,000\,000$
• $T_0 + T_1 + \dots + T_{Q-1} \le 1\,000\,000$

Print the answer to each query on its own line, in the order the queries are given.

The three queries of the example are answered as follows.

• In query 0, company $U_0$ owns factories in cities 0 and 6, and company $V_0$ owns factories in cities 3 and 4. The shortest route runs from the factory of $V_0$ in city 3 to the factory of $U_0$ in city 6, and its length is 12.
• In query 1, company $U_1$ owns factories in cities 0, 1 and 3, and company $V_1$ owns factories in cities 4 and 6. The shortest route runs from the factory of $V_1$ in city 6 to the factory of $U_1$ in city 1, and its length is 3.
• In query 2, company $U_2$ owns a factory in city 2 and company $V_2$ owns a factory in city 5. The distance from the factory of $V_2$ in city 5 to the factory of $U_2$ in city 2 is 11.