Bình đang học về mã hóa dữ liệu đơn giản. Một phương pháp là nén Run-Length Encoding (RLE): chuyển xâu \(S\) thành dãy các cặp (ký tự, số lần lặp). Ví dụ, xâu aaabbbcc được mã hóa thành a3b3c2. Hãy giúp Bình viết chương trình nén xâu theo RLE.

Định dạng đầu vào

• Một dòng chứa xâu \(S\) chỉ gồm chữ cái in thường, độ dài không quá \(10^5\).

Định dạng đầu ra

• In ra xâu đã nén theo RLE. Nếu độ dài xâu nén lớn hơn xâu gốc, in ra xâu gốc.

Ví dụ

Input:

aaabbbcc

Output:

a3b3c2

Input 2:

abc

Output 2:

abc

Ràng buộc

• 50% số điểm: \(|S| \le 1000\).
• 50% số điểm còn lại: \(|S| \le 10^5\).