괄호 생성

문제

N쌍의 괄호로 만들 수 있는 모든 올바른 괄호 문자열을 사전순으로 출력하라.

여기서 올바른 괄호 문자열이란 다음 조건을 만족하는 문자열이다.

• 여는 괄호 (와 닫는 괄호 )의 개수가 같다.
• 문자열의 모든 접두사에 대해 여는 괄호의 개수가 닫는 괄호의 개수보다 같거나 많다.

입력

첫째 줄에 괄호 쌍의 개수 N이 주어진다.

• 1 ≤ N ≤ 10

출력

만들 수 있는 모든 올바른 괄호 문자열을 사전순으로 한 줄에 하나씩 출력한다.

예제 입력 1

2

예제 출력 1

(())
()()