Hash-shashin
Đề bài
Mô tả
Hashshashin, thường được biết đến với tên gọi Hội Sát thủ, là một giáo phái nổi tiếng với những, ờ, hoạt động bí mật nhắm vào đối thủ. Để thực hiện các hoạt động bí mật mà không bị thế giới bên ngoài phát hiện, các thành viên của hội, gọi là Sát thủ, thường liên lạc với nhau bằng những thông điệp được mã hóa nghiêm ngặt. Người gửi trước tiên chuyển thông điệp thành một xâu độ dài chỉ gồm các ký tự 0 và 1. Sau đó, người gửi tính một dãy, gọi là , định nghĩa như sau:
- ;
- với mọi .
Ở đây là ký tự thứ (đánh số từ ) của thông điệp nhị phân và là một số nguyên dương được người gửi và người nhận thống nhất từ trước. Người gửi sau đó gửi dãy cho người nhận.
Dễ thấy thông điệp có thể được khôi phục nếu biết , với điều kiện . Ngoài ra, để đảm bảo thông điệp không bị can thiệp, người gửi còn gửi riêng một xâu độ dài chứa kết quả so sánh giữa từng cặp phần tử liên tiếp của :
- là < nếu ;
- là = nếu ;
- là > nếu .
Nhiệm vụ của bạn là giúp Altaïr, một Sát thủ kỳ cựu, trong chiến dịch bí mật sắp tới. Altaïr chờ một thông điệp từ người thầy Mualim vạch ra các mục tiêu tiếp theo. Tuy nhiên, anh chỉ nhận được ; thông điệp chứa dãy đã bị gián điệp đối phương chặn mất. Vì gửi lại thông điệp lúc này rõ ràng không an toàn, Altaïr muốn khôi phục được càng nhiều ký tự của thông điệp gốc càng tốt. Cụ thể, với mỗi vị trí (), Altaïr muốn biết có giống nhau với mọi thông điệp phù hợp với nhận được hay không. Cũng có thể chính đã bị sửa đổi và không tồn tại xâu nào phù hợp, khi đó Altaïr cũng muốn được biết điều này. Hãy giúp anh!
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ test. Mỗi bộ test gồm:
- Dòng đầu tiên chứa hai số nguyên , (, ): độ dài thông điệp gốc và số modulo đã thống nhất.
- Dòng thứ hai chứa xâu độ dài , mỗi ký tự là <, = hoặc > như mô tả ở trên.
Dữ liệu đảm bảo tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, gọi là tập tất cả các xâu nhị phân phù hợp với . Nếu rỗng, in ra impossible. Ngược lại, in ra một xâu độ dài , trong đó:
- là 0 nếu với mọi ;
- là 1 nếu với mọi ;
- là ? trong các trường hợp còn lại.
Ràng buộc
- ,
- Tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 6 <<<>> 10 998244353 ==<<<<<<<< 5 3 <>=<= |
10??? 001??????? impossible |
Bộ test thứ nhất: với , dãy là và là <<<>>; các xâu phù hợp còn lại là , và . Bộ test thứ hai: mọi xâu độ dài bắt đầu bằng đều phù hợp. Bộ test thứ ba: có thể chứng minh không có xâu nào phù hợp. |
| 2 3 3 <<= 4 5 <>>> |
101 impossible |
Bộ test thứ nhất: chỉ có với . |
Bình luận