DNA

DNA는 A, C, G, T 네 종류의 뉴클레오타이드 문자로 표현할 수 있다. 길이가 같은 두 DNA 문자열의 Hamming Distance는 같은 위치에 있는 문자가 서로 다른 위치의 개수이다.

길이가 M인 DNA 문자열 N개 s_1, s_2, ..., s_N이 주어진다. 길이가 M인 DNA 문자열 S를 하나 골라, S와 모든 입력 문자열 사이의 Hamming Distance 합을 최소로 만들려고 한다. 즉, d(S, s_1) + d(S, s_2) + ... + d(S, s_N)이 최소가 되는 S를 구해야 한다. 가능한 문자열이 여러 개라면 사전순으로 가장 앞서는 문자열을 선택한다.

첫째 줄에 DNA 문자열의 개수 N과 각 문자열의 길이 M이 주어진다. 둘째 줄부터 N개의 줄에는 길이가 M인 DNA 문자열이 하나씩 주어진다.

N은 1 이상 1,000 이하이고, M은 1 이상 50 이하이다. 각 DNA 문자열은 문자 A, C, G, T로만 이루어져 있다.

첫째 줄에 Hamming Distance 합이 최소가 되는 DNA 문자열을 출력한다. 그러한 문자열이 여러 개라면 사전순으로 가장 앞서는 문자열을 출력한다.

둘째 줄에는 그 최소 Hamming Distance 합을 출력한다.