Ngoặc đúng từ xâu cho trước

Dãy ngoặc đúng được định nghĩa đệ quy: xâu rỗng là dãy ngoặc đúng; nếu \(A\) đúng thì \((A)\) đúng; nếu \(A, B\) đúng thì \(AB\) đúng.

Cho xâu \(S\) chỉ gồm các ký tự ( và ). Bằng cách xóa đi một số ký tự bất kỳ (có thể không xóa) và giữ nguyên thứ tự các ký tự còn lại, ta thu được các xâu con. Hãy liệt kê tất cả các dãy ngoặc đúng khác rỗng và đôi một khác nhau có thể thu được.

Input

• Một xâu \(S\) khác rỗng, độ dài không quá \(20\), chỉ gồm ( và ).

Output

• Dòng đầu: số lượng dãy tìm được (in 0 nếu không có).
• Các dòng sau: từng dãy, theo thứ tự từ điển tăng dần (theo mã ASCII, ( < )).

Constraints

• \(1 \le |S| \le 20\)

Sample Input

(()(()

Sample Output

3
(())
()
()()