Барбара опоздала на урок математики, поэтому учитель сразу же заставил ее решить пример на листке. Барбара посмотрела на листок и увидела на нем лишь \(n\) чисел \(a_1, a_2, \ldots, a_n\), без каких-либо арифметических знаков. Учитель объяснил Барбаре, что ей требуется лишь расставить разрешенные знаки между числами так, чтобы получившееся выражение имело максимально возможное значение. Для того чтобы узнать разрешенные знаки, учитель дал Барбаре строку \(s\), которая содержит данную информацию.
Легко заметить, что Барбаре требуется поставить \(n - 1\) знак между соседними числами. Выражение должно начинаться с числа и все знаки должны быть разрешены (содержаться в строке \(s\)). Обратите внимание, что умножение имеет приоритет выше, чем сложение или вычитание, а сложение и вычитание имеют одинаковый приоритет и выполняются слева направо. Помогите Барбаре и составьте требуемое выражение!
Выходные данные
Выведите \(n\) чисел, разделённых \(n - 1\) знаком — выражение, имеющее максимальный результат. Если вариантов ответа несколько — выведите любой из них.
Примечание
В первом тестовом примере также подходят ответы: «2+2+0», «2+2-0», «2*2+0».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2 0
+-*
|
2*2-0
|
|
2
|
4
2 1 1 2
+*
|
2+1+1+2
|