K. Two Paths
time limit per test
7 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You are given a tree $$$T$$$ consisting of $$$N$$$ vertices. Each edge has a positive integer weight. The weight of a path $$$P$$$ in $$$T$$$ is defined as the sum of weights of edges in $$$P$$$, denoted by $$$W(P)$$$.

You are given a total of $$$Q$$$ queries, each containing two vertices, $$$u$$$ and $$$v$$$, and two integers, $$$A$$$ and $$$B$$$. For each query, you are to find two simple paths $$$P_1$$$ and $$$P_2$$$ in $$$T$$$ satisfying the following requirements.

  • $$$P_1$$$ and $$$P_2$$$ don't share a vertex.
  • $$$P_1$$$ starts from $$$u$$$, and $$$P_2$$$ starts from $$$v$$$.
  • Among all $$$P_1$$$ and $$$P_2$$$ satisfying the conditions above, the value of $$$A \cdot W(P_1) + B \cdot W(P_2)$$$ should be maximized.

You should output the value of $$$A \cdot W(P_1) + B \cdot W(P_2)$$$ for each query.

Input

The first line contains two space-separated integers $$$N$$$ and $$$Q$$$.

Each of the following $$$N - 1$$$ lines contains three space-separated integers $$$u$$$, $$$v$$$, $$$w$$$. This means that there is an edge in $$$T$$$ connecting vertices $$$u$$$ and $$$v$$$ with weight $$$w$$$. Together these edges form a tree.

Each of the following $$$Q$$$ lines contains four space-separated integers $$$u$$$, $$$v$$$, $$$A$$$, $$$B$$$, denoting a single query.

  • $$$2 \le N \le 200\,000$$$
  • $$$1 \le Q \le 500\,000$$$
  • $$$1 \le u \lt v \le N$$$ for both edges and queries
  • $$$1 \le w \le 10\,000$$$
  • $$$1 \le A, B \le 2\cdot 10^9$$$
Output

For each query, output a single line with an integer: the maximum possible value of $$$A \cdot W(P_1) + B \cdot W(P_2)$$$.

Example
Input
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
Output
18
32
18
160