Nén xâu (Run-Length Encoding)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho xâu $S$ chỉ gồm các chữ cái Latin in hoa từ A đến Z.

Chia $S$ thành các đoạn liên tiếp cực đại sao cho mọi ký tự trong cùng một đoạn đều giống nhau. Mỗi đoạn được mã hóa bằng ký tự của đoạn, ngay sau đó là số lần ký tự ấy xuất hiện. Số lần xuất hiện luôn được ghi, kể cả khi bằng $1$.

Hãy tạo xâu nén của $S$ theo quy tắc trên.

Input

Một dòng duy nhất chứa xâu $S$.

Output

In xâu nén tương ứng của $S$.

Subtask

• Subtask 1 (50 điểm): $1 \le |S| \le 10^3$.
• Subtask 2 (50 điểm): $1 \le |S| \le 10^6$.
• Trong mọi Subtask, $S$ chỉ gồm các ký tự A..Z.

Ví dụ

Input

AAABCCCCDDDA

Output

A3B1C4D3A1

Giải thích

Xâu được chia lần lượt thành năm đoạn: AAA, B, CCCC, DDD, A.

Độ dài các đoạn tương ứng là $3,1,4,3,1$, vì vậy các đoạn được mã hóa thành A3, B1, C4, D3, A1.

Ghép các phần này theo thứ tự ban đầu, ta nhận được A3B1C4D3A1.