가장 짧은 접두사

문자열의 접두사는 그 문자열의 맨 앞에서 시작하는 부분 문자열이다. carbon의 접두사는 c, ca, car, carb, carbo, carbon이다. 이 문제에서 빈 문자열은 접두사로 보지 않지만, 비어 있지 않은 모든 문자열은 자기 자신의 접두사로 본다.

일상에서 우리는 단어를 접두사로 줄여 쓰곤 한다. 예를 들어 carbohydrate는 흔히 carb로 줄여 쓴다. 이 문제에서는 단어들의 집합이 주어지며, 각 단어에 대해 그 단어를 유일하게 식별하는 가장 짧은 접두사를 찾아야 한다.

예를 들어 carbohydrate는 carboh로 줄일 수 있지만 carbo(또는 그보다 짧은 접두사)로는 줄일 수 없다. 목록의 다른 단어들도 carbo로 시작하기 때문이다.

정확히 일치하는 경우는 접두사 일치보다 우선한다. 예를 들어 접두사 car는 단어 car와 정확히 일치하므로, car는 목록에서 car로 시작하는 carriage 등 다른 단어가 아니라 car 자신의 약어로 모호함 없이 이해된다.

입력은 최소 두 줄, 최대 $1000$줄로 이루어진다. 각 줄에는 소문자 $1$~$20$자로 이루어진 단어 하나가 들어 있다. 모든 단어는 서로 다르다.

입력과 같은 수의 줄을 출력한다. 각 줄에는 대응하는 입력 줄의 단어를 출력하고, 공백 한 칸을 둔 뒤, 그 단어를 유일하게 식별하는 가장 짧은 접두사를 출력한다.