Nén và giải nén xâu

Một phần mềm lưu trữ dùng phương pháp mã hoá độ dài chạy để rút gọn văn bản: mỗi đoạn gồm các ký tự giống hệt nhau đứng liền kề được thay bằng số lần lặp viết liền trước ký tự đó. Số lần lặp luôn được viết ra, kể cả khi bằng \(1\). Ví dụ aaabbbbc được nén thành 3a4b1c.

Bạn cần cài đặt cả hai chiều: nén một xâu và giải nén một xâu đã nén.

Input

• Dòng 1: xâu \(S\) cần nén, chỉ gồm các chữ cái Latinh (hoa và thường phân biệt nhau).
• Dòng 2: xâu \(T\) đã ở dạng nén, gồm các cặp (số nguyên dương, chữ cái) viết liền nhau như trên.

Output

• Dòng 1: dạng nén của \(S\) (mỗi đoạn ký tự giống nhau tối đa liên tiếp được thay bằng số lần + ký tự).
• Dòng 2: xâu thu được sau khi giải nén \(T\).

Constraints

• \(1 \le |S|, |T| \le 10^6\).
• Xâu sau khi giải nén \(T\) có độ dài không quá \(10^6\).

Sample Input

wwwwkkkTT
3k1Z2m

Sample Output

4w3k2T
kkkZmm

Explanation

wwww kkk TT lần lượt thành 4w, 3k, 2T. Ở chiều ngược lại 3k là kkk, 1Z là Z, 2m là mm.