Республиканская олимпиада по информатике 2008 год

Задача B. Подпоследовательность

Ограничение по времени:

2 seconds

Ограничение по памяти:

128 MB.

Дана последовательность из $N$ целых чисел. Требуется найти ее $K$-ю в лексикографическом порядке возрастающую подпоследовательность. Подпоследовательность получается из исходной последовательности вычеркиванием нуля или более, но не всех, чисел. В возрастающей последовательности каждое число строго больше предыдущего, если оно существует. Последовательность $A = {a_1, a_2, \dots a_n}$ считается лексикографически меньше последовательности $B = {b_1, b_2, \dots b_m}$, если $A$ — префикс (начальная часть) последовательности B, или существует такое $k$, что $a_i = b_i$ при $i < k$, и $a_k < b_k$.

Формат входного файла

Первая строка входного файла содержит два целых числа $N$ и $K$ ($1 < N <= 60$, $K >= 1$). На следующей строке записаны N целых чисел в пределах от $0$ до $10^9$. Числа в строках разделены пробелом. Гарантируется, что искомая подпоследовательность существует.

Формат выходного файла

Первая строка выходного файла должна содержать число $M$ — количество чисел в найденной подпоследовательности. Вторая строка должна содержать $M$ разделенных пробелом целых чисел — саму найденную подпоследовательность.

Примеры:

Вход

3 2
1 1 2

Ответ

2
1 2