시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2 1 1 50.000%

문제

1부터 N까지의 수들이 중복 없이 임의로 나열된 한 순열을 생각하자. 이러한 순열에서 몇 개의 수들을 제거하면 하나의 수열이 생기는데, 이를 원래 순열의 부분수열이라 한다. 예를 들어 N=4일 때 3 1 2 4 가 순열의 한 예이고, 1 4는 그 순열이 부분수열의 한 예이다. 부분수열은 원래 순열에서의 순서를 유지해야 하므로 4 1은 앞의 순열의 부분수열이 아니다.

부분수열을 이루는 수들이 차례로 증가하는 경우, 이를 부분 증가수열이라 하며, 반대로 차례로 감소하는 경우에는 부분 감소수열이라 한다. 최대 부분 증가수열은 이러한 부분 증가수열들 중 길이가 가장 긴 것을 의미하며, 최대 부분 감소수열은 이러한 부분 감소수열들 중 길이가 가장 긴 것을 의미한다. 앞 예의 3 1 2 4의 최대 부분 증가수열은 1 2 4로 그 길이가 3이며, 최대 부분 감소수열은 3 1 또는 3 2로 그 길이가 2이다.

세 정수 N, M, K가 주어졌을 때, 길이가 N인 순열들 중 최대 부분 증가수열의 길이가 M이고, 최대 부분 감소수열의 길이가 K인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 순열의 길이 N(1 ≤ N ≤ 100,000), 최대 부분 증가수열의 길이 M, 최대 부분 감소수열의 길이 K(1 ≤ M, K ≤ N)가 빈 칸을 사이에 두고 순서대로 주어진다.

출력

첫째 줄에는 문제의 조건을 만족하는 수열 중에서 사전 순으로 가장 앞서는 것을 출력하고, 둘째 줄에는 가장 마지막에 오는 것을 출력한다.

조건을 만족하는 수열이 존재하지 않는 경우 첫째 줄에 -1만을 출력한다.

예제 입력 1

4 4 1

예제 출력 1

1 2 3 4
1 2 3 4

예제 입력 2

4 4 2

예제 출력 2

-1

예제 입력 3

4 3 2

예제 출력 3

1 2 4 3
4 1 2 3

예제 입력 4

4 2 2

예제 출력 4

2 1 4 3
3 4 1 2

예제 입력 5

13 5 4

예제 출력 5

1 2 5 4 3 9 8 7 6 13 12 11 10
13 11 12 6 7 8 9 10 1 2 3 4 5

출처