Xâu là một dãy các kí tự liên tiếp bao gồm các kí tự chữ cái tiếng Anh, kí tự số, kí tự đặc biệt và có thể chứa dấu cách. Ví dụ: [email protected], Ca Mau.

Yêu cầu: Với một xâu bất kì, hãy đưa ra các kí tự chữ cái tiếng Anh (không phân biệt chữ hoa hay thường) có mặt trong xâu và số lần xuất hiện của nó. Ví dụ: Xâu kí tự Tran Thi Ngoc Nga có kí tự a xuất hiện 2 lần, tương tự thì c(1), g(2), h(1), i(1), n(3), o(1), r(1), t(2).

Dữ liệu vào: Tệp tin văn bản demkitu.inp một xâu st có N kí tự thể hiện trên một dòng (0 < N < 2.10$^7$).

Dữ liệu ra: Ghi ra tệp tin văn bản demkitu.out gồm 1 dòng chứa kí tự ch là kí tự có mặt trong xâu st và một số nguyên dương k là số lần xuất hiện của ch trong st. Các kí tự ch được thể hiện theo thứ tự tăng dần và là các chữ cái viết thường (Xem ví dụ phía dưới để biết được dạng dữ liệu ra).

Ràng buộc:

• Có 50% số test tương ứng 50% số điểm của bài với 0 < N < 256.

• Có 30% số test tương ứng 30% số điểm của bài với 256 ≤ N ≤ 10$^6$.

• Có 20% số test tương ứng 20% số điểm của bài với 10$^6$ < N ≤ 2.10$^7$.

Input

Tran Thi Ngoc Nga

Output

a2
c1
g2
h1
i1
n3
o1
r1
t2