Bessie lại chơi với các xâu. Cô phát hiện rằng bằng cách thay đổi thứ tự bảng chữ cái, cô có thể khiến một số xâu đứng trước tất cả các xâu khác theo thứ tự từ điển.

Chẳng hạn, với các xâu "omm", "moo", "mom" và "ommnom", Bessie nhận thấy cô có thể khiến "mom" xuất hiện đầu tiên bằng bảng chữ cái tiêu chuẩn và có thể khiến "omm" xuất hiện đầu tiên bằng bảng chữ cái "abcdefghijklonmpqrstuvwxyz". Tuy nhiên, Bessie không tìm ra cách nào để khiến "moo" hoặc "ommnom" xuất hiện đầu tiên.

Hãy giúp Bessie xác định những xâu nào trong dữ liệu vào có thể đứng đầu theo thứ tự từ điển bằng cách sắp xếp lại thứ tự bảng chữ cái. Để xác định xâu \(X\) có đứng trước xâu \(Y\) theo thứ tự từ điển hay không, hãy tìm vị trí đầu tiên \(j\) mà hai ký tự tương ứng khác nhau. Nếu không có vị trí như vậy thì \(X\) đứng trước \(Y\) theo thứ tự từ điển khi \(X\) ngắn hơn \(Y\). Nếu có, \(X\) đứng trước \(Y\) theo thứ tự từ điển khi \(X[j]\) xuất hiện trước \(Y[j]\) trong bảng chữ cái.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 30\,000\)), là số lượng xâu mà Bessie đang xét.
• \(N\) dòng tiếp theo, mỗi dòng chứa một xâu không rỗng. Tổng số ký tự trong tất cả các xâu không vượt quá \(300\,000\). Mọi ký tự trong dữ liệu vào đều là chữ cái thường từ a đến z. Dữ liệu vào không chứa hai xâu trùng nhau.

Dữ liệu ra

• Dòng đầu tiên chứa số nguyên \(K\), là số lượng xâu có thể đứng đầu theo thứ tự từ điển.
• \(K\) dòng tiếp theo: dòng thứ \(1+i\) chứa xâu thứ \(i\) trong số các xâu có thể đứng đầu theo thứ tự từ điển. Các xâu phải được in theo đúng thứ tự xuất hiện trong dữ liệu vào.

Ví dụ

4
omm
moo
mom
ommnom

2
omm
mom

Nguồn

USACO 2012 December Contest, Gold — Problem 2: First!

Tác giả đề: Mark Gordon, 2012.