Вот и наступил день открытия самого большого магазина в мире. Для показа всех возможностей своего магазина, в том числе невероятной скорости обслуживания покупателей на кассе, владельцы придумали такой рекламный ход: в магазин запускается n самых средних покупателей мира. Кассы же откроются лишь тогда, когда все покупатели наберут себе вещей и встанут в очереди на оплату. Но если каждый будет ходить и выбирать самую маленькую очередь, то это затянется на несколько часов. Поэтому вас попросили автоматизировать выбор очереди для каждого подходящего покупателя.
Отдел социологов рассказал вам, как средний покупатель выбирает очередь: он смотрит на количество людей в ней и на количество покупок двух последних людей в данной очереди. Формально, средний покупатель выбирает очередь в ту кассу i, для которой минимален показатель xi = ci·p, где ci — количество покупателей в i-ой очереди, а p — среднее количество покупок у одного покупателя очереди. Число p определяется максимум по двум последним покупателям в очереди: p = (p1 + p2) / 2, если в очереди 2 и больше людей, где p1 и p2 — количество покупок последнего и предпоследнего покупателя, p = p1, если покупатель в очереди всего один, и p = 0, если покупателей в очереди нет. Из всех касс с минимальным xi покупатель выбирает кассу с минимальным номером i.
После выбора кассы покупатель встает в очередь к данной кассе и никуда из нее не уходит.
В первой строке содержатся два целых числа через пробел: n и k (1 ≤ n, k ≤ 105) — количество потенциальных покупателей и количество касс в магазине.
В следующей строке содержатся n целых чисел через пробел: pj (1 ≤ pj ≤ 1000) — количество покупок у j-ого в хронологическом порядке покупателя. Гарантируется, что каждый покупатель успевает выбрать очередь и встать в неё до того, как кассу начинает выбирать следующий покупатель.
В единственной строке выведите n чисел через пробел. i-е число должно быть равно номеру кассы, в очередь к которой стоит встать i-му покупателю, руководствуясь критерием, описанным в задаче.
5 2
1 3 1 2 3
1 2 1 1 2
5 7
1 3 1 2 3
1 2 3 4 5
