Xuất bản bài báo

Xem dưới dạng PDF

Gửi bài giải

Điểm: 10
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

Nguoingu45 sẽ xuất bản một bài báo trên ACOJ. Nguoingu45 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, Nguoingu45 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.

Nguoingu45 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à Nguoingu45 đị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 Nguoingu45 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

Không có ý kiến tại thời điểm này.