Đề bài

"Sống bên bờ vực!" là một chương trình truyền hình mới dành cho những người yêu thích lý thuyết đồ thị. Trong mỗi tập, người dẫn chương trình đưa ra một bài toán mới cho các thí sinh. Người giải được bài toán sẽ giành giải thưởng lớn: một chuyến đi trọn gói đến bờ biển Croatia, kèm theo chuyến tham quan có hướng dẫn theo một chu trình Euler quanh những bức tường nổi tiếng của Dubrovnik.

Tomislav may mắn được chọn tham gia tập tiếp theo và lập tức bắt đầu chuẩn bị. Cậu trải qua nhiều đêm trong thư viện để đọc những định lý ít người biết nhất. Một đêm, cậu vô tình ngủ quên và mơ thấy mình xuất hiện trong chương trình. Khi tỉnh dậy, cậu vẫn nhớ rõ bài toán được đưa ra và việc mình đã không giải được nó.

Người dẫn chương trình vẽ hai cây có gốc, mỗi cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\). Hai cây được đánh số \(1\) và \(2\). Cả hai cây đều có trọng số dương trên các cạnh, nhưng các trọng số được giữ bí mật. Sau đó, Tomislav được chọn một tập con bất kỳ gồm đúng \(K\) nhãn đỉnh.

Sau khi chọn tập con, Tomislav được hỏi nhiều nhất \(Q\) câu hỏi dạng \((a,b)\), trong đó \(a\) và \(b\) là các nhãn đỉnh. Với mỗi câu hỏi, người dẫn trả về bộ bốn có thứ tự

Ở đây, \(d_t(x,y)\) là tổng trọng số các cạnh trên đường đi duy nhất giữa hai đỉnh \(x\) và \(y\) trong cây \(t\), còn \(l_t\) là nhãn của tổ tiên chung thấp nhất của \(a\) và \(b\) trong cây \(t\), tức là đỉnh xa gốc nhất nhận cả \(a\) và \(b\) làm hậu duệ, không nhất thiết là hậu duệ trực tiếp.

Để giành giải, Tomislav phải trả lời đúng chính xác \(T\) câu hỏi của người dẫn, mỗi câu có dạng \((p,q)\) với \(p\) và \(q\) đều thuộc tập con đã chọn. Với mỗi câu hỏi, Tomislav phải trả về khoảng cách giữa \(p\) và \(q\) trong cả hai cây, tức là bộ đôi

Hãy viết chương trình giúp Tomislav giải bài toán trong giấc mơ.

Giao tiếp

Đây là bài tương tác. Chương trình của bạn đóng vai Tomislav và giao tiếp với chương trình của ban tổ chức, chương trình này đóng vai người dẫn.

Trước tiên, chương trình đọc một dòng chứa bốn số nguyên \(N\), \(K\), \(Q\) và \(T\), cách nhau bởi dấu cách.

Tiếp theo, chương trình đọc mô tả của hai cây trên hai dòng: dòng đầu mô tả cây thứ nhất và dòng thứ hai mô tả cây thứ hai. Mỗi cây được cho bởi \(N\) số nguyên \(p_1,p_2,\ldots,p_N\), trong đó \(p_i\in\{-1,1,2,\ldots,N\}\) là cha của đỉnh \(i\), hoặc bằng \(-1\) nếu cây có gốc tại đỉnh \(i\).

Sau đó, chương trình phải in \(K\) số nguyên đôi một khác nhau \(x_1,x_2,\ldots,x_K\) \((1\le x_i\le N)\), cách nhau bởi dấu cách. Đây là tập nhãn đỉnh Tomislav chọn. Hãy đẩy dữ liệu đầu ra sau khi in dòng này.

Chương trình được phép hỏi nhiều nhất \(Q\) câu hỏi. Mỗi câu hỏi được in trên một dòng theo dạng:

? a b

với \(1\le a,b\le N\). Khi đã hỏi xong, chương trình phải in riêng ký tự ! trên một dòng rồi đẩy dữ liệu đầu ra.

Sau đó, chương trình đọc câu trả lời cho từng câu hỏi đã đặt, theo đúng thứ tự. Mỗi câu trả lời là một dòng chứa bốn số nguyên

Tiếp theo, chương trình đọc toàn bộ \(T\) câu hỏi của người dẫn. Mỗi câu hỏi nằm trên một dòng và gồm hai số nguyên \(p\) và \(q\), với \(p,q\in\{x_1,x_2,\ldots,x_K\}\).

Cuối cùng, với mỗi câu hỏi \((p,q)\) theo đúng thứ tự nhận được, chương trình in một dòng gồm hai số nguyên \(d_1(p,q)\) và \(d_2(p,q)\). Sau khi in đủ \(T\) câu trả lời, chương trình phải đẩy dữ liệu đầu ra lần cuối.

Bạn có thể tải mã nguồn mẫu từ hệ thống chấm. Mã nguồn này giao tiếp đúng với chương trình của ban tổ chức, bao gồm việc đẩy dữ liệu đầu ra, và giải được ví dụ đầu tiên.

Ràng buộc

Các trọng số cạnh bí mật là số nguyên dương không vượt quá \(2\,000\).

Trong tất cả các subtask:

• \(2\le K\le 100\,000\).
• \(1\le T\le\min(K^2,100\,000)\).

Phân nhóm

• Subtask 1 (10 điểm): \(N=500\,000\), \(Q=K-1\), hai cây giống hệt nhau, kể cả các trọng số cạnh bí mật.
• Subtask 2 (25 điểm): \(N=500\,000\), \(Q=2K-2\).
• Subtask 3 (19 điểm): \(N=500\,000\), \(K=200\), \(Q=K-1\).
• Subtask 4 (22 điểm): \(N=1\,000\,000\), \(K=1\,000\), \(Q=K-1\).
• Subtask 5 (24 điểm): \(N=1\,000\,000\), \(Q=K-1\).

Ví dụ giao tiếp

![Hai cây có trọng số trong ví dụ; các đỉnh thuộc tập được chọn được tô màuhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_879e7f39.png

Trong ví dụ này, chương trình chọn tập \(\{1,5,7\}\). Sau đó, chương trình hỏi hai câu \((1,5)\) và \((1,7)\).

Với câu hỏi thứ nhất, tổ tiên chung thấp nhất của \(1\) và \(5\) lần lượt là \(l_1=1\) và \(l_2=7\). Câu trả lời là

Với câu hỏi thứ hai, tổ tiên chung thấp nhất của \(1\) và \(7\) lần lượt là \(l_1=1\) và \(l_2=7\). Câu trả lời là

Cuối cùng, chương trình nhận các câu hỏi \((1,7)\), \((7,5)\) và \((5,1)\). Các câu trả lời tương ứng là \((3,5)\), \((5,3)\) và \((2,8)\).