Question

The Courier's Nested Package Labels

A courier service uses a special labeling system for packages nested inside one another: each package gets an opening tag when it's placed inside another, and a matching closing tag when its own contents are sealed, forming a properly nested sequence (much like matched parentheses).

Given an integer n, generate every possible valid tag sequence using exactly n opening tags and n matching closing tags, where every opening tag has a corresponding closing tag later in the sequence, properly nested.

The resulting list of sequences must be sorted in lexicographically increasing order (treating an opening tag '(' as coming before a closing tag ')').

Input

A single line containing the integer KaTeX can only parse string typed expression.

Output

Print a single integer on the first line — the number of valid tag sequences. Then print that many lines, each containing one valid sequence, sorted lexicographically.

Example

Example 1:
Input

Output

5

((()))

(()())

(())()

()(())

()()()

Explanation
There are exactly 5 distinct ways to properly nest 3 pairs of tags, listed in sorted order.

Example 2:
Input

Output

1

()

Explanation
With only 1 pair, there is exactly one valid arrangement.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions