問題文

黒板に $N$ 個の非負整数 $A_1, \cdots, A_N$ が一列にこの順に書かれています。

あなたは $2$ 個の隣接する数 $A_i, A_{i+1}$ の間に記号 + または * を書き加えて数式を作ります。 + 、 * はそれぞれ加法、乗法を表す二項演算子とします。 ただし、記号を書き加える際には次の制約を満たす必要があります。

• * を $K$ 個以上連続で書いてはならない。 具体的には、$A_i, A_{i+1}$ の間に書き加えた記号を $S_i$ として、記号列 $S_1, \cdots, S_{N-1}$ の連続する長さ $K$ の部分列であって + を含まないものが存在してはならない。

作った数式の計算結果が最大になるような記号列 $S_1, \cdots, S_{N-1}$ を出力してください。そのような記号列が複数ある場合はいずれか一つを出力してください。

制約

• 入力はいずれも整数
• $3 \leq N \leq 2 \times 10^5$
• $2 \leq K < \min(N, 10)$
• $0 \leq A_i \leq 100$

入力

入力は以下の形式で標準入力から与えられます。

出力

作った数式の計算結果が最大になるような記号列 $S_1, \cdots, S_{N-1}$ を出力してください。

入出力例

5 3
3 1 4 1 5

+ + * *

$3+1+4\times1\times5 = 24$ であり、作ることのできる数式の計算結果に $24$ を超えるものはありません。

10 4
31 41 59 26 53 58 97 93 23 84

* * * + * * * + *