После реформы образования Поликарп изучает в школе всего два предмета — ОБЖ и физкультуру. За долгие месяцы четвертой четверти он получил n отметок по ним. Когда учителя ставили отметку в дневник, они не записывали за какой предмет оценка, а только ставили саму отметку.
Теперь пришла пора показывать дневник строгим родителям. Поликарп знает, что недавно на родительском собрании родителям сообщили, что он получил a отметок по ОБЖ и b отметок по физкультуре (a + b = n). Теперь Поликарп хочет вписать название предмета перед каждой отметкой так, чтобы:
- было ровно a отметок по ОБЖ,
- было ровно b отметок по физкультуре,
- суммарный средний балл по обоим предметам был максимален.
Средним баллом по предмету называется сумма всех отметок по нему, деленных на их количество. Конечно, деление производится в вещественных числах без каких-либо округлений. Цель Поликарпа максимизировать x1 + x2, где x1 средний балл по первому предмету (ОБЖ), а x2 — по второму (физкультура).
Выходные данные
Выведите последовательность целых чисел f1, f2, ..., fn, где fi (1 ≤ fi ≤ 2) — номер предмета к которому следует отнести i-ую отметку. Если решений несколько, то выведите такое, что последовательность f1, f2, ..., fn — наименьшая лексикографически.
Последовательность p1, p2, ..., pn лексикографически меньше q1, q2, ..., qn, если существует такое j (1 ≤ j ≤ n), что pi = qi для всех 1 ≤ i < j, а pj < qj.
Примечание
В первом примере средний балл по первому предмету равен 4, а по второму — 4.5. Суммарный средний балл равен 8.5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2
4 4 5 4 4
|
1 1 2 1 2
|
|
2
|
4
2 2
3 5 4 5
|
1 1 2 2
|
|
3
|
6
1 5
4 4 4 5 4 4
|
2 2 2 1 2 2
|