У RedDreamer есть массив \(a\), состоящий из \(n\) неотрицательных целых чисел. Также у RedDreamer есть свое несчастливое число — \(T\).
Обозначим неудачливость массива \(b\) длины \(m\) как \(f(b)\) — количество пар целых чисел \((i, j)\), в которых \(1 \le i < j \le m\) и \(b_i + b_j = T\). RedDreamer должен покрасить каждый элемент массива \(a\) в один из двух цветов — белый или черный (цвет каждого элемента выбирается независимо от остальных элементов), а после этого создать два массива \(c\) и \(d\) таким образом, что все белые элементы принадлежат \(c\), а все черные — \(d\) (возможно, что один из этих массивов окажется пустым). RedDreamer хочет покрасить массив так, чтобы значение \(f(c) + f(d)\) было минимально возможным.
Например:
- если \(n = 6\), \(T = 7\) и \(a = [1, 2, 3, 4, 5, 6]\), можно покрасить \(1\)-й, \(4\)-й и \(5\)-й элемент в белый цвет, а все остальные — в черный. Тогда \(c = [1, 4, 5]\), \(d = [2, 3, 6]\), и \(f(c) + f(d) = 0 + 0 = 0\);
- если \(n = 3\), \(T = 6\) и \(a = [3, 3, 3]\), можно покрасить \(1\)-й элемент в белый цвет, а все остальные — в черный. Тогда \(c = [3]\), \(d = [3, 3]\), и \(f(c) + f(d) = 0 + 1 = 1\).
Помогите RedDreamer раскрасить массив оптимальным образом!
Выходные данные
Для каждого набора тестовых данных выведите \(n\) целых чисел: \(p_1\), \(p_2\), ..., \(p_n\) (\(p_i\) равняется либо \(0\), либо \(1\)), описывающих раскраску. Если \(p_i\) равняется \(0\), то элемент \(a_i\) — белый и принадлежит массиву \(c\), в противном случае он — черный и принадлежит массиву \(d\).
Если существует несколько ответов, при которых достигается минимальное значение \(f(c) + f(d)\), выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6 7
1 2 3 4 5 6
3 6
3 3 3
|
1 0 0 1 1 0
1 0 0
|