정리하기

FJ에게는 $N$마리($1 \leq N \leq 10^5$)의 소가 있고, 각 소는 $1 \ldots N$의 서로 다른 번호로 구별된다. 소들은 한 줄로 서 있다. FJ는 소들이 번호 오름차순으로 정렬되어 있기를 바라지만, 안타깝게도 지금은 순서가 뒤죽박죽이다. 예전에는 "버블 정렬" 같은 획기적인 알고리즘으로 소를 정렬했지만, 오늘은 꽤 게으른 기분이다. 대신 특정 소 한 마리씩에게 "정리해"라고 소리친다. 소리치는 소는 (자신의 관점에서) 자신이 순서에서 벗어나 있지 않도록 만든다. 바로 오른쪽에 자신보다 번호가 작은 소가 있는 동안 두 소는 자리를 바꾼다. 그다음, 바로 왼쪽에 자신보다 번호가 큰 소가 있는 동안 두 소는 자리를 바꾼다. 마지막으로 그 소의 "정리"가 끝나고, 이 시점에 왼쪽 소의 번호는 더 작고 오른쪽 소의 번호는 더 크다.

FJ는 소의 부분집합을 하나 고른 뒤, 그 부분집합을 순회하면서 각 소에게 번호 오름차순으로 소리친다. 이를 $N$마리의 소가 모두 정렬될 때까지 반복한다. 예를 들어 번호 $\{2, 4, 5\}$인 소의 부분집합을 골랐다면, 소 2에게 소리치고, 그다음 소 4, 그다음 소 5에게 소리친다. $N$마리의 소가 여전히 정렬되지 않았다면, 필요할 때마다 이 같은 소들에게 계속 소리친다.

FJ는 어떤 소가 귀를 기울이는지 확실하지 않으므로, 이 부분집합의 크기를 최소로 하고 싶다. 게다가 FJ는 수 $K$를 매우 행운의 수라고 생각한다. 이 소들에게 반복해서 소리치면 결국 모든 소가 정렬되는, 최소 크기의 부분집합 중 $K$번째로 사전순으로 작은 부분집합을 구하도록 도와주자.

$\{1,\dots,N\}$의 부분집합 $S$가 $T$보다 사전순으로 작다는 것은, $S$의 원소를 오름차순으로 나열한 리스트가 $T$의 원소를 오름차순으로 나열한 리스트보다 사전순으로 작다는 뜻이다. 예를 들어 $\{1, 3, 6\}$은 $\{1, 4, 5\}$보다 사전순으로 작다.

첫째 줄에 두 정수 $N$과 $K$가 주어진다($1 \leq K \leq 10^{18}$). 둘째 줄에 소의 번호를 왼쪽에서 오른쪽 순서로 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다.

유효한 부분집합이 적어도 $K$개 있음이 보장된다.

첫째 줄에 최소 부분집합의 크기를 출력한다. 나머지 줄에는 최소 크기의 부분집합 중 $K$번째로 사전순으로 작은 부분집합에 속하는 소의 번호를 오름차순으로 한 줄에 하나씩 출력한다.

배열 $\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}$에서 시작한다. FJ가 번호 1인 소에게 소리치면 배열은 $\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}$이 된다. FJ가 번호 4인 소에게 소리치면 배열은 $\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}$이 된다. 이 시점에서 배열은 정렬되어 있다.