問題文

高校生の田中君は、数学のテストを受けています。
しかし田中君はある問題が解けず、このままでは赤点になってしまいます。
ある問題とは、微分を含む一変数多項式を解く問題です。

田中君の脳はインターネットに接続しており、テスト中でも式をコンピュータに送信し答えを受け取ることができます。
田中君のために、与えられた式を計算して解くプログラムを組んであげてください。

式に現れる演算子は足し算を表す'+',かけ算を表す'*'だけとなっています。
式に現れる値は定数と変数'x'、式$f(x)$の導関数"d{$f(x)$}"です。
($f(x)$の導関数は一般的なライプニッツの記法で$\frac{d}{dx}\{f(x)\}$ですが式を簡単化するため"d{$f(x)$}"としています。)

演算子が限られているため,$x^n=x\ast x\ast x\ast ...\ast x\ast x$と$x$のn乗がn個の$x$同士のかけ算で表されることに注意してください。
演算子の優先順序は、現実の世界と同様の '+' < '*' です。

入力

$N$
$d$
$S$

$N$は式を表す文字列$S$の文字数を表します。
$d$は,（微分前の）式に現れる変数xの最大の次数を表します。
$S$は式を表す長さ$N$の文字列です。$S$に空白は含まれません。

$1\le N=|S|\le 50000$
$0\le d\le 10$

式$S$は演算子'+','*' 、定数,変数'x',導関数"d{$T$}"が含まれます。$T$も式を表す文字列で$1\le |T|$が保証されています。
また、式中に現れる定数は1以上9以下の整数です。

一つの項に二つ以上の定数が現れることはありません。
つまり、"2*2*x"のような定数が2回以上現れる項が含まれる入力は存在しません。
"x*2"のように定数が先頭にあるとは限りません。

導関数に隣接しうる演算子は'+'のみです。
つまり、"x*d{x}"のような入力は存在しません

出力

$A_0{A}_1{A}_2...A_{d-1}{A}_d$

式に含まれる微分を全て計算した結果$A_0\ast x^0+A_1\ast x^1+...+A_d\ast x^d$を求めてください。
$x_0,x_1,x_2,...,x_{d-1},x_d$の係数$A_0,A_1,A_2,...,A_{d-1},A_d$を出力してください。
計算結果の係数の値に気をつけましょう。
最後に改行してください。

サンプル

8
2
d{x*x+x}

1 2 0

19
3
d{2*x+d{3*x*x*x}}+x

2 19 0 0

1
1
x

0 1

59
3
x*x*x+d{x*x*x}+d{d{x*x*x}}+d{d{d{x*x*x}}}+d{d{d{d{x*x*x}}}}

6 6 3 1