#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
using namespace std;
const int max_n = 50;
int memo[max_n];
int count(int n)
{
if (n == 0)
return 1;
int &ans = memo[n];
if (ans != -1)
return ans;
ans = 0;
for (int i = 0; i < n; ++i)
ans += count(i) * count(n - 1 - i);
return ans;
}
void bracket(int n)
{
if (n == 0)
return;
int r = rand() % count(n);
int left_len = 0;
while (r >= count(left_len) * count(n - 1 - left_len)) {
r -= count(left_len) * count(n - 1 - left_len);
++left_len;
}
int right_len = n - 1 - left_len;
cout << '(';
bracket(left_len);
cout << ')';
bracket(right_len);
}
int main()
{
srand(time(NULL));
int n;
cin >> n;
memset(memo, -1, sizeof memo);
bracket(n);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjdGltZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBtYXhfbiA9IDUwOwppbnQgbWVtb1ttYXhfbl07CgppbnQgY291bnQoaW50IG4pCnsKCWlmIChuID09IDApCgkJcmV0dXJuIDE7CgkKCWludCAmYW5zID0gbWVtb1tuXTsKCWlmIChhbnMgIT0gLTEpCgkJcmV0dXJuIGFuczsKCQkKCWFucyA9IDA7Cglmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKCQlhbnMgKz0gY291bnQoaSkgKiBjb3VudChuIC0gMSAtIGkpOwoJCglyZXR1cm4gYW5zOwp9Cgp2b2lkIGJyYWNrZXQoaW50IG4pCnsKCWlmIChuID09IDApCgkJcmV0dXJuOwoJCglpbnQgciA9IHJhbmQoKSAlIGNvdW50KG4pOwoJaW50IGxlZnRfbGVuID0gMDsKCXdoaWxlIChyID49IGNvdW50KGxlZnRfbGVuKSAqIGNvdW50KG4gLSAxIC0gbGVmdF9sZW4pKSB7CgkJciAtPSBjb3VudChsZWZ0X2xlbikgKiBjb3VudChuIC0gMSAtIGxlZnRfbGVuKTsKCQkrK2xlZnRfbGVuOwoJfQoJaW50IHJpZ2h0X2xlbiA9IG4gLSAxIC0gbGVmdF9sZW47CgkKCQoJY291dCA8PCAnKCc7CglicmFja2V0KGxlZnRfbGVuKTsKCWNvdXQgPDwgJyknOwoJYnJhY2tldChyaWdodF9sZW4pOwp9CQoKaW50IG1haW4oKQp7CglzcmFuZCh0aW1lKE5VTEwpKTsKCQoJaW50IG47CgljaW4gPj4gbjsKCQoJbWVtc2V0KG1lbW8sIC0xLCBzaXplb2YgbWVtbyk7CgkKCWJyYWNrZXQobik7CgkKCXJldHVybiAwOwp9