Xét xâu S độ dài không vượt quá 10¹⁸ chỉ gồm các ký tự ‘a’ đến ’z’ được mã hoá 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, mã hoá dãy các ký tự liên tiếp bằng nhau trong S thành ký tự đại diện và số lượng. Độ dài các xâu mã hoá không vượt quá 1000.

Ví dụ, xâu S=aaabbbbaaaaaaaaaaz thì SE=a3b4a10z1

Yêu cầu: Cho xâu S được mã hoá thành SE và số nguyên k, hãy xoá bỏ k ký tự trong xâu S để nhận được xâu Smax có thứ tự từ điển lớn nhất, Smin nhỏ nhất. Đưa ra xâu mã hoá của Smin, Smax.
Ví dụ: XE=b1a1b10, k=1 thì xâu mã hoá của Smax là b11, còn xâu mã hoá của Smin là a1b10

Input

- Dòng 1: chứa số nguyên k (k<length(S));
- Dòng 2: chứa xâu SE là mã hóa của S.

Output

- Dòng 1: ghi Smax có thứ tự từ điển lớn nhất;
- Dòng 2: ghi Smin có thứ tự từ điển nhỏ nhất.