Một dãy ngoặc hợp lệ được định nghĩa như sau:

• Xâu rỗng là một dãy ngoặc hợp lệ.
• Nếu B là một dãy ngoặc hợp lệ thì (B) cũng là một dãy ngoặc hợp lệ.
• Nếu L và R là hai dãy ngoặc hợp lệ thì phép nối LR cũng là một dãy ngoặc hợp lệ.

Gọi B là một dãy ngoặc hợp lệ có độ dài N; ký tự ở vị trí i được ký hiệu là B_i. Với hai vị trí i < j, B_i và B_j là một cặp ngoặc khớp nhau nếu B_i = '(', B_j = ')', và các ký tự nằm giữa chúng tạo thành một dãy ngoặc hợp lệ hoặc j = i + 1.

Cho xâu S gồm N chữ cái tiếng Anh viết thường. Dãy ngoặc hợp lệ B khớp với S nếu B có độ dài N và hai ký tự trong mọi cặp ngoặc khớp của B nằm ở các vị trí có cùng chữ cái trong S.

Hãy tìm dãy ngoặc hợp lệ nhỏ nhất theo thứ tự từ điển khớp với S. Nếu không tồn tại, in -1. Khi so sánh thứ tự từ điển, ký tự ( nhỏ hơn ký tự ).

Dữ liệu vào

Một dòng chứa xâu S gồm N chữ cái tiếng Anh viết thường.

Dữ liệu ra

In ra dãy ngoặc hợp lệ nhỏ nhất theo thứ tự từ điển khớp với S, hoặc -1 nếu không tồn tại.

Ràng buộc

• 2 ≤ N ≤ 100000.

Phân nhóm

• Nhóm 1: N ≤ 18, đạt 10 điểm.
• Nhóm 2: N ≤ 2000, đạt thêm 27 điểm.
• Nhóm 3: Không có ràng buộc bổ sung, đạt 63 điểm còn lại.

Ví dụ

abbaaa

(()())

abab

-1

Nguồn

CEOI 2016, Ngày 2, Bài 1.