#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n; int d; string s; #define MAX 50002 int be[MAX]; string pluss(string a, string b, bool flag = false){ if (!flag){ reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); } if (a.size() > b.size()){ swap(a, b); } string ans; ans.clear(); long long int want = 0; for (int i = 0; i < a.size(); i++){ long long int val = a[i] - '0'; val += b[i] - '0'; val += want; want = val / 10LL; val %= 10LL; ans.push_back(val + '0'); } for (int j = a.size(); j < b.size(); j++){ long long int val = 0; val += b[j] - '0'; val += want; want = val / 10LL; val %= 10LL; ans.push_back(val + '0'); } while (want){ ans.push_back(want % 10 + '0'); want /= 10; } if (!flag){ reverse(ans.begin(), ans.end()); } return ans; } string mult(string a, string b, bool flag = false){ if (!flag){ reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); } string ans = "0"; string pas; string kari; pas.clear(); for (int i = 0; i < b.size(); i++){ long long int bb = b[i] - '0'; long long int tmp = 0; kari = pas; for (int j = 0; j < a.size(); j++){ long long int val = (long long int)(a[j] - '0')*bb; val += tmp; tmp = val / 10LL; val %= 10LL; kari.push_back(val + '0'); } while (tmp){ kari.push_back((tmp % 10LL) + '0'); tmp /= 10LL; } ans = pluss(ans, kari, true); //end pas.push_back('0'); } if (!flag){ reverse(ans.begin(), ans.end()); } return ans; } string zero = "0"; vector v; string kari; struct st{ string ind[12]; st(){ for (int i = 0; i < 12; i++){ ind[i] = zero; } } void mult_x(int num=1){ for (int i = 10; i >= 0; i--){ if (i + num < 12){ ind[i + num] = ind[i]; } } } void mult_val(string num){ for (int i = 0; i <= 10; i++){ if (ind[i] != zero){ ind[i] = mult(ind[i], num); } } } st ex(){ for (int i = 1; i <= 10; i++){ ind[i - 1] = ind[i]; ind[i - 1] = mult(ind[i - 1], v[i]); } return *this; } void output(){ for (int i = 0; i <= d; i++){ if (i){ printf(" "); } printf("%s", ind[i].c_str()); } } void merge(st a){ for (int i = 0; i <= d; i++){ ind[i] = pluss(ind[i], a.ind[i]); } } void add(int id, string val){ ind[id] = pluss(ind[id], val); } }; inline st dfs(int l,int r){ st R; int countt = 0; string val = "1"; bool flag = false; while (l <= r){ if (s[l] == '}' || s[l] == '+'){ if (flag){ R.add(countt, val); val = "1"; countt = 0; flag = false; } l++; continue; } if (s[l] == '{'){ l++; continue; } if (s[l] == 'd'){ R.merge(dfs(l + 2, be[l]).ex()); l = be[l] + 1; continue; } if (s[l] == '*'){ l++; continue; } if (isdigit(s[l])){ flag = true; val = mult(val, v[s[l] - '0']); l++; continue; } if (s[l] == 'x'){ flag = true; countt++; l++; continue; } } if (flag){ R.add(countt, val); } return R; } int main(){ for (int i = 0; i <= 10; i++){ kari.clear(); kari.push_back(i + '0'); v.push_back(kari); } cin >> n >> d; cin >> s; stack st; for (int i = 0; i < s.size(); i++){ if (s[i] == 'd'){ st.push(i); } if (s[i]=='}'){ be[st.top()] = i; st.pop(); } } dfs(0, s.size() - 1).output(); return 0; }