LZW(Lempel-Ziv-Welch)는 매우 효율적인 무손실 데이터 압축 알고리즘 중 하나이다.

LZW 알고리즘은 입력을 순차적으로 읽어가며 단어 사전을 동적으로 구축하고, 이 사전을 활용하여 데이터를 압축한다.

주어진 문자열에 대해 LZW 알고리즘이 동작할 때 최종적으로 생성되는 단어 사전을 구하는 프로그램을 작성하시오.

알고리즘의 사전 생성 절차는 다음과 같다.

1. 1단계 (기본 사전 생성): 문자열을 왼쪽부터 오른쪽으로 스캔하며, 처음 등장하는 길이 \(1\)인 모든 문자를 순서대로 사전에 등록한다. 이때 번호는 \(1\)부터 순차적으로 부여한다.
2. 2단계 (동적 사전 확장): 문자열의 현재 위치 \(i\)에서 시작하는 부문자열 중 사전에 등록되어 있는 가장 긴 문자열 \(w\)를 찾는다.
   • 만약 \(w\) 바로 뒤에 이어지는 문자 \(c\)가 존재하고, \(w + c\)가 사전에 없다면 \(w + c\)를 사전에 새롭게 등록한다.
   • 그 후, 탐색 위치를 \(w\)의 길이만큼 오른쪽으로 이동시킨다.
   • 뒤에 이어지는 문자가 없어 문자열의 끝에 도달하면 탐색을 종료한다.

입력

첫째 줄에 문자열의 길이 \(n\)이 주어진다. (\(3 \le n \le 10,000\))

둘째 줄에 알파벳 대소문자(\(a \sim z\), \(A \sim Z\))로만 이루어진 길이 \(n\)의 문자열이 주어진다.

출력

생성된 사전에 등록된 단어들을 등록된 순서대로 한 줄에 하나씩 번호:단어 형식으로 출력한다.

예제 입력 1

14
ABABBABCABABBA

예제 출력 1

1:A
2:B
3:C
4:AB
5:BA
6:ABB
7:BAB
8:BC
9:CA
10:ABA
11:ABBA