Bạn là một kỹ sư phần mềm tại một công ty chuyên phát triển hệ thống gửi email tự động. Hệ thống này cần gửi đi hàng triệu email mỗi ngày, nhiều email chứa các chuỗi ký tự dài lặp lại. Việc gửi những chuỗi dài như vậy làm tăng đáng kể chi phí băng thông và thời gian xử lý.

Bạn quyết định áp dụng một thuật toán nén đơn giản để giảm độ dài chuỗi: tìm kiếm các đoạn lặp lại trong chuỗi và thay thế chúng bằng một biểu diễn ngắn gọn hơn. Phương pháp nén này sử dụng các chữ số để biểu thị số lần lặp lại, kèm theo đoạn lặp được đặt trong dấu ngoặc đơn. Ví dụ: chuỗi abababaaaaa có thể được nén thành 3(ab)5(a), trong đó 3(ab) biểu thị rằng chuỗi ab xuất hiện 3 lần liên tiếp, 5(a) biểu thị rằng ký tự a xuất hiện 5 lần liên tiếp.

Định nghĩa cú pháp nén:

• <L> là một ký tự chữ thường trong khoảng từ a đến z;
• <D> là một số nguyên lớn hơn hoặc bằng 2, biểu thị số lần lặp lại của chuỗi con bên trong dấu ngoặc đơn;
• <R> có thể là một ký tự <L> duy nhất hoặc một chuỗi nén bằng cách sử dụng một số nguyên <D> và một phần tử <S>;
• <S> biểu diễn một chuỗi ký tự đã nén, có thể bao gồm một hoặc nhiều phần tử <R>.

Yêu cầu: Hãy viết chương trình để tìm ra cách nén chuỗi đầu vào ~A~ có độ dài là ~N~ sao cho biểu diễn kết quả có độ dài ngắn nhất. Nếu có nhiều cách nén chuỗi đầu vào ~A~ với độ dài ngắn nhất, hãy đưa ra cách có thứ tự từ điển nhỏ nhất.

Dữ liệu

Đọc từ tệp văn bản WSTRING.INP có dạng:

• Dòng đầu tiên gồm một số nguyên ~N~ (~1 \le N \le 200~) là độ dài của chuỗi đầu vào ~A~;
• Dòng thứ hai gồm chuỗi đầu vào ~A~. Chuỗi ~A~ chỉ bao gồm các ký tự Latin thường.

Kết quả

Ghi ra tệp văn bản WSTRING.OUT một chuỗi ký tự là chuỗi nén theo yêu cầu.

Ví dụ 1

Input

15
zzzzzzzzzzzzzzz

Output

15(z)

Ví dụ 2

Input

4
aaaa

Output

4(a)

Ví dụ 3

Input

3
bbb

Output

bbb

Ví dụ 4

Input

7
abcdefg

Output

abcdefg

Ví dụ 5

Input

24
abababcaaaaaabababcaaaaa

Output

2(3(ab)c5(a))

Ví dụ 6

Input

11
abababaaaaa

Output

3(ab)5(a)

Giải thích

• Ở ví dụ 2, có 2 cách biểu diễn ngắn nhất. Cách thứ nhất là giữ nguyên aaaa với độ dài là 4. Cách thứ hai là nén thành 4(a), cũng với độ dài 4. Cả 2 cách đều có độ dài là 4, nhưng cách thứ 2 có thứ tự từ điển bé hơn, vì vậy kết quả là 4(a);
• Ở ví dụ 3, nếu giữ nguyên thì độ dài là 3, còn nếu nén thành 3(b) thì độ dài là 4.

Giới hạn

• Có 60% số test tương ứng với 60% số điểm có ~1 \le N \le 10~;
• Có 20% số test tương ứng với 20% số điểm có ~5 \le N \le 25~ và chuỗi ~A~ chỉ bao gồm ký tự a, b;
• Có 20% số test tương ứng với 20% số điểm không có ràng buộc gì thêm.