Gặp gỡ

Đất nước Z có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\). Có đúng \(n-1\) con đường hai chiều nối giữa các thành phố thỏa mãn điều kiện: có thể đi từ thành phố bất kì đến tất cả các thành phố còn lại theo đường trực tiếp hoặc gián tiếp qua các thành phố khác.

Đất nước Z thường có các sự kiện văn hóa lớn, mỗi lần sự kiện sẽ được tổ chức tại một thành phố, điều này ảnh hưởng tới chi phí di chuyển trên các con đường. Cụ thể, nếu thành phố \(u\) là thành phố tổ chức sự kiện văn hóa, khi đó các con đường hướng tới thành phố \(u\) sẽ có chi phí là \(a\) còn các con đường đi xa thành phố \(u\) sẽ có chi phí là \(b\). Con đường từ thành phố \(i\) tới thành phố \(j\) được gọi là hướng tới \(u\) nếu đường đi ngắn nhất từ \(i\) tới \(u\) dài hơn đường đi ngắn nhất từ \(j\) tới \(u\), ngược lại thì con đường từ \(i\) tới \(j\) được gọi là đi xa thành phố \(u\).

Khi sự kiện văn hóa diễn ra, một người di chuyển qua \(s\) con đường sẽ bị mất chi phí bằng tổng của từng lần di chuyển, lần di chuyển thứ \(k\) (\(1 \le k \le s\)) sẽ mất chi phí \(k \times cost_k\), trong đó \(cost_k\) bằng \(a\) hoặc \(b\) tùy thuộc lần di chuyển thứ \(k\) đang đi qua con đường hướng tới thành phố tổ chức sự kiện hay đi xa thành phố tổ chức sự kiện.

Một câu hỏi thường gặp ở đất nước Z là: nếu sự kiện văn hóa diễn ra tại thành phố \(u\), có hai người ở thành phố \(i\) và thành phố \(j\) thì chi phí nhỏ nhất để hai người đó gặp nhau tại một thành phố nào đó là bao nhiêu?

Yêu cầu: Cho thông tin về các con đường của đất nước Z và \(q\) câu hỏi, mỗi lệnh hỏi được mô tả bằng \(5\) số \(u, i, j, a, b\). Hãy tìm chi phí nhỏ nhất để hai người gặp nhau.

Input

Dữ liệu vào từ bàn phím gồm:

• Dòng 1: chứa số nguyên dương \(n\) và \(q\) (\(n, q \le 10^5\)).

• \(n-1\) dòng tiếp theo, mỗi dòng chứa số nguyên \(x\) và \(y\) mô tả có con đường nối thành phố \(x\) với thành phố \(y\) (\(1 \le x, y \le n\), \(x \ne y\)).

• \(q\) dòng tiếp theo, mỗi dòng chứa \(5\) số nguyên dương \(u, i, j, a, b\) (\(1 \le u, i, j \le n\); \(i \ne j\); \(a, b \le 10^6\)).

Ràng buộc:

• Có \(20\%\) số test với \(n, q \le 100\).

• Có \(20\%\) số test khác có \(n, q \le 1000\).

• Có \(20\%\) số test khác có \(n \le 2000\), \(q \le 10^5\).

• Có \(20\%\) số test khác có \(n, q \le 10^5\) và \(b \ge n \times a\).

• Có \(20\%\) số test còn lại không có ràng buộc bổ sung.

Output

Ghi ra màn hình gồm \(q\) dòng, mỗi dòng ghi kết quả tương ứng với lệnh hỏi đầu vào.

Example

Input:

8 2
1 2
5 6
5 3
4 3
8 2
3 1
7 5
3 3 2 5 2
5 8 7 8 12

Output:

6
80

Note

Lệnh hỏi 1: Hai người gặp nhau ở thành phố \(2\). Chi phí của người thứ nhất: \(2 + 2 \times 2 = 6\). Chi phí của người thứ hai: \(0\). Tổng chi phí là \(6\).

Lệnh hỏi 2: Hai người gặp nhau ở thành phố \(3\). Chi phí của người thứ nhất: \(8 + 8 \times 2 + 8 \times 3 = 48\). Chi phí của người thứ hai: \(8 + 12 \times 2 = 32\). Tổng chi phí là \(80\).