Задача 3. Knapsack problem

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей, сумма элементов которой равна w, либо установите, что искомой подпоследовательности не существует.

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

Во входном файле находятся числа N и w, а за ними следует последовательность из N целых чисел ai.

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

Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами. Единица на позиции i означает, что элемент последовательности ai принадлежит найденной подпоследовательности, 0 означает обратное. В противном случае выведите  − 1.

Ограничения

1 ≤ N ≤ 40, 0 ≤ ai,w ≤ 10000000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 7
1 5 6
1 0 1

0.062s 0.010s 13