Податки

Обмеження: 2 сек., 256 МіБ

Скоро жовтень — ФОПам треба буде подавати податкову декларацію за третій квартал. Ти ж, студенте, не приховуєш свого доходу від держави та сплачуєш податки ?

Є дві системи оподаткування: загальна та спрощена. Загальна система характеризується параметрами $k_1$, $b_1$, а спрощена — $k_2$, $b_2$. На загальній системі за отримання доходу $x$ треба сплатити податок у розмірі $k_1 x + b_1$, а на спрощеній — $k_2 x + b_2$.

ФОП Зеник перебуває на одній із систем оподаткування. Він щомісяця вибирає залишитися на тій системі, на якій є, або перейти на іншу з урахуванням обмежень.

• У перший місяць роботи можна вибрати будь-яку систему оподаткування.

• Із спрощеної на загальну систему можна перейти на початку будь-якого місяця.

• Якщо підприємець на загальній системі не перебував на спрощеній раніше, він може на початку будь-якого місяця перейти на спрощену систему.

• Після переходу із спрощеної на загальну систему назад на спрощену можна повернутися, тільки перебувши $m$ місяців на загальній.

Зеник знає, який у нього буде дохід протягом наступних $n$ місяців — $a_i$ в $i$-ий місяць.

Допоможи йому знайти стратегію, що мінімізує суму сплачених податків.

Вхідні дані

У першому рядку задано два цілі числа $n$ і $m$ — кількість місяців, для яких треба знайти стратегію, і кількість місяців, протягом яких треба перебути на загальній системі оподаткування перед поверненням назад на спрощену.

У другому рядку записано чотири цілі числа $k_1$, $b_1$, $k_2$, $b_2$ — параметри, що задають загальну й спрощену системи.

У третьому рядку задано $n$ цілих чисел $a_i$ — дохід Зеника в наступні $n$ місяців.

Вихідні дані

У першому рядку виведи ціле число — мінімальну суму сплачених податків за $n$ місяців.

У другому рядку виведи $n$ чисел 1 і 2 без пропусків. $i$-е число повинне дорівнювати 1, якщо у твоїй стратегії в $i$-ий місяць Зеник буде перебувати на загальній системі оподаткування, і 2 — якщо на спрощеній.

Обмеження

$1 \le m < n \le 10^5$,

$0 \le k_1, k_2 \le 10^6$,

$0 \le b_1, b_2 \le 10^{12}$,

$0 \le a_i \le 10^6$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 2 4 74 7 47 6 12 14 13 1 10 15 5 10 2 16	1167 21112112221

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 2 7 47 4 74 6 12 14 13 1 10 15 5 10 2 16	1170 12221121112

Примітки

У першому прикладі Зеник буде на загальній системі в другому, третьому, четвертому, шостому, сьомому та одинадцятому місяцях, а на спрощеній — у першому, п’ятому, восьмому, дев’ятому та десятому.