Thi thử vòng 2 2022 - ngày 2

Năm 2015, trường Mầm non chuyên Bắp Rang giành quyền đăng cai kỳ thi PreVOZ. Đến với kỳ thi, các sửu nhi thường mang đến đây những cây bút rất to, bởi theo kẻ mà ai cũng biết là ai đấy, bút to thì ... viết ... sướng lắm. Điều này có thể khiến nạn trộm cắp bút gia tăng, vì vậy đảm bảo an ninh cho kỳ thi là một vấn đề nan giải.

Hệ thống an ninh của trường gồm 3 pháo đài lớn, có thể quan sát toàn bộ trường. 3 pháo đài này do 3 nữ đại sửu nhi dẫn đầu cuộc thi Bé trẻ bé trâu vừa qua: Hà béo, Chi tồ và Linh hấp điều khiển. Ngoài ra trường còn có N đội sửu nhi cơ động để ứng phó trong trường hợp khẩn cấp.

Tổng tư lệnh phụ trách an ninh – Mr Th. đại ca, ra lệnh cho trung sửu nhi Hoàng Huy Hoàng làm trưởng đội cơ động. Mr Th. đại ca chỉ định Hoàng bố trí đội cơ động theo sơ đồ vẽ sẵn. Tuy nhiên, Hoàng đã không tuân lệnh mà bố trí các đội cơ động quanh pháo đài của một nữ sửu nhi tóc ngắn.

Nếu biểu diễn trên mặt phẳng 2D, 3 pháo đài là các điểm \(H\), \(C\) và \(L\). Mr Th. đại ca yêu cầu Hoàng đặt \(N\) đội cơ động tại các điểm \(Q_1, Q_2, ... ,Q_N\). Hoàng bố trí đội cơ động tại các điểm \(P_1, P_2, ..., P_N\).

Vị tổng tư lệnh vô cùng tức giận trước sự phản đối này, bắt Hoàng bố trí lại các đội cơ động. Nhưng để di chuyển các đội cơ động, tại mỗi bước, Hoàng phải trọn 1 trong 3 pháo đài làm tâm, thay đổi vị trí của toàn bộ \(N\) đội cơ động từ vị trí hiện tại sang vị trí là ảnh của vị trí hiện tại qua phép đối xứng qua tâm vừa chọn.

Nếu xếp lại được các đội cơ động về vị trí trong sơ đồ, Hoàng sẽ nhận được phần thưởng rất lớn từ vị tổng tư lệnh. Món tiền này giúp cậu ta tiếp tục theo đuổi cô sửu nhi tóc ngắn. Vì vậy, Hoàng cần các bạn giúp đỡ Hoàng trả lời câu hỏi: Liệu Hoàng có thể di chuyển các đội cơ động về đúng vị trí sau hữu hạn bước hay không?

Nhắc lại, ảnh của điểm \(A\) qua phép đối xứng tâm \(O\) là điểm \(B\) sao cho \(O\) là trung điểm của \(AB\).

Input

Dòng đầu tiên của file input chứa số nguyên \(T\) - số bộ test trong file. Tiếp theo là \(T\) bộ test, mỗi bộ test được mô tả trong 4 dòng như sau:

• Dòng đầu tiên chứa 6 số nguyên \(X_H, Y_H, X_C, Y_C, X_L, Y_L\) - tọa độ của 3 điểm \(H\), \(C\) và \(L\).
• Dòng thứ hai chứa số nguyên \(N\) - số đội cơ động.
• Dòng thứ ba chứa \(2N\) số nguyên \(X_{P_1}, Y_{P_1}, X_{P_2}, Y_{P_2}, ..., X_{P_N}, Y_{P_N}\) - tọa độ các điểm \(P_1, P_2, ..., P_N\).
• Dòng thứ tư chứa \(2N\) số nguyên \(X_{Q_1}, Y_{Q_1}, X_{Q_2}, Y_{Q_2}, ..., X_{Q_N}, Y_{Q_N}\) - tọa độ các điểm \(Q_1, Q_2, ..., Q_N\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) có dạng “Case #i: X”, trong đó \(X\) là kết quả của bộ test thứ \(i\): “Fall in love” nếu Hoàng có thể xếp các đội cơ động về đúng vị trí, ngược lại là “Broken heart”

Scoring

• Subtask 1 (30 điểm): \(T < 20, N < 3\), các số trong file input có giá trị tuyệt đối không quá \(25\).
• Subtask 2 (70 điểm): \(T < 200, N < 51\), các số trong file input có giá trị tuyệt đối không quá \(10^6\).

Example

Trong máy tính có 2 số \(N\) và \(C\). Bạn được cho biết trước số \(N\), nhưng số \(C\) bị giấu đi. Nhiệm vụ của bạn là đoán được số \(C\).

Để giúp bạn đoán được số \(C\), bạn được quyền giao tiếp với máy tính không quá \(64\) lần. Trong mỗi lần, bạn sẽ gửi cho máy tính một số nguyên từ \(1\) đến \(N\); tuy nhiên bạn không thể gửi cùng một số trong hai lượt khác nhau. Sau mỗi lần bạn gửi con số, hệ thống sẽ trả về một trong hai xâu \(YES\) hoặc \(NO\). Ở lượt đầu tiên, máy tính sẽ gửi ngẫu nhiên cho bạn một trong hai xâu này. Kể từ lượt thứ 2 trở đi, máy sẽ trả về \(YES\) khi và chỉ khi chênh lệch của số được gửi lần này và số được gửi ở lần ngay trước đó không bé hơn \(C\), và \(NO\) nếu ngược lại. Cụ thể, nếu bạn gửi số \(X\) trong lần thứ \(i - 1\) và số \(Y\) trong lần thứ \(i\), bạn sẽ nhận về \(YES\) ở lượt thứ \(i\) khi và chỉ khi \(|X - Y| \geq C\) và sẽ nhận về \(NO\) nếu \(|X - Y| < C\).

Trong nhiệm vụ này, mỗi test \(T\) thử nghiệm riêng biệt, để qua được một test bạn phải đoán đúng giá trị \(C\) trong các thử nghiệm đó.

Tương tác

Đây là bài toán tương tác. Mỗi test gồm \(T\) test con.

• Đầu tiên, bạn cần đọc vào giá trị \(T\).
• \(T\) test sẽ được thực hiện tuần tự, trong đó ở mỗi test:
• Bạn đọc vào số nguyên \(N\)
• Truy vấn ? X: chương trình sẽ trả lời YES nếu chênh lệnh giữa hai phần tử trong 2 lần gửi gần nhất lớn hơn hoặc bằng C và NO trong trường hợp ngược lại. Các giá trị của \(X\) trong các lần gọi hàm phải đôi một phân biệt, nếu không, bạn sẽ nhận được kết quả Wrong Answer. Trong mỗi test con, bạn được hỏi truy vấn này không quá \(64\) lần.
• Trả lời = C: đưa ra giá trị \(C\) cần tìm. Bạn chỉ được trả lời một lần với mỗi test con.

Constants

\(1 \leq C \leq N \leq 10^{18}, 1 \leq T \leq 1000\)

Subtask

• Subtask 1 (9 điểm): \(N \leq 64\)
• Subtask 2 (13 điểm): \(N \leq 125\)
• Subtask 3 (21 điểm): \(N \leq 1000\)`
• Subtask 4 (24 điểm): \(N \leq 10^9\)
• Subtask 5 (33 điểm): \(N \leq 10^{18}\)

Ví dụ

Một trong những thách thức lớn nhất sau khi kết hôn là quyết định xem ai sẽ làm công việc nhà nào trong gia đình. Cô dâu và chú rể may mắn của chúng ta đã quyết định giải quyết từng câu hỏi này bằng cách chơi một trò chơi.

Họ sẽ chơi nhiều phiên bản khác nhau của trò chơi. Các phiên bản của trò chơi sẽ được chơi trên cùng một cây có trọng số. Cây có \(N\) đỉnh, được đánh số từ \(1\) đến \(N\). Mỗi cạnh của cây được thể hiện bởi 3 số nguyên \(u, v, w\) thể hiện cạnh nối đỉnh \(u\) và đỉnh \(v\) có trọng số là \(w\).

Đối với mỗi trò chơi, cô dâu và chú rể sẽ chọn bốn thông số: \((U, V, hi, lo)\). Trò chơi sẽ được chơi trên con đường từ đỉnh \(U\) đến đỉnh \(V\) trong cây. Người chơi sẽ phủ lên một số cạnh của con đường này bằng các thẻ.

Các người chơi luân phiên thay phiên nhau, bắt đầu từ cô dâu. Trong mỗi lượt, người chơi hiện tại phải chọn một cạnh trên đường đi chưa có đặt thẻ và đặt thẻ vào cạnh đó.

Trong suốt trò chơi, người chơi duy trì một giá trị duy nhất được gọi là \(X\). Vào đầu trò chơi \(X = hi\). Khi một người chơi chọn một cạnh, họ phải chọn một cạnh có trọng số không lớn hơn \(X\). Khi đặt thẻ vào cạnh đó, \(X\) sẽ thay đổi bằng trọng số của cạnh đó.

Người chơi không thể thực hiện một nước đi hợp lệ sẽ thua cuộc. Ngoài ra, người chơi buộc phải đặt \(X\) nhỏ hơn \(lo\) (bằng cách đặt một thẻ lên một cạnh có trọng lượng nhỏ hơn \(lo\)) sẽ thua trò chơi.

Có \(Q\) truy vấn, mỗi truy vấn có dạng \((U, V, hi)\). Đối với mỗi truy vấn, bạn hãy in ra số giá trị \(lo\) trong phạm vi \([0, hi]\) để chú rể sẽ thắng trò chơi nếu cả cô dâu và chú rể đều chơi tối ưu.

Input:

• Dòng đầu tiên là số nguyên \(T\) - số thứ tự subtask

• Dòng thứ 2 chứa số nguyên \(N\) \((1 \leq N \leq 3 \cdot 10^5)\)

• \(N - 1\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u, v, w\) \((1 \leq u, v \leq N, u \neq v, 1 \leq w \leq N)\) thể hiện 1 cạnh của cây.

• Dòng tiếp theo chứa số nguyên \(Q\) \((1 \leq Q \leq 6 \cdot 10^5)\) thể hiện số truy vấn

• \(Q\) dòng cuối cùng, dòng thứ \(i\) chứa 3 số nguyên \(U, V, hi\) \((1 \leq U, V \leq N, 1 \leq hi \leq N)\)` thể hiện truy vấn thứ \(i\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) thể hiện kết quả của truy vấn thứ \(i\).

Scoring

• Subtask 1 (18 điểm): \(N \leq 40, Q \leq 200\)
• Subtask 2 (20 điểm): \(N \leq 700\)
• Subtask 3 (22 điểm): Cây có dạng đường thẳng
• Subtask 4 (20 điểm): \(N \leq 10^5, Q \leq 2 \cdot 10^5\).
• Subtask 5 (20 điểm): Không có ràng buộc gì thêm.

Example