Đám mây hashtag

Một hashtag là xâu bắt đầu bằng ký tự #, theo sau là một dãy chữ cái Latin thường. Độ dài của hashtag được tính bằng số ký tự sau dấu #.

Trang tin có $n$ hashtag được liệt kê theo thứ tự đăng bài. Người quản trị muốn dãy hashtag này không giảm theo thứ tự từ điển, nhưng không được đổi chỗ chúng. Thao tác duy nhất được phép là xoá một hậu tố (một số ký tự liên tiếp ở cuối) của một hashtag bất kỳ. Có thể xoá bao nhiêu ký tự tuỳ ý, kể cả xoá hết phần chữ cái, khi đó hashtag chỉ còn lại đúng ký tự #.

Hãy tìm cách xoá sao cho tổng số ký tự bị xoá là nhỏ nhất, rồi in ra dãy hashtag thu được.

Xâu $a_1{a}_2\dots a_m$ không lớn hơn xâu $b_1{b}_2\dots b_k$ theo thứ tự từ điển nếu tại vị trí đầu tiên $i$ mà $a_i\ne b_i$ ta có $a_i$ đứng trước $b_i$ trong bảng chữ cái, hoặc không tồn tại vị trí như vậy và $m\le k$. Theo định nghĩa này, hashtag chỉ gồm một ký tự # không lớn hơn mọi hashtag khác.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số hashtag.
• $n$ dòng tiếp theo, mỗi dòng chứa một hashtag có độ dài dương.

Dữ liệu ra

In ra $n$ dòng là các hashtag sau khi xoá, theo đúng thứ tự ban đầu.

Ràng buộc

• $1\le n\le 500000$
• Tổng độ dài của tất cả các hashtag (không tính ký tự #) không vượt quá $500000$

Ví dụ