Nén bản tin (Message Compression)

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

Đề bài

Một bản tin được biểu diễn bởi xâu $S$ chỉ gồm các chữ cái in hoa từ A đến Z.

Ta nén từng nhóm ký tự giống nhau liên tiếp theo quy tắc:

• Nếu một ký tự xuất hiện liên tiếp đúng một lần thì giữ nguyên ký tự đó.
• Nếu ký tự $c$ xuất hiện liên tiếp $k$ lần với $k \ge 2$, thay cả nhóm bởi ký tự $c$ rồi ghi ngay sau đó số $k$ ở hệ thập phân.

Ví dụ, AAABBCCCCDAA được nén thành A3B2C4DA2.

Hãy tạo xâu nén $T$ và xác định độ dài $|T|$.

Input

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

Output

• Dòng thứ nhất ghi xâu nén $T$.
• Dòng thứ hai ghi số nguyên $|T|$ là độ dài của xâu nén.

Subtask

• Subtask 1 (40%): $1 \le |S| \le 255$.
• Subtask 2 (30%): $1 \le |S| \le 10^5$.
• Subtask 3 (30%): $1 \le |S| \le 10^6$.

Ví dụ

Ví dụ 1

Input

AAABBCCCCDAA

Output

A3B2C4DA2
9

Giải thích

Các nhóm liên tiếp là AAA, BB, CCCC, D, AA, có độ dài lần lượt $3,2,4,1,2$. Do đó chúng được viết thành A3, B2, C4, D, A2.

Ví dụ 2

Input

ABCDE

Output

ABCDE
5

Giải thích

Mỗi ký tự tạo thành một nhóm có độ dài $1$, nên xâu được giữ nguyên.

Ví dụ 3

Input

AAAAAAAAAAAA

Output

A12
3

Giải thích

Có $12$ ký tự A liên tiếp, nên cả nhóm được thay bằng A12, có độ dài $3$.