E. Замена чисел
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Евгения есть n карточек, на каждой из которых написано ровно одно целое число. Евгений хочет поменяться с Николаем некоторыми карточками так, чтобы количество четных чисел на его карточках стало равно количеству нечетных чисел на его карточках, при этом все числа стали различными.

У Николая есть m карточек, на которых написаны различные числа от 1 до m, то есть у Николая есть ровно одна карточка, на которой написано число 1, ровно одна карточка, на которой написано число 2 и так далее.

Назовем обменом процесс, в котором Евгений отдает одну из своих карт Николаю, и берет у него одну другую карту. Перед вами стоит задача найти минимальное количество обменов карт, а также определить какие на какие карточки нужно обменивать Евгению.

Входные данные

В первой строке следуют два целых числа n и m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 109) — количество карточек у Евгения и количество карточек у Николая. Гарантируется, что n четно.

Во второй строке следует последовательность из n целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — числа на карточках Евгения.

Выходные данные

Если ответа не существует, выведите -1.

В противном случае, в первую строку выведите минимальное количество обменов. Во вторую строку выведите n чисел — карточки Евгения после обмена с Николаем. Порядок карточек должен совпадать с порядком карт из входных данных. Если i-я карточка не обменивалась, то i-е число должно совпадать с числом из входных данных. В противном случае, будет считаться, что эта карточка была поменяна, и i-е число должно равняться числу на карточке, на которую она была поменяна.

Если ответов несколько, разрешается вывести любой из них.

Примеры
Входные данные
6 2
5 6 7 9 4 5
Выходные данные
1
5 6 7 9 4 2
Входные данные
8 6
7 7 7 7 8 8 8 8
Выходные данные
6
7 2 4 6 8 1 3 5
Входные данные
4 1
4 2 1 10
Выходные данные
-1