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 hơn. Phương pháp nén này sử dụng các số đếm độ 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ể nén thành "~3(ab)5(a)~", trong đó "~3(ab)~" biểu thị đoạn "~ab~" được lặp lại ~3~ lần, "~5(a)~", biểu thị 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ự 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ự <~A~> 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ử <~R~> khác.

  • <~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: Cho một chuỗi ~A~, hãy xác định cách nén chuỗi ~A~ sao cho độ dài biểu diễn của nó là ngắn nhất có thể. Biểu diễn độ dài của chuỗi nén nếu có nhiều cách nén có độ dài ngắn nhất thì chọn cách nào xuất hiện đầu tiên từ trái sang phải trong chuỗi gốc ~A~.

Input

Vào từ file văn bản WSTRING.INP:

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

Output

Ghi ra file văn bản WSTRING.OUT: Một chuỗi ký tự ~S~, là chuỗi đã được nén sao cho độ dài là ngắn nhất.

Scoring

• Subtask ~1~ ~(60\%)~: ~1\leq N\leq 10~.
• Subtask ~2~ ~(20\%)~: ~5\leq N\leq 25~ và chuỗi ~A~ chỉ gồm các chữ cái ~a~ và ~b~.
• Subtask ~3~ ~(20\%)~: Không có ràng buộc gì thêm.

Example input 1

15
zzzzzzzzzzzzzzz

Example output 1

15(z)

Example input 2

4
aaaa

Example output 2

4(a)

Note 2

Có ~2~ cách biểu diễn ngắn nhất là "~aaaa~" và "~4(a)~", đều dài ~4~ ký tự. Tuy nhiên, "~4(a)~" được ưu tiên vì có thứ tự từ điển bé hơn.

Example input 3

3
bbb

Example output 3

bbb

Note 3

Chúng ta giữ nguyên chuỗi thì sẽ có độ dài là ~3~ còn nếu chúng ta nén thành "~3(b)~" thì sẽ có độ dài là ~4~.

Example input 4

7
abcdefg

Example output 4

abcdefg

Example input 5

22
ababbaaaaaaaahabbabcaaan

Example output 5

2(3(ab)5(a))

Example input 6

11
ahbabaaaaaa

Example output 6

3(ab)5(a)