Một dãy dấu ngoặc hợp lệ là một dãy các ký tự "(" và ")" được định nghĩa như sau:

• Dãy rỗng (không có ký tự nào) là một dãy dấu ngoặc hợp lệ
• Nếu A là một dãy dấu ngoặc hợp lệ thì (A) là dãy dấu ngoặc hợp lệ. Nếu A và B là hai dãy dấu ngoặc hợp lệ thì AB là dãy dấu ngoặc hợp lệ.
  Ví dụ: ((()))(())()() là một dãy dấu ngoặc hợp lệ còn )))((( không phải dãy dấu ngoặc hợp lệ

Yêu cầu:

Liệt kê các dãy ngoặc hợp lệ độ dài ~n~.

Dữ liệu:

Số nguyên dương chẵn ~n≤24~

Kết quả:

Các dãy ngoặc hợp lệ độ dài ~n~ liệt kê theo thứ tự từ điển, mỗi dãy một dòng

Input

4

Output

(())
()()