Generate Parentheses

Given an integer \(n\), generate all combinations of well-formed parentheses consisting of exactly \(n\) pairs. A well-formed parentheses string is defined such that every opening parenthesis '(' has a corresponding closing parenthesis ')', and the pairs are properly nested.

Your task is to output all valid combinations in lexicographical order. This means that the combinations should be sorted as they would appear in a dictionary.

inputFormat

Input consists of a single integer (n) ((1 \le n \le 10)), which denotes the number of pairs of parentheses.

outputFormat

Output all valid well-formed parentheses combinations in lexicographical order. Each combination should be printed on a new line.## sample

1

()