Thống kê chữ cái in hoa

Cho một xâu chỉ gồm các chữ cái in hoa từ A đến Z. Với mỗi chữ cái có mặt trong xâu, hãy thống kê xem nó xuất hiện bao nhiêu lần.

Ví dụ, xâu BANANA có \(3\) chữ A, \(1\) chữ B và \(2\) chữ N.

Input

Một dòng chứa xâu chỉ gồm các chữ cái in hoa.

Output

Với mỗi chữ cái xuất hiện ít nhất một lần, in ra một dòng gồm chữ cái đó, một dấu cách rồi số lần xuất hiện. Các dòng được in theo thứ tự chữ cái từ A đến Z. Chữ cái không xuất hiện thì không in.

Constraints

• Độ dài xâu từ \(1\) đến \(10^6\).

Sample Input

QUANGNAMQ

Sample Output

A 2
G 1
M 1
N 2
Q 2
U 1