Вам дан массив из $n$ целых положительных чисел и целое число $k$. Гарантируется, что данный массив можно разбить на две подпоследовательности так, что сумма элементов в обоих будет равна $\frac{S}{2}$, где $S$ --- сумма всего массива.

Требуется найти такое разбиение этого массива на две подпоследовательности, что, если мы назовём большую из сумм $A$, то $A \le \frac{S}{2} \cdot \frac{k+1}{k}$.

Подпоследовательность — это последовательность, которая получается из данной путем удаления нуля или более ее элементов.

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

В первой строке вам даны два целых числа --- $n$ и $k$ ($1 \le n \le 1\ 000$, $1 \le k \le 200$). Во второй строке даны $n$ целых положительных чисел $a_i$ ($a_i \le 10^9$).

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

В ответ выведите $n$ чисел $1$ или $2$, где $i$-е число обозначает номер подмассива, к которому вы отнесли $i$-й элемент. Если решений несколько, выведите любое.

Подзадачи