Cho một cây \(n\) đỉnh có trọng số, định nghĩa \(f(u,v)\) là hiệu giữa trọng số cạnh lớn nhất và nhỏ nhất trên đường đi đơn từ \(u\) đến \(v\), hay đặt \(w_1\) là trọng số cạnh nhỏ nhất trên đường đi từ \(u\) đến \(v\), \(w_2\) là trọng số cạnh lớn nhất trên đường đi từ \(u\) đến \(v\) thì \(f(u,v)=w_2-w_1\).

Cho \(q\) truy vấn, mỗi truy vấn đưa ra số nguyên dương \(k\) \((k\leq n)\) và \(k\) đỉnh phân biệt \(u_1,u_2,...,u_k\) và yêu cầu tính giá trị của \(\sum_{i=1}^{k-1}{\sum_{j=i+1}^{k}} f(u_i,u_j)\).

Hãy trả lời các truy vấn trên.

Input

• Dòng \(1\) chứa hai số nguyên dương \(n,q\) \((1\leq n,q \leq 10^5)\).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u,v,w\) thể hiện cạnh nối trực tiếp giữa \(u\) và \(v\) có trọng số \(w\) trên cây \((1\leq u,v \leq n,u\neq v,1\leq w\leq 10^6)\).
• \(q\) dòng tiếp theo, mỗi dòng có \(k+1\) số nguyên dương lần lượt là \(k,u_1,u_2,...,u_k\) cho mỗi truy vấn. Dữ liệu đảm bảo tổng \(k\) trong các truy vấn không vượt quá \(3\cdot10^5\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số nguyên dương duy nhất là đáp án cho truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n,q\leq 500\).
• Subtask \(2\) (\(10\%\) số điểm): \(n,q\leq 1000\).
• Subtask \(3\) (\(20\%\) số điểm): \(q=1,n\leq 10^5\).
• Subtask \(4\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

Sample input

10 3
2 1 7
1 3 12
1 4 12
4 5 11
2 6 12
1 7 8
7 8 11
9 4 4
10 4 2
3 8 10 1 
3 5 3 8 
2 1 2 

23
9
0

Note

Giải thích truy vấn \(1\):

• \(f(8,10)=12-2=10\).
• \(f(8,1)=11-8=3\).
• \(f(10,1)=12-2=10\).

Đáp số là \(10+3+10=23\).