Flugvallakóðar

flickr.com에서 가져온 이미지

공항은 두 종류의 코드인 IATA와 ICAO로 알려져 있다. 예를 들어 Keflavík의 공항은 IATA 코드가 KEF이고, ICAO 코드가 BIKF이다.

하지만 Absurdistan에서는 국제 표준을 사용하지 않으며, Absurdistan에서 사용하려는 모든 것은 국내에서 만들어지고 Absurdistan에서 독자적으로 개발된 것이어야 한다.

따라서 Absurdistan의 수도 Sillysocks에 최초의 공항이 건설되었을 때, Absurdistan 의회가 공항 코드 체계를 결정했다. 이 체계는 다음 규칙으로 구성된다.

• 코드는 항상 3개의 문자로 이루어진다.

• 다른 공항이 이미 그 코드를 사용하고 있지 않다면 도시 이름의 처음 3개 문자를 사용한다.

• 그 코드가 이미 사용 중이라면 도시 이름에서 가장 먼저 나타나는 사용 가능한 코드를 선택한다. 문자들은 이름에서 서로 인접할 필요는 없지만, 이름과 코드에서 같은 순서로 나타나야 한다.

• 선택지가 여러 개라면 첫 번째 문자가 도시 이름에서 가장 이른 위치에 나타나는 코드를 선택한다.

• 그러한 선택지 두 개의 첫 번째 문자가 같은 위치에 있다면 두 번째 문자가 더 이른 위치에 나타나는 것을 선택한다.

• 마지막으로 그러한 선택지 두 개의 처음 두 문자가 같은 위치에 있다면 세 번째 문자가 더 이른 위치에 나타나는 것을 선택한다.

이 표준은 AANS, 또는 Absurdistan Airport National Standard라고 한다. 공항 데이터베이스가 주어지며, 각 공항의 AANS 코드를 결정해야 한다.

AANS 코드는 항상 대문자여야 하므로 대문자와 소문자를 구분하지 않는다. 출력에서도 반드시 이를 지켜야 한다.

예를 들어 Absurdistan의 Sillysocks 공항은 AANS 코드로 SIL를 갖는다. 하지만 이후 Silverstone이라는 마을에 또 다른 공항을 건설한다면, 이 공항은 AANS 코드로 SIV를 갖는다. SIL는 이미 사용 중이고 Silverstone에서 V가 L보다 뒤에 나오기 때문이다.

채점

그룹 | 점수 | 제한

1 | 10 | 각 공항 이름은 최대 $200$개의 문자이며, $n = 1$.

2 | 20 | 각 공항 이름은 최대 $200$개의 문자이며, $1 \leq n \leq 100$, 코드가 존재한다면 이름의 처음 3개 문자를 사용한다.

3 | 20 | 각 공항 이름은 최대 $200$개의 문자이며, $1 \leq n \leq 100$, 코드가 존재한다면 이름의 처음 2개 문자를 사용한다.

4 | 20 | 각 공항 이름은 최대 $200$개의 문자이며, $1 \leq n \leq 100$, 코드가 존재한다면 이름의 첫 문자를 사용한다.

5 | 20 | 각 공항 이름은 최대 $200$개의 문자이며, $1 \leq n \leq 100$.

6 | 5 | 각 공항 이름은 최대 $200$개의 문자이며, $1 \leq n \leq 10 \, 000$.

7 | 5 | 추가 제한이 없다.

입력의 첫 줄에는 Absurdistan의 공항 수를 나타내는 하나의 양의 정수 $n$이 주어진다. 다음 $n$개의 줄에는 각각 공항이 있는 도시의 이름이 주어진다. 이름은 영문 대문자와 소문자로만 이루어진다. 각 이름은 적어도 $3$개의 문자로 이루어지며, 입력에 포함된 문자의 총개수는 최대 $2 \, 000 \, 000$개이다.

입력은 공항이 건설된 순서대로 주어진다는 점에 유의한다. 따라서 코드를 선택할 때 입력에서 앞서 나오는 공항이 뒤에 나오는 공항보다 우선한다.

각 공항의 AANS 코드를 출력한다. 가능한 유효한 AANS 코드가 없다면 해당 공항은 건설되지 않았다는 뜻이므로, 대신 ":("을 출력한다.