관광 사업

옥토끼나라는 $N$개의 도시를 잇는 $N-1$개의 도로로 이루어진 나라다. 어떤 도시에서든 도로만 따라 원하는 다른 도시로 이동할 수 있으므로, 옥토끼나라는 트리 구조다. 각 도로는 자연수 길이를 가지며, 두 도시 사이의 거리는 두 도시를 잇는 단순 경로 위 도로 길이의 합이다.

옥토끼나라는 새 관광 사업으로 두 도시 $X$와 $Y$를 골라 관광 자매결연을 맺는다. 자매결연을 맺으면 두 도시의 주민들이 서로 관광하러 이동한다. $D(X,Y)$를 $X$와 $Y$ 사이의 거리, $C_X$와 $C_Y$를 각각 $X$와 $Y$에 거주하는 인구 수라고 하면, 교통료 수익은 $(C_X+C_Y) \times D(X,Y)$다.

옥토끼나라는 요즘 격변을 겪고 있어 도시의 인구 수가 계속 바뀌고, 자매결연에 참가하려는 도시도 상황마다 다르다. 그래서 여러 상황에서 자매결연을 맺을 도시를 골라야 한다.

$Q$개의 자매결연 계획이 주어진다. 각 계획에는 $X$의 후보 도시 집합 $A$, $Y$의 후보 도시 집합 $B$, 그리고 각 후보 도시의 인구 수 $C_u$가 주어진다. $A$와 $B$에 동시에 포함되는 도시는 없다.

각 자매결연 계획마다 $X$와 $Y$를 정해 얻을 수 있는 최대 교통료 수익을 구한다.

1행에 $N$과 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 300\ 000$, $1 \leq Q \leq 100\ 000$)

이어지는 $N-1$개의 줄에 도로 정보 $u$, $v$, $d$가 공백으로 구분되어 주어진다. $i$번째 도로는 도시 $u$와 도시 $v$를 잇고, 길이는 $d$다. ($1 \leq u,v \leq N$, $1 \leq d \leq 30$)

이후 $Q$개의 자매결연 계획이 다음 형식으로 주어진다.

• 첫 줄에 $N_A$와 $N_B$가 공백으로 구분되어 주어진다. $N_A$는 $A$의 크기, $N_B$는 $B$의 크기다. ($1 \leq N_A,N_B, N_A+N_B \leq N$)
• 이어지는 $N_A$개의 줄에 $u$와 $p$가 공백으로 구분되어 주어진다. 도시 $u$는 집합 $A$에 속하며, 거주 인구 수는 $p$명, 즉 $C_u=p$다. ($1 \leq u \leq N$, $1 \leq p \leq 3 \times 10^6$)
• 이어지는 $N_B$개의 줄에 $v$와 $q$가 공백으로 구분되어 주어진다. 도시 $v$는 집합 $B$에 속하며, 거주 인구 수는 $q$명, 즉 $C_v=q$다. ($1 \leq v \leq N$, $1 \leq q \leq 3 \times 10^6$)

$\sum_{i=1}^{Q} (N_A+N_B)$는 $200\ 000$ 이하다.

각 자매결연 계획의 최대 교통료 수익을 입력된 순서대로 한 줄에 하나씩 출력한다.

$X=3$이고 $Y=7$인 경우 교통료 수익이 $(5+1) \times 17=102$로 최적이다. $X=1$이고 $Y=5$인 경우도 최적이다.