Xâu là dãy liên tiếp các kí tự (bao gồm kí tự chữ Latinh, số và dấu cách).

Yêu cầu: Cho xâu \(S\) có \(N\) kí tự (chỉ chứa các kí tự chữ Latinh và in thường). Hãy đếm số lần xuất hiện của các kí tự có trong xâu \(S\).

Dữ liệu vào

Từ tệp tin văn bản demkitu.inp gồm một dòng duy nhất chứa xâu \(S\) có \(N\) kí tự (\(1 \le N \le 10^6\)).

Dữ liệu ra

Ghi ra tệp tin văn bản demkitu.out gồm nhiều dòng, mỗi dòng gồm hai kết quả lần lượt là kí tự và số lần xuất hiện của nó trong xâu \(S\) (các kí tự được sắp xếp theo thứ tự Alpha), hai kết quả được ngăn cách nhau bởi một khoảng trắng.

Ví dụ

demkitu.inp

dbakabk

demkitu.out

a 2
b 2
d 1
k 2

Giải thích: Có 4 kí tự xuất hiện trong xâu \(S\) là a, b, d và k, với số lần xuất hiện:

• Kí tự 'a': 2 lần;
• Kí tự 'b': 2 lần;
• Kí tự 'd': 1 lần;
• Kí tự 'k': 2 lần.

Ràng buộc

Không có ràng buộc con (subtask) — toàn bộ test đều thỏa \(1 \le N \le 10^6\), \(S\) chỉ gồm chữ cái Latinh in thường (a-z).