$N$개의 정점으로 이루어진 트리 $T$가 주어진다. 각 간선은 양의 정수 가중치를 가진다. 트리 $T$에서 경로 $P$의 가중치는 $P$에 포함된 간선들의 가중치 합으로 정의되며, 이를 $W(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 \cdot W(P_1) + B \cdot W(P_2)$의 값을 최대화해야 한다.

각 쿼리에 대해 $A \cdot W(P_1) + B \cdot W(P_2)$의 최댓값을 출력하시오.

입력

첫 번째 줄에는 두 개의 정수 $N$과 $Q$가 공백으로 구분되어 주어진다.

다음 $N - 1$개의 줄에는 각각 세 개의 정수 $u, v, w$가 공백으로 구분되어 주어진다. 이는 트리 $T$에 가중치 $w$를 가진 정점 $u$와 $v$를 잇는 간선이 존재함을 의미한다. 이 간선들은 트리를 구성한다.

다음 $Q$개의 줄에는 각각 하나의 쿼리를 나타내는 네 개의 정수 $u, v, A, B$가 공백으로 구분되어 주어진다.

• $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 \cdot 10^9$

출력

각 쿼리에 대해 $A \cdot W(P_1) + B \cdot W(P_2)$의 최댓값을 한 줄에 하나씩 출력하시오.

예제

입력 1

6 4
1 2 4
2 5 5
2 3 7
3 6 5
3 4 4
1 4 1 1
1 4 2 1
5 6 1 1
5 6 1 10

출력 1

18
32
18
160