Vladik và đoạn chat

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Vladik tải về một số đoạn chat từ mạng xã hội để dùng làm dữ liệu huấn luyện. Tuy nhiên, một phần script chạy lỗi nên một vài tin nhắn bị mất thông tin về người gửi. Bạn cần khôi phục lại người gửi cho từng tin nhắn sao cho:

Không có hai tin nhắn liên tiếp được gửi bởi cùng một người (nếu một người gửi nhiều tin liền nhau, chúng đã được gộp thành một tin duy nhất).
Người gửi của một tin nhắn không bao giờ nhắc tên chính mình trong nội dung tin nhắn đó.

Một tin nhắn được gọi là nhắc tên người dùng $u$ nếu chuỗi $u$ xuất hiện trong nội dung như một từ riêng biệt — tức là hai ký tự liền kề (nếu có) trước và sau lần xuất hiện đó đều không phải chữ cái Latinh hoặc chữ số. Ví dụ chuỗi "Vasya, masha13 and Kate!" nhắc tới các từ "Vasya", "masha13", "and", "Kate", nhưng không nhắc "masha".

Hai tên người dùng được coi là khác nhau ngay cả khi chỉ khác nhau ở chữ hoa/thường.

Đảm bảo rằng dữ liệu vào không có người gửi đã biết nào tự nhắc tên mình và không có hai tin nhắn liền kề có cùng người gửi đã biết.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 10$ ) — số đoạn chat. Tiếp theo là $t$ đoạn chat, mỗi đoạn có dạng:

Dòng đầu chứa $n$ ( $1 \leq n \leq 100$ ) — số người dùng trong đoạn chat.
Dòng tiếp theo chứa $n$ tên người dùng phân tách bằng dấu cách. Tên người dùng gồm chữ cái Latinh hoa/thường và chữ số, không bắt đầu bằng chữ số, và độ dài không vượt quá $10$ .
Dòng tiếp theo chứa $m$ ( $1 \leq m \leq 100$ ) — số tin nhắn.
m dòng tiếp theo mô tả các tin nhắn theo thứ tự, mỗi dòng có một trong hai dạng:
- <username>:<text> — tin nhắn có người gửi đã biết. Tên <username> xuất hiện trong danh sách người dùng của đoạn chat.
- <?>:<text> — tin nhắn không rõ người gửi.

Nội dung <text> chỉ chứa chữ cái Latinh hoa/thường, chữ số, các ký tự ., ,, !, ? và dấu cách; không có khoảng trắng cuối dòng; độ dài dương và không vượt quá $100$ .

Dữ liệu ra

Với mỗi đoạn chat, in ra:

Một dòng Impossible nếu không tồn tại cách khôi phục người gửi thoả mãn điều kiện;
Hoặc $m$ dòng, mỗi dòng có dạng <username>:<text> mô tả người gửi và nội dung tin nhắn theo thứ tự. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq t \leq 10$
$1 \leq n \leq 100$
$1 \leq m \leq 100$
Tên người dùng và nội dung tin nhắn theo các điều kiện ở trên.

Ví dụ

Input	Output	Giải thích
1 2 Vladik netman 2 ?: Hello, Vladik! ?: Hi	netman: Hello, Vladik! Vladik: Hi	Tin thứ nhất nhắc tên `Vladik` nên người gửi phải là `netman`. Tin thứ hai do đó phải là `Vladik` để không trùng người gửi với tin trước.
1 2 netman vladik 3 netman:how are you? ?:wrong message vladik:im fine	Impossible	Tin thứ hai phải khác `netman` (tin trước) và khác `vladik` (tin sau), nhưng đoạn chat chỉ có hai người dùng nên không có lựa chọn nào.
2 3 netman vladik Fedosik 2 ?: users are netman, vladik, Fedosik vladik: something wrong with this chat 4 netman tigerrrrr banany2001 klinchuh 4 ?: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready? klinchuh: yes, coach! ?: yes, netman banany2001: yes of course.	Impossible netman: tigerrrrr, banany2001, klinchuh, my favourite team ever, are you ready? klinchuh: yes, coach! tigerrrrr: yes, netman banany2001: yes of course.	Đoạn chat đầu: tin "?" nhắc cả ba người dùng nên không ai có thể là người gửi. Đoạn chat thứ hai: tin "?" thứ nhất chỉ có thể là `netman`, tin "?" thứ ba phải khác `klinchuh` và `banany2001` đồng thời không nhắc tên mình, nên là `tigerrrrr`.

Bình luận

Không có bình luận tại thời điểm này.