Ріст у теплиці#7778
Ви переходите із галузі інформатики в сільське господарство, і ваша нова робота полягає у вирощуванні соняшників у підземній теплиці. Теплиця містить рослин соняшника, розташованих в одну пряму лінію та пронумерованих цілими числами від до зліва направо. Дві лампи забезпечують соняшники необхідними для росту світлом і теплом: лампа розташована з лівого кінця лінії, а лампа — з правого.
Кожного дня вмикається рівно одна з ламп, через що всі соняшники повертаються в бік світла, і деякі з них починають рости. Соняшник росте тоді і тільки тоді, коли соняшник, що знаходиться безпосередньо перед ним (у напрямку джерела світла), вищий за нього. Ріст відбувається безперервно з постійною швидкістю, що дорівнює рівно сантиметру на день.
Зверніть увагу, що коли соняшник починає рости, він може миттєво змусити рости соняшник, що знаходиться безпосередньо позаду нього.
Вам дано початкові висоти соняшників та розклад увімкнення ламп на наступні днів. Визначте підсумкові висоти всіх соняшників.
У першому рядку містяться два цілих числа і m~(1 \le n, m \le 300,000) — кількість соняшників і кількість днів у розглянутому періоді.
У наступному рядку містяться цілих чисел h_1, h_2, \ldots, h_n~(1 \le h_k \le 10^9) — початкові висоти соняшників, задані зліва направо.
У наступному рядку міститься рядок, що складається рівно з символів, кожен з яких є або , або . -й символ визначає, яка лампа увімкнена в -й день періоду.
Виведіть один рядок, що містить цілих чисел — підсумкові висоти соняшників, розташованих зліва направо.
Приклад 1