B. Скучное Разбиение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача самая скучная из всех, которые Вы когда-либо видели.

Дана последовательность целых чисел a1, a2, ..., an и неотрицательное целое число h, наша задача — разбить последовательность на две подпоследовательности (не обязательно состоящие из подряд идущих элементов). Каждый элемент исходной последовательности должен содержаться ровно в одной из полученных подпоследовательностей. Заметьте, что одна из полученных подпоследовательностей может быть пустой.

Определим функцию f(ai, aj), аргументами которой являются два различных элемента (то есть, i ≠ j) исходной последовательности. Если ai и aj находятся в одной и той же подпоследовательности в текущем разбиении, f(ai, aj) = ai + aj в противном случае f(ai, aj) = ai + aj + h.

Рассмотрим все возможные значения функции f для некоторого разбиения. Назовем хорошестью данного разбиения разность между максимальным значением функции f и минимальным значением функции f.

Ваша задача — найти разбиение данной последовательности a, которое имеет минимально возможную хорошесть среди всех возможных разбиений.

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

Первая строка входных данных содержит целые числа n и h (2 ≤ n ≤ 105, 0 ≤ h ≤ 108). Во второй строке записан список n целых чисел через пробел, обозначающих a1, a2, ..., an (0 ≤ ai ≤ 108).

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

Первая строка выходных данных должна содержать искомую минимальную хорошесть.

Вторая строка описывает оптимальное разбиение. Выведите n разделенных пробелами целых чисел: i-ое целое число равняется 1, если ai находится в первой подпоследовательности, в противном случае оно должно равняться 2.

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

Примеры
Входные данные
3 2
1 2 3
Выходные данные
1
1 2 2
Входные данные
5 10
0 1 0 2 1
Выходные данные
3
2 2 2 2 2
Примечание

В первом примере значения f таковы: f(1, 2) = 1 + 2 + 2 = 5, f(1, 3) = 1 + 3 + 2 = 6 и f(2, 3) = 2 + 3 = 5. Таким образом, разность между максимальным и минимальным значением f равняется 1.

Во втором примере значение h велико, следовательно, лучше оставить одну из подпоследовательностей пустой.