#include <bits/stdc++.h>
#define ll long long
#define el cout << '\n'
using namespace std;
const int maxn = 1e3;
const ll INF = 3e18;
int n, k, mx = 0, level = 0;
ll dp[maxn + 10][maxn + 10][2], ans = 1, p;
string s;
vector<char> stk, tmp, res;
void add(ll &a, ll b)
{
a += b;
a = min(a, INF);
}
bool is_open(char c)
{
return c == '(' || c == '[' || c == '{';
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("BRCNT1.INP", "r"))
{
freopen("BRCNT1.INP", "r", stdin);
freopen("BRCNT1.OUT", "w", stdout);
}
cin >> n >> k;
cin >> s;
s = ' ' + s;
cin >> p;
dp[n + 1][0][0] = 1;
for (int i = n + 1; i - 1; i--)
for (int j = 0; j <= k; j++)
for (int t = 0; t <= 1; t++)
{
add(dp[i - 1][j + 1][t || (j + 1 == k)], dp[i][j][t]);
if (j)
add(dp[i - 1][j - 1][t], 3 * dp[i][j][t]);
}
for (int i = 1; i <= n; i++)
{
level += is_open(s[i]) ? 1 : -1;
mx = max(mx, level);
if (s[i] == '(')
continue;
if (s[i] == '[')
{
ans += dp[i + 1][level][1];
if (mx == k)
ans += dp[i + 1][level][0];
}
else if (s[i] == '{')
{
ans += 2 * dp[i + 1][level][1];
if (mx == k)
ans += 2 * dp[i + 1][level][0];
}
else if (level + 2 <= k)
{
ans += 3 * dp[i + 1][level + 2][1];
if (mx == k || level + 2 == k)
ans += 3 * dp[i + 1][level + 2][0];
}
}
cout << ans, el;
level = 0;
mx = 0;
for (int i = 1; i <= n; i++)
{
mx = max(mx, level);
if (mx == k)
{
if (level + 1 <= k)
{
ll m = dp[i + 1][level + 1][0] + dp[i + 1][level + 1][1];
if (m >= p)
{
tmp.push_back('(');
level++;
continue;
}
else
p -= m;
if (m >= p)
{
tmp.push_back('[');
level++;
continue;
}
else p -= m;
if (m >= p)
{
tmp.push_back('{');
level++;
continue;
}
else p -= m;
}
tmp.push_back(')');
level--;
}
else
{
if (level + 1 <= k)
{
ll m = dp[i + 1][level + 1][1];
if (m >= p)
{
tmp.push_back('(');
level++;
continue;
}
else
p -= m;
if (m >= p)
{
tmp.push_back('[');
level++;
continue;
}
else p -= m;
if (m >= p)
{
tmp.push_back('{');
level++;
continue;
}
else p -= m;
}
tmp.push_back(')');
level--;
}
}
for (char c : tmp)
{
if (c == ')')
{
if (stk.back() == '(')
res.push_back(')');
if (stk.back() == '[')
res.push_back(']');
if (stk.back() == '{')
res.push_back('}');
stk.pop_back();
}
else
{
stk.push_back(c);
res.push_back(c);
}
}
for (char c : res)
cout << c;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGVsIGNvdXQgPDwgJ1xuJwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBtYXhuID0gMWUzOwpjb25zdCBsbCBJTkYgPSAzZTE4OwoKaW50IG4sIGssIG14ID0gMCwgbGV2ZWwgPSAwOwpsbCBkcFttYXhuICsgMTBdW21heG4gKyAxMF1bMl0sIGFucyA9IDEsIHA7CnN0cmluZyBzOwp2ZWN0b3I8Y2hhcj4gc3RrLCB0bXAsIHJlczsKCnZvaWQgYWRkKGxsICZhLCBsbCBiKQp7CiAgICBhICs9IGI7CiAgICBhID0gbWluKGEsIElORik7Cn0KYm9vbCBpc19vcGVuKGNoYXIgYykKewogICAgcmV0dXJuIGMgPT0gJygnIHx8IGMgPT0gJ1snIHx8IGMgPT0gJ3snOwp9CgppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgaWYgKGZvcGVuKCJCUkNOVDEuSU5QIiwgInIiKSkKICAgIHsKICAgICAgICBmcmVvcGVuKCJCUkNOVDEuSU5QIiwgInIiLCBzdGRpbik7CiAgICAgICAgZnJlb3BlbigiQlJDTlQxLk9VVCIsICJ3Iiwgc3Rkb3V0KTsKICAgIH0KCiAgICBjaW4gPj4gbiA+PiBrOwogICAgY2luID4+IHM7CiAgICBzID0gJyAnICsgczsKICAgIGNpbiA+PiBwOwoKICAgIGRwW24gKyAxXVswXVswXSA9IDE7CiAgICBmb3IgKGludCBpID0gbiArIDE7IGkgLSAxOyBpLS0pCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPD0gazsgaisrKQogICAgICAgICAgICBmb3IgKGludCB0ID0gMDsgdCA8PSAxOyB0KyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGFkZChkcFtpIC0gMV1baiArIDFdW3QgfHwgKGogKyAxID09IGspXSwgZHBbaV1bal1bdF0pOwogICAgICAgICAgICAgICAgaWYgKGopCiAgICAgICAgICAgICAgICAgICAgYWRkKGRwW2kgLSAxXVtqIC0gMV1bdF0sIDMgKiBkcFtpXVtqXVt0XSk7CiAgICAgICAgICAgIH0KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBsZXZlbCArPSBpc19vcGVuKHNbaV0pID8gMSA6IC0xOwogICAgICAgIG14ID0gbWF4KG14LCBsZXZlbCk7CiAgICAgICAgaWYgKHNbaV0gPT0gJygnKQogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICBpZiAoc1tpXSA9PSAnWycpCiAgICAgICAgewogICAgICAgICAgICBhbnMgKz0gZHBbaSArIDFdW2xldmVsXVsxXTsKICAgICAgICAgICAgaWYgKG14ID09IGspCiAgICAgICAgICAgICAgICBhbnMgKz0gZHBbaSArIDFdW2xldmVsXVswXTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZiAoc1tpXSA9PSAneycpCiAgICAgICAgewogICAgICAgICAgICBhbnMgKz0gMiAqIGRwW2kgKyAxXVtsZXZlbF1bMV07CiAgICAgICAgICAgIGlmIChteCA9PSBrKQogICAgICAgICAgICAgICAgYW5zICs9IDIgKiBkcFtpICsgMV1bbGV2ZWxdWzBdOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmIChsZXZlbCArIDIgPD0gaykKICAgICAgICB7CiAgICAgICAgICAgIGFucyArPSAzICogZHBbaSArIDFdW2xldmVsICsgMl1bMV07CiAgICAgICAgICAgIGlmIChteCA9PSBrIHx8IGxldmVsICsgMiA9PSBrKQogICAgICAgICAgICAgICAgYW5zICs9IDMgKiBkcFtpICsgMV1bbGV2ZWwgKyAyXVswXTsKICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8IGFucywgZWw7CiAgICBsZXZlbCA9IDA7CiAgICBteCA9IDA7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICB7CiAgICAgICAgbXggPSBtYXgobXgsIGxldmVsKTsKICAgICAgICBpZiAobXggPT0gaykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChsZXZlbCArIDEgPD0gaykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGwgbSA9IGRwW2kgKyAxXVtsZXZlbCArIDFdWzBdICsgZHBbaSArIDFdW2xldmVsICsgMV1bMV07CiAgICAgICAgICAgICAgICBpZiAobSA+PSBwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHRtcC5wdXNoX2JhY2soJygnKTsKICAgICAgICAgICAgICAgICAgICBsZXZlbCsrOwogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHAgLT0gbTsKICAgICAgICAgICAgICAgIGlmIChtID49IHApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgdG1wLnB1c2hfYmFjaygnWycpOwogICAgICAgICAgICAgICAgICAgIGxldmVsKys7CiAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIHAgLT0gbTsKICAgICAgICAgICAgICAgIGlmIChtID49IHApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgdG1wLnB1c2hfYmFjaygneycpOwogICAgICAgICAgICAgICAgICAgIGxldmVsKys7CiAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIHAgLT0gbTsKICAgICAgICAgICAgfQogICAgICAgICAgICB0bXAucHVzaF9iYWNrKCcpJyk7CiAgICAgICAgICAgIGxldmVsLS07CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGlmIChsZXZlbCArIDEgPD0gaykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGwgbSA9IGRwW2kgKyAxXVtsZXZlbCArIDFdWzFdOwogICAgICAgICAgICAgICAgaWYgKG0gPj0gcCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB0bXAucHVzaF9iYWNrKCcoJyk7CiAgICAgICAgICAgICAgICAgICAgbGV2ZWwrKzsKICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBwIC09IG07CiAgICAgICAgICAgICAgICBpZiAobSA+PSBwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHRtcC5wdXNoX2JhY2soJ1snKTsKICAgICAgICAgICAgICAgICAgICBsZXZlbCsrOwogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBwIC09IG07CiAgICAgICAgICAgICAgICBpZiAobSA+PSBwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHRtcC5wdXNoX2JhY2soJ3snKTsKICAgICAgICAgICAgICAgICAgICBsZXZlbCsrOwogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZSBwIC09IG07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgdG1wLnB1c2hfYmFjaygnKScpOwogICAgICAgICAgICBsZXZlbC0tOwogICAgICAgIH0KICAgIH0KICAgIGZvciAoY2hhciBjIDogdG1wKQogICAgewogICAgICAgIGlmIChjID09ICcpJykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChzdGsuYmFjaygpID09ICcoJykKICAgICAgICAgICAgICAgIHJlcy5wdXNoX2JhY2soJyknKTsKICAgICAgICAgICAgaWYgKHN0ay5iYWNrKCkgPT0gJ1snKQogICAgICAgICAgICAgICAgcmVzLnB1c2hfYmFjaygnXScpOwogICAgICAgICAgICBpZiAoc3RrLmJhY2soKSA9PSAneycpCiAgICAgICAgICAgICAgICByZXMucHVzaF9iYWNrKCd9Jyk7CiAgICAgICAgICAgIHN0ay5wb3BfYmFjaygpOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBzdGsucHVzaF9iYWNrKGMpOwogICAgICAgICAgICByZXMucHVzaF9iYWNrKGMpOwogICAgICAgIH0KICAgIH0KICAgIGZvciAoY2hhciBjIDogcmVzKQogICAgICAgIGNvdXQgPDwgYzsKfQo=