sẽ xuất bản một bài báo trên ACOJ. nghe thấy một tin đồn: danh sách tên các tác giả trên bài báo luôn được sắp xếp theo thứ tự từ điển.
Sau khi kiểm tra,
phát hiện ra rằng đôi khi điều đó không đúng. Trên một số bài báo, tên của các tác giả không được sắp xếp theo tiêu chuẩn thông thường của thứ tự từ điển. Nhưng sau khi sửa đổi một số thứ tự của các chữ cái trong bảng chữ cái Latin thì thứ tự tên của các tác giả được sắp xếp đúng theo thứ tự từ điển mới.muốn biết liệu có tồn tại thứ tự các chữ cái trong bảng chữ cái Latin sao cho các tên trên bài báo mà định xuất bản được sắp xếp theo thứ tự từ điển hay không. Nếu có, bạn hãy giúp tìm ra một thứ tự thỏa mãn bất kỳ.
Thứ tự từ điển được xác định theo cách sau: Khi so sánh \(2\) xâu kí tự \(s\) và \(t\), đầu tiên ta tìm vị trí ngoài cùng bên trái sao cho các ký tự khác nhau \((s_i≠t_i)\) rồi so sánh các ký tự \(s_i\) và \(t_i\) theo thứ tự của chúng trong bảng chữ cái, nếu \(s_i<t_i\) thì \(s\) có thứ tự từ điển nhỏ hơn \(t\) và ngược lại. Còn nếu không có vị trí như vậy (tức là \(s\) là tiền tố của \(t\) hoặc ngược lại) thì chuỗi ngắn hơn sẽ có thứ tự từ điển nhỏ hơn.
Input
- Dòng đầu tiên chứa số nguyên dương \(n\) là số lượng tên các tác giả.
- \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi kí tự \(name_i\) \((1 \le name_i \le 100)\) gồm các chữ cái Latin in thường là tên của tác giả thứ \(i\). Tất cả tên của các tác giả đều khác nhau.
Output
- Nếu tồn tại thứ tự các chữ cái mà các tên đã cho được sắp xếp theo thứ tự từ điển, hãy in ra bất kỳ thứ tự nào thỏa mãn là hoán vị của các ký tự ′a′-′z′ (tức là, đầu tiên in ra chữ cái đầu tiên của bảng chữ cái đã sửa đổi, sau đó in ra chữ cái thứ hai, v.v.. ).
- Nếu không, in ra một từ duy nhất: Impossible
Constraints
- \(1 \le n \le 100\)
Example
Input 1
3
rivest
shamir
adleman
Output 1
bcdefghijklmnopqrsatuvwxyz
Input 2
10
tourist
petr
wjmzbmr
yeputons
vepifanov
scottwu
oooooooooooooooo
subscriber
rowdark
tankengineer
Output 2
Impossible
Nhận xét