Tourism business

Octorabbit Kingdom has $N$ cities connected by $N-1$ roads. From any city, you can reach any other city using only roads, so the country forms a tree. Each road has a positive integer length. The distance between two cities is the sum of the road lengths on the simple path that connects them.

For a new tourism project, the country picks two cities $X$ and $Y$ and makes them tourism sister cities. Once paired, people from each city travel to visit the other. Let $D(X,Y)$ be the distance between $X$ and $Y$, and let $C_X$ and $C_Y$ be the populations living in $X$ and $Y$. The transport fee income is $(C_X+C_Y) \times D(X,Y)$.

The country is going through upheaval, so city populations keep changing, and the cities that want to join vary from situation to situation. The country needs to find the right pairs for many different situations.

There are $Q$ sister city plans. Each plan gives a set $A$ of candidate cities for $X$ and a set $B$ of candidate cities for $Y$, along with the population $C_u$ of each candidate city. No city is in both $A$ and $B$.

For each plan, find the maximum transport fee income that can be obtained by choosing $X$ and $Y$.

The first line contains $N$ and $Q$, separated by a space. ($1 \leq N \leq 300\ 000$, $1 \leq Q \leq 100\ 000$)

The next $N-1$ lines each contain $u$, $v$, and $d$, separated by spaces. The $i$-th road connects city $u$ and city $v$, and has length $d$. ($1 \leq u,v \leq N$, $1 \leq d \leq 30$)

Then the $Q$ plans follow in this format.

• The first line contains $N_A$ and $N_B$, separated by a space. $N_A$ is the size of $A$, and $N_B$ is the size of $B$. ($1 \leq N_A,N_B, N_A+N_B \leq N$)
• The next $N_A$ lines each contain $u$ and $p$, separated by a space. City $u$ belongs to set $A$ and has a population of $p$, that is, $C_u=p$. ($1 \leq u \leq N$, $1 \leq p \leq 3 \times 10^6$)
• The next $N_B$ lines each contain $v$ and $q$, separated by a space. City $v$ belongs to set $B$ and has a population of $q$, that is, $C_v=q$. ($1 \leq v \leq N$, $1 \leq q \leq 3 \times 10^6$)

The sum $\sum_{i=1}^{Q} (N_A+N_B)$ is at most $200\ 000$.

Print the maximum transport fee income for each sister city plan on its own line, in order.

When $X=3$ and $Y=7$, the transport fee income is $(5+1) \times 17=102$, which is optimal. $X=1$ and $Y=5$ is also optimal.