Bracket sequences#1663

Bracket sequences

1 second
128 megabytes
Very easy

Given a positive integer (1 \le n \le 10), print all correct bracket sequences of length in alphabetical order, assuming that the character '' comes before '' in the alphabet.

A correct bracket sequence is either an empty string, or a string of the form , where is a correct bracket sequence, or a string of the form S_1S_2, where S_1 and S_2 are correct bracket sequences.

Input

One integer (1 \le n \le 10).

Output

Print in alphabetical order all correct bracket sequences of length , one sequence per line, without spaces.

Examples

Example 1

Loading
Loading