Trong Vương quốc IOI có \(N\) thành phố, được đánh số từ \(0\) đến \(N-1\). Các thành phố được nối bởi \(N-1\) con đường hai chiều, và có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác.

Vương quốc có nhiều công ty sản xuất linh kiện đặc biệt. Mỗi công ty chỉ sản xuất một loại linh kiện, và không có hai công ty nào sản xuất cùng một loại. Mỗi công ty có ít nhất một nhà máy; mỗi nhà máy nằm tại một thành phố, và một thành phố có thể có nhà máy của nhiều công ty.

Đôi khi một công ty cần linh kiện của một công ty khác. Nếu công ty \(C_A\) cần linh kiện của công ty \(C_B\) với \(C_A \ne C_B\), linh kiện có thể được vận chuyển từ bất kỳ nhà máy nào của \(C_B\) đến bất kỳ nhà máy nào của \(C_A\). Hai nhà máy được chọn sao cho khoảng cách vận chuyển là nhỏ nhất.

Cho cây đường của vương quốc và \(Q\) truy vấn. Trong truy vấn thứ \(j\), công ty \(U_j\) có nhà máy tại các thành phố \(X_{j,0},\ldots,X_{j,S_j-1}\) cần linh kiện của công ty \(V_j\) có nhà máy tại các thành phố \(Y_{j,0},\ldots,Y_{j,T_j-1}\). Với mỗi truy vấn, hãy trả về khoảng cách vận chuyển nhỏ nhất.

Chi tiết cài đặt

Bài nộp phải khai báo:

#include "factories.h"

và cài đặt chính xác hai hàm sau:

void Init(int N, int A[], int B[], int D[]);
long long Query(int S, int X[], int T, int Y[]);

Hàm Init được gọi đúng một lần lúc bắt đầu.

• N là số thành phố.
• A, B, D là các mảng độ dài \(N-1\).
• Với mỗi \(0 \le i \le N-2\), có một con đường độ dài D[i] nối A[i] và B[i].

Hàm Query được gọi một lần cho mỗi truy vấn.

• S và T lần lượt là số thành phố có nhà máy của hai công ty.
• X là mảng độ dài S chứa các thành phố có nhà máy của công ty cần nhận linh kiện.
• Y là mảng độ dài T chứa các thành phố có nhà máy của công ty cung cấp linh kiện.
• Hàm phải trả về khoảng cách nhỏ nhất giữa một thành phố trong X và một thành phố trong Y.

Bài nộp không được cài đặt hàm main.

Định dạng bộ chấm mẫu

Bộ chấm mẫu đọc:

• Dòng đầu gồm \(N,Q\).
• \(N-1\) dòng tiếp theo, dòng thứ \(i+1\) gồm \(A_i,B_i,D_i\).
• Mỗi truy vấn gồm ba dòng: dòng đầu chứa \(S_j,T_j\); dòng sau chứa \(S_j\) số \(X_{j,0},\ldots,X_{j,S_j-1}\); dòng cuối chứa \(T_j\) số \(Y_{j,0},\ldots,Y_{j,T_j-1}\).

Bộ chấm mẫu in giá trị trả về bởi từng lời gọi Query, mỗi giá trị trên một dòng.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(1 \le Q \le 100\,000\).
• \(0 \le A_i,B_i \le N-1\) và \(A_i \ne B_i\).
• \(1 \le D_i \le 100\,000\,000\).
• Các con đường nối mọi thành phố thành một cây.
• \(1 \le S_j,T_j \le N-1\).
• Mọi phần tử của X và Y nằm trong đoạn \([0,N-1]\).
• Trong mỗi truy vấn, tất cả thành phố xuất hiện trong X và Y đôi một khác nhau.

Phân nhóm

• Nhóm 1 (15 điểm): \(N,Q \le 5\,000\)
• Nhóm 2 (18 điểm): \(S_j,T_j \le 10\) với mọi truy vấn
• Nhóm 3 (67 điểm): Không có ràng buộc bổ sung

Ví dụ

7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5

12
3
11