Đất nước JOI sử dụng \(100\) ký tự khác nhau. Vì khó biểu diễn trực tiếp các ký tự này trên máy tính, người ta dùng cách viết thay thế sau:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99

Như vậy, mỗi ký tự được biểu diễn bằng hai chữ số, với \(10\times10\) khả năng. Từ điển của đất nước JOI sắp xếp các từ theo thứ tự ký tự trong bảng này: ký tự ở hàng phía trên đứng trước; trong cùng một hàng, ký tự nằm bên trái đứng trước.

Hiện nay, trò chơi nối từ shiritori đang rất thịnh hành ở đất nước JOI. Người chơi lần lượt nói một từ bắt đầu bằng ký tự cuối cùng của từ mà người trước vừa nói. Không được dùng lại một từ đã được nói.

Yêu cầu

Một ngày nọ, bạn chơi “shiritori 5” cùng bạn bè. Ngoài các quy tắc thông thường của shiritori, trò chơi này yêu cầu mọi từ được sử dụng đều phải có đúng \(5\) ký tự. Bạn đã ghi lại trên máy tính danh sách \(N\) từ được nói, nhưng vô tình sắp xếp lại danh sách. Hãy khôi phục diễn biến của trò chơi “shiritori 5” từ danh sách đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số từ.
• \(N\) dòng tiếp theo, mỗi dòng chứa một từ. Mỗi từ được biểu diễn bằng một chuỗi gồm đúng \(10\) chữ số, tương ứng với \(5\) ký tự của đất nước JOI. Các từ được cho theo thứ tự xuất hiện trong từ điển và đôi một khác nhau.

Dữ liệu ra

Nếu không thể tạo thành một trò chơi “shiritori 5” sử dụng tất cả \(N\) từ đã cho, in ra đầu ra chuẩn một dòng chứa impossible.

Nếu có thể, in \(N\) từ theo thứ tự được nói, mỗi từ trên một dòng và mỗi từ được dùng đúng một lần. Nếu có nhiều thứ tự hợp lệ, chọn thứ tự theo các ưu tiên sau:

• Trước hết, chọn phương án có từ thứ nhất đứng sớm nhất trong từ điển.
• Nếu vẫn còn nhiều phương án, chọn phương án có từ thứ hai đứng sớm nhất trong từ điển.
• Tiếp tục xét lần lượt các vị trí như vậy; nếu đến vị trí cuối cùng vẫn chưa xác định được, chọn phương án có từ thứ \(N\) đứng sớm nhất trong từ điển.

Ràng buộc

• \(1\le N\le500\,000\).
• Mỗi từ gồm đúng \(5\) ký tự, mỗi ký tự được biểu diễn bằng một cặp chữ số từ 00 đến 99.
• Các từ đôi một khác nhau và đã được sắp theo thứ tự từ điển trong dữ liệu vào.
• Giới hạn thời gian CPU: \(5\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

• Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
• Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
• Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
• Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm. Các tỉ lệ dưới đây mô tả những tập dữ liệu có thể giao nhau:

• Các bộ dữ liệu chiếm \(65\%\) tổng số điểm chỉ sử dụng \(20\) loại ký tự từ 00 đến 19.
• Các bộ dữ liệu chiếm \(65\%\) tổng số điểm thỏa mãn \(N\le1000\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm vừa chỉ sử dụng các ký tự từ 00 đến 19, vừa thỏa mãn \(N\le1000\).
• Các bộ dữ liệu chiếm \(90\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: chỉ sử dụng các ký tự từ 00 đến 19, hoặc \(N\le1000\).

Ví dụ

5
0000010201
0102030403
0104050603
0206070801
0308090002

0000010201
0102030403
0308090002
0206070801
0104050603

4
9600000098
9700000099
9800000099
9900000098

impossible

12
0114090401
0214051905
0304141219
0510031717
0703050011
1102190101
1108040907
1110090702
1313071203
1707120711
1902090011
1909121313

1909121313
1313071203
0304141219
1902090011
1108040907
0703050011
1110090702
0214051905
0510031717
1707120711
1102190101
0114090401