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

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

주어진 문자열에 대해 LZW 알고리즘을 적용할 때 최종적으로 생성되는 압축 코드를 구하는 프로그램을 작성하시오.

압축 절차는 다음과 같다.

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

입력

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

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

출력

첫째 줄에 생성된 압축 코드의 개수 \(M\)을 출력한다.

둘째 줄에 \(M\)개의 압축 코드를 공백으로 구분하여 출력한다.

예제 입력 1

14
ABABBABCABABBA

예제 출력 1

9
1 2 4 5 2 3 4 6 1