백인일수

百人一首는 일본의 전통 게임이다. 이 게임에서는 $N$장의 카드가 쓰이며, 각 카드에는 문자열이 하나씩 적혀 있다. 세부 규칙은 생략한다. A군은 $N$장의 카드에 적힌 문자열을 어떤 순서로든 각각 정확히 한 번씩 읽게 되었다.

百人一首에서는 접두사가 매우 중요하다. 百人一首에 쓰이는 문자열은 접두사가 비슷한 것이 많아서, 비슷한 문자열을 연달아 읽으면 A군도 헷갈린다. 그래서 A군은 연속한 두 카드의 문자열 접두사가 가능한 한 다르도록 카드를 재배열하려고 한다.

A군의 목표는 '야마후다(山札)의 읽기 쉬움'이라고 불리는 지표를 최소화하는 야마후다를 구하는 것이다. 여기서 야마후다란 이 百人一首에서 읽는 $N$장의 카드를 재배열한 것을 말한다. 야마후다의 읽기 쉬움은 야마후다에서 인접한 카드들의 유사도를 모두 더한 값이다. 두 카드의 유사도는 두 카드에 적힌 문자열의 최장 공통 접두사 길이로 정의한다. 문자열 $t$와 $u$의 최장 공통 접두사는 $t$와 $u$ 모두의 접두사인 문자열 가운데 가장 긴 것을 뜻한다.

예를 들어 두 카드에 적힌 문자열이 각각 jag와 japan이라면 두 카드의 유사도는 2이다. 반면 wan과 nyan이라면 유사도는 0이다.

읽기 쉬움이 최소가 되는 야마후다가 여러 개일 수 있다. A군은 최소 해가 될 수 있는 야마후다 중 사전순으로 가장 작은 것을 구하고 싶다. 야마후다 $P$와 $Q$에 대해, $P$가 사전순으로 작다는 것은 어떤 양의 정수 $i$가 존재해서 1번째부터 $i-1$번째 카드까지는 서로 같고, $i$번째 카드의 문자열은 $P$ 쪽이 사전순으로 작다는 뜻이다.

당신의 일은 읽기 쉬움을 최소로 하는 야마후다 중 사전순 최소인 것을 구하는 것이다.

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

N
s1
...
sN

첫 줄에는 카드 수를 나타내는 정수 $N$ ($1 \leq N \leq 100,000$)이 주어진다. 이어지는 $N$줄에는 길이 1 이상의 문자열이 한 줄에 하나씩 적혀 있으며, 각 줄은 영어 소문자만으로 이루어진다. 같은 데이터셋 안에서 각 $s_i$는 서로 다르다고 보장된다. 또한 $s_i$ 길이의 총합은 400,000 이하임이 보장된다.

입력의 끝은 0만 있는 줄로 나타낸다.

각 데이터셋에 대해, 읽기 쉬움이 최소가 되는 야마후다 중 사전순 최소인 야마후다를 $N$줄에 출력하라. 구체적으로는 그 야마후다의 $i$번째 카드에 적힌 문자열을 $i$번째 줄에 출력한다.

사전순의 정의에 주의하라. 이번 정의에서는 문자열을 이어 붙였을 때 사전순 최소가 된다는 뜻이 아니다. 예를 들어 세 번째 입력 예의 [aaa, a, aa]도 읽기 쉬움이 최소인 해 중 하나이고, 이어 붙이면 같은 문자열이 되므로 사전순 최소 해처럼 보일 수 있다. 그러나 이번 정의에서는 맨 앞의 문자열인 "aa"와 "aaa"를 먼저 비교하므로, 사전순 최소 해는 [aa, a, aaa]가 된다.