Nguồn: https://www.codechef.com/
Akhil có rất nhiều quả bóng trắng và đen. Một ngày, anh chơi
với chúng. Trong khi chơi, anh ta xếp các quả bảnh thành hai hàng, mỗi hàng
chứa N quả banh. Hai hàng banh này
được cung cấp cho bạn dưới dạng 2 chuỗi X,
Y. Cả 2 chuỗi này chỉ chứa 'W' và 'B' trong đó 'B' ký hiệu cho qua banh màu
trắng và 'B' ký hiệu cho quả banh màu đen.
Ngoài hai hàng banh này, Akhil có số lượng vô hạn các quả
banh của mỗi màu. Anh ta muốn tạo ra một dòng nữa gồm N quả banh, ký hiệu bằng Z,
sao cho tổng khoảng cách hamming giữa X
và Z và khoảng cách hamming giữa Y và Z là tối đa.
Khoảng cách hamming giữa hai chuỗi X và Y được đỉnh nghĩa
là số lượng vị trí mà màu của trái banh trong X khác với hàng Y ở tại
vị trí đó. Ví dụ, khoảng cách hamming giữa “WBB” và “BWB” là 2, vì ở ví trí 1
và 2, màu tương ứng trong hai chuỗi khác nhau.
Vì có thể có nhiều cách tạo hàng Z, Akhil muốn bạn tìm chuỗi có thứ tự từ điển nhỏ nhất mà có giá
trị như nói ở trên là lớn nhất.
Dữ liệu vào
· Dòng đầu tiên của tập tin dữ liệu vào chứa một số nguyen T là số lượng bô test. Mô tả của T bộ test như sau:
· Dòng đầu tiên của mỗi bộ test sẽ chứa một chuỗi X là cách sắp xếp các quả banh trong
hàng đầu tiên.
· Dòng thứ hai chứa một chuỗi Y là cách sắp xếp các quả banh trong hàng thứ hai.
Dữ liệu ra
· Với mỗi bộ test, xuất ra một dòng duy nhất chứa chuỗi có độ
dài là N là cách sắp xếp các quả
banh trong hàng Z.
Ràng buộc
• 1 ≤
T ≤ 3
Giới hạn
· Subtask #1 (10 điểm) : 1
≤ N ≤ 16
· Subtask #2 (20 điểm) : 1
≤ N ≤ 103
· Subtask #3 (70 điểm) : 1
≤ N ≤ 105
Ví dụ
Input:
WBWB
WBBB
Output:
BWBW
Giải thích
Ví dụ 1. Như đã biết, khoảng các Hamming(WBWB, BWBW) và khoảng cách
Hamming(WBBB, BWBW) = 4 + 3 = 7.
Bạn có thể thử những ía trị khác cho chuỗi Z, giá trị sẽ không bao giờ vượt quá 6
