Бүтін \(n\) саны берілген. Тек '(' және ')' таңбаларынан тұратын ұзындығы \(2n\) болатын барлық дұрыс жақша тізбектерін шығару керек.

Дұрыс жақша тізбегі рекурсивті түрде анықталады: бос жол дұрыс; егер \(A\) және \(B\) дұрыс болса, онда \((A)\) және \(AB\) жолдары да дұрыс болады.

Жауапты кез-келген ретпен шығарыңыз.

Енгізу

Жалғыз жолда бүтін \(n\) саны берілген (\(1 \le n \le 10\)).

Шығару

Ұзындығы \(2n\) болатын барлық дұрыс жақша тізбектерін әрқайсысын жеке жолға шығарыңыз.

Мысалдар

Енгізу 1

3

Жауап 1

((()))
(()())
(())()
()(())
()()()