Parentheses, episode 3

Given 5 integers n, give for each integer the different ways to arrange n pairs of parentheses. the output must be ordered lexicographically.

Input

  • 0 ≤ n ≤ 13

Examples

Input :

0
1
2

Output :

[""]
["()"]
["()()","(())"]

I/O SU

Évènement organisé par ALIAS