Lampice

면접 대비

시간 제한1초메모리 제한512 MB

요약

n개의 색 배열에서 앞뒤를 잘라 남은 구간이 어떤 패턴을 정확히 k번 반복한 형태가 되게 하고, 그 패턴을 출력한다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 구현, 문자열 매칭, 배열
정답자: 아직 제출이 없습니다

문제

베라가 크리스마스를 좋아한다는 설정입니다. 베라는 발코니를 장식하려고 일렬로 연결된 $n$ 개의 전구를 샀고, 각 전구는 1000가지 색 중 하나로 빛납니다.

베라는 반복되는 무늬를 좋아하기 때문에, 어떤 색 무늬가 연속으로 $k$ 번 반복되는 상태로 발코니를 꾸미고 싶어 합니다. 그러나 산 전구가 그 조건을 만족하지 않을 수 있으므로, 수열의 앞에서 0개 이상, 뒤에서 0개 이상의 전구를 잘라내어 어떤 색 무늬가 연속으로 $k$ 번 반복되는 수열을 얻으려고 합니다.

이렇게 잘라서 원하는 전구 수열을 얻을 수 있는지 판별하고, 얻을 수 있다면 반복되는 무늬를 출력하세요.

입력

첫째 줄에 양의 정수 $n$ 과 $k$ 가 주어집니다 ( $1 ≤ k ≤ n ≤ 50$ ).

둘째 줄에 베라가 산 전구의 색을 순서대로 나타내는 $n$ 개의 양의 정수 $a_1, a_2, \dots, a_n$ 이 주어집니다 ( $1 ≤ a_i ≤ 1000$ ).

출력

베라가 원하는 전구 수열을 잘라서 얻을 수 없다면 -1을 출력합니다.

얻을 수 있다면 첫째 줄에 반복되는 무늬의 길이를, 둘째 줄에 그 무늬를 이루는 색의 수열을 출력합니다. 답이 여러 개라면 그중 아무거나 출력해도 됩니다.

힌트

세 번째 예제에 대한 설명: 베라가 뒤에서 전구 6개를 자르고 앞에서 0개를 자르면 전구 수열 1 5 1 5를 얻고, 여기서 무늬 1 5가 연속으로 두 번 반복됩니다. 반대로 앞에서 전구 4개를 자르고 뒤에서 0개를 자르면 전구 수열 2 5 6 2 5 6을 얻고, 여기서 무늬 2 5 6이 두 번 반복되므로 이것도 올바른 답입니다.

예제3

예제 1
입력
```
8 6
10 1 1 1 1 1 1 5
```
예상 출력
```
1
1
```
예제 2
입력
```
3 2
1 2 1
```
예상 출력
```
-1
```
예제 3
입력
```
10 2
1 5 1 5 2 5 6 2 5 6
```
예상 출력
```
2
1 5
```