미친 과학자 창호는 어젯 밤 구재현을 납치해서, 구재현의 DNA를 추출했다. 인간의 DNA의 길이는 n이며, A, C, G, T 4개의 염색체로 구성되어 있다.

창호는 매일 자신을 놀리던 구재현을 좋아하지 않고, 대신 잘 생긴 콜드플레이의 크리스 마틴을 더 좋아한다. 이러한 경험을 토대로 창호는 이론을 하나 만들었다. 창호의 이론에 따르면, 구재현의 DNA와의 유사도가 최소인 DNA가 크리스 마틴의 DNA이다.

두 DNA의 유사도는, 두 DNA 간의 최장 공통 부분 수열(LCS)의 길이를 뜻한다. 어떠한 DNA의 부분 수열은, 그 DNA에서 0개 이상의 원소를 제거해서 만들 수 있는 또 다른 DNA 수열을 뜻한다. 두 DNA A, B의 최장 공통 부분 수열은, A와 B의 부분 수열이면서, 길이가 최대인 수열들을 뜻한다.

사실 잘 몰랐겠지만, 여러분도 지금 창호에게 납치되어 있다. 크리스 마틴의 DNA를 구하지 못하면 여러분에게 무슨 일이 일어날 지 모른다. 빨리 크리스 마틴의 DNA를 구하자. 가능한 답이 여러 가지일 경우, 아무거나 출력하면 된다.

입력 형식

첫 번째 줄에 인간 DNA의 길이 n이 주어진다. (1 ≤ n ≤ 10, 000) 이 주어진다.

이후 길이 n의 DNA 문자열이 주어진다. 문자열의 모든 문자는 A, C, G, T 넷 중 하나다.

출력 형식

첫 번째 줄에 최소 유사도 c 를 출력한다.

두 번째 줄에 이를 만족하는 길이 n의 문자열을 출력한다. 가능한 답이 여러개 일 경우, 아무거나 출력하면 된다.

예제 입력

4
GACT

예제 출력

1
TCAG