유전 공학

바이토시아의 고생물학자들이 최근 호박 몇 덩이를 발굴했다. 그 안에는 고대의 모기가 갇혀 있었다. 표본을 분석해 보니 모기는 쥐라기의 것이었고, 그렇다면 당시 바이토시아 땅을 지배한 거대 파충류의 피를 빨았을 가능성이 높다. 유전학자들은 여기서 착안해 모기의 피에서 바이토랩터의 유전 물질을 되살려 보기로 했다.

바이토시아의 모든 생물과 마찬가지로 바이토랩터의 유전체는 바이트아미노산이 이어진 사슬이다. 편의상 바이트아미노산의 종류는 자연수로 나타낸다. 유전체에는 중복이 있다. 같은 종류의 바이트아미노산이 $k$개씩 반복되므로 올바른 유전체의 길이는 항상 $k$의 배수다. 다시 말해 유전체를 앞에서부터 연속한 $k$개씩 블록으로 나누면 각 블록은 한 종류의 바이트아미노산으로만 채워진다.

유전학자들은 모기의 피에서 길이 $n$인 바이트아미노산 사슬을 분리했다. 그런데 이 사슬은 올바른 유전체가 아닐 수도 있다. 외부의 바이트아미노산이 섞여 들어갔다고 의심하기 때문이다. 이제 사슬에서 바이트아미노산을 가장 적게 지워 정상적인 유전체를 만들려고 한다. 지우고 남은 바이트아미노산은 원래 순서를 유지한다. 길이가 같은 답이 여럿이면 사전순으로 가장 앞서는 유전체를 찾는다.

길이가 같은 두 사슬 $l_1$과 $l_2$의 사전순은 이렇게 비교한다. 두 사슬이 처음으로 달라지는 위치를 찾고, 그 위치의 바이트아미노산 번호가 더 작은 쪽이 사전순으로 앞선다.

첫째 줄에 분리한 사슬의 길이 $n$과 올바른 유전체의 중복도 $k$가 주어진다 ($1 \le n \le 1{,}000{,}000$, $2 \le k \le 1{,}000{,}000$).

둘째 줄에 사슬을 이루는 바이트아미노산의 종류 $g_1, \ldots, g_n$이 순서대로 주어진다 ($1 \le g_i \le 1{,}000{,}000$).

첫째 줄에 사슬에서 바이트아미노산을 지워 만들 수 있는 올바른 유전체의 최대 길이 $m$을 출력한다 ($0 \le m \le n$).

둘째 줄에 그 유전체를 이루는 바이트아미노산의 종류를 순서대로 공백 하나로 구분해 출력한다. 길이가 $m$인 답이 여럿이면 사전순으로 가장 앞서는 것을 출력한다. $m = 0$이면, 즉 비어 있지 않은 올바른 유전체를 하나도 만들 수 없으면 둘째 줄은 빈 줄로 둔다.