Nén chuỗi

Ta nén một xâu chữ cái thường theo quy tắc sau. Một biểu diễn nén \(S\) là dãy gồm một hoặc nhiều phần tử \(R\) viết liền nhau, mỗi \(R\) là:

• một chữ cái thường a..z; hoặc
• có dạng D(S), trong đó \(D \ge 2\) là số nguyên viết bằng chữ số thập phân (không có số \(0\) đứng đầu) và \(S\) là một biểu diễn nén; nó biểu thị \(S\) (sau khi giải nén) được lặp lại \(D\) lần liền nhau.

Ví dụ abababaaaaa có thể viết là 3(ab)5(a).

Cho xâu \(A\) gồm \(N\) chữ cái thường. Hãy tìm biểu diễn nén của \(A\) có độ dài ngắn nhất (tính cả chữ số và dấu ngoặc). Nếu có nhiều biểu diễn cùng độ dài ngắn nhất, chọn biểu diễn nhỏ nhất theo thứ tự từ điển tính theo mã ASCII (( = 40, ) = 41, chữ số = 48..57, chữ cái thường = 97..122).

Input

• Dòng đầu là số nguyên \(N\).
• Dòng thứ hai là xâu \(A\) gồm \(N\) chữ cái thường.

Output

• In ra biểu diễn nén tìm được trên một dòng.

Constraints

• \(1 \le N \le 300\)
• Ở \(60\%\) số test \(N \le 10\); ở \(20\%\) số test \(N \le 25\) và xâu chỉ gồm a, b.

Sample Input

12
aabaabaabxyy

Sample Output

3(aab)xyy

Explanation

aab lặp \(3\) lần rồi đến xyy; biểu diễn 3(aab)xyy có độ dài \(9\), ngắn hơn xâu gốc.