Alice đang nghiên cứu về xâu mã hóa RLE. Cụ thể, xét xâu S chỉ gồm các kí tự từ 'a' đến 'z' được mã hóa thành xâu SE (chỉ gồm các kí tự 'a' đến 'z' và kí tự '0' đến '9') như sau: Đi từ trái qua phải, nếu một dãy các kí tự liên tiếp bằng nhau trong \(S\) thì thay bằng kí tự đại diện và số lượng. Độ dài các xâu mã hóa không vượt quá \(3000\).

Ví dụ, xâu \(S\) = "aaabbbbaaaaaaaaaaz" thì xâu mã hóa của \(S\) là \(SE\) = "a3b4a10z1".

Yêu cầu:

• Với xâu \(S\) được mã hóa thành \(SE\) và số nguyên \(k\), Alice muốn xóa bỏ \(k\) kí tự trong xâu \(SE\) để nhận được xâu Smax có thứ tự từ điển lớn nhất và xâu Smin có thứ tự từ điển nhỏ nhất. Hãy giúp Alice đưa ra xâu mã hóa của Smax và Smin.

Ví dụ:

Nếu xâu SE là "b1a1b10" và \(k = 1\) thì:

• Xâu mã hóa của Smax là "b11".
• Xâu mã hóa của Smin là "a1b10".

Dữ liệu vào:

• Dòng đầu chứa số nguyên k.
• Dòng thứ hai chứa xâu SE là mã hóa của S.

Dữ liệu ra:

• Dòng đầu ghi xâu mã hóa của Smax.
• Dòng thứ hai ghi xâu mã hóa của Smin.

Input 1

1
b1a1b10

Output 1

b11
a1b10

Ràng buộc:

• Subtask \(1\) (20% điểm): độ dài xâu \(S\) không vượt quá \(10\).
• Subtask \(2\) (20% điểm): độ dài xâu \(S\) không vượt quá \(10^2\).
• Subtask \(3\) (20% điểm): độ dài xâu \(S\) không vượt quá \(10^6\).
• Subtask \(4\) (20% điểm): độ dài xâu \(S\) không vượt quá \(10^9\).
• Subtask \(5\) (20% điểm): độ dài xâu \(S\) không vượt quá \(10^{18}\).