두 경로

정점이 $N$개인 트리 $T$가 주어진다. 각 간선에는 양의 정수 가중치가 있다. 경로 $P$의 가중치 $W(P)$는 $P$에 포함된 간선 가중치의 합이다.

총 $Q$개의 질의가 주어진다. 각 질의는 정점 $u$, $v$와 정수 $A$, $B$로 이루어진다. 각 질의마다 다음 조건을 만족하는 단순 경로 $P_1$, $P_2$를 찾는다.

• $P_1$과 $P_2$는 정점을 공유하지 않는다.
• $P_1$은 $u$에서 시작하고, $P_2$는 $v$에서 시작한다.

이 조건을 만족하는 모든 $P_1$, $P_2$ 중에서 $A \times W(P_1) + B \times W(P_2)$가 최대가 되는 값을 구한다.

첫 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다.

이어서 $N-1$개의 줄에 간선 정보 $u$, $v$, $w$가 주어진다. 이는 정점 $u$와 $v$를 가중치 $w$인 간선이 잇는다는 뜻이다.

그다음 $Q$개의 줄에 질의 정보 $u$, $v$, $A$, $B$가 주어진다.

각 질의에 대해 $A \times W(P_1) + B \times W(P_2)$의 최대값을 한 줄에 하나씩 출력한다.

• $2 \le N \le 200\,000$
• $1 \le Q \le 500\,000$
• 간선과 질의 모두에 대해 $1 \le u < v \le N$
• $1 \le w \le 10\,000$
• $1 \le A, B \le 2 \times 10^9$