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