#include<stdio.h>
int main()
{
int i=1, j, x, y, a, b, k, c;
char tab[5009];
for(j=0;j<c;++j)tab[j]='(';
for(j=c;j<2*c;++j)tab[j]=')';
while(1)
{
for(x=1,j=2*c-2;j>=0;j-=2)
if(tab[j]=='('&&tab[j+1]==')')++x;
else break;
if(x-1==c)break;
for(j=2*c-2,y=0;j;--j)
{
if(tab[j]=='(')++y;
if(y==x)break;
}
tab[j]=')';tab[j+1]='(';
for(a=b=0,k=j+2;k<2*c;++k)
if(tab[k]=='(')++a;
else ++b;
for(k=j+2;k<2*c;++k)
if(k-j-2<a)tab[k]='(';
else tab[k]=')';
}
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KCmludCBtYWluKCkKewoJaW50IGk9MSwgaiwgeCwgeSwgYSwgYiwgaywgYzsKCWNoYXIgdGFiWzUwMDldOwoJCglzY2FuZigiJWQiLCZjKTsKCWZvcihqPTA7ajxjOysrail0YWJbal09JygnOwoJZm9yKGo9YztqPDIqYzsrK2opdGFiW2pdPScpJzsKCXdoaWxlKDEpCgl7CgkJcHJpbnRmKCIlZC5cdCVzXG4iLGkrKyx0YWIpOwoJCWZvcih4PTEsaj0yKmMtMjtqPj0wO2otPTIpCgkJCWlmKHRhYltqXT09JygnJiZ0YWJbaisxXT09JyknKSsreDsKCQkJZWxzZSBicmVhazsKCQlpZih4LTE9PWMpYnJlYWs7CgkJZm9yKGo9MipjLTIseT0wO2o7LS1qKQoJCXsKCQkJaWYodGFiW2pdPT0nKCcpKyt5OwoJCQlpZih5PT14KWJyZWFrOwoJCX0KCQl0YWJbal09JyknO3RhYltqKzFdPScoJzsKCQlmb3IoYT1iPTAsaz1qKzI7azwyKmM7KytrKQoJCQlpZih0YWJba109PScoJykrK2E7CgkJCWVsc2UgKytiOwoJCWZvcihrPWorMjtrPDIqYzsrK2spCgkJCWlmKGstai0yPGEpdGFiW2tdPScoJzsKCQkJZWxzZSB0YWJba109JyknOwoJfQoJcmV0dXJuIDA7Cn0=