Nén chuỗi

Bạn là một kỹ sư phần mềm tại một công ty phát triển hệ thống gửi email tự động. Để tiết kiệm băng thông và tăng hiệu suất, bạn muốn nén các chuỗi ký tự lặp lại trong email bằng một phương pháp nén đơn giản.

Một chuỗi được nén hợp lệ sẽ có dạng như sau:

• Một chuỗi con được lặp lại liên tiếp \(D\) lần được viết thành \(D(S)\), trong đó \(S\) là chuỗi con lặp lại và \(D \ge 2\).

• Chuỗi được cấu thành từ hai chuỗi \(A\) và \(B\) hợp lệ, khi đó chuỗi \(AB\) là hợp lệ.

• Chuỗi được giữ nguyên so với chuỗi gốc - không thay đổi.

\end itemize

Ví dụ: Chuỗi abababaaaaa có thể được nén thành \(3(ab)5(a)\).

Yêu cầu của bạn là tìm ra cách nén ngắn nhất cho một chuỗi đã cho. Nếu có nhiều cách có cùng độ dài ngắn nhất, chọn cách có thứ tự từ điển nhỏ hơn.

Input

Dữ liệu vào gồm hai dòng:
\begin itemize

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 200\)) --- độ dài chuỗi.
• Dòng thứ hai chứa chuỗi đầu vào \(s\) gồm đúng \(n\) ký tự thường.
  \end itemize

Output

Ghi ra chuỗi đã nén ngắn nhất theo định dạng trên.

Example

10
zzzzzzzzzz

10(z)

4
aaaa

4(a)

3
bbb

bbb

24
abababcaaaaaabababcaaaaa

2(3(ab)c5(a))

Scoring

• Có 50% số điểm ứng với \(1 \le N \le 15\).
• Có 20% số điểm ứng với \(1 \le N \le 70\).
• 30% số điểm còn lại không có ràng buộc gì thêm.