Trong giờ học Tin học, cô giáo đưa cho An một xâu ký tự chỉ gồm các chữ cái tiếng Anh in thường. An muốn biết với mỗi chữ cái trong xâu, chữ cái đó xuất hiện tất cả bao nhiêu lần trong toàn bộ xâu.

Tuy nhiên, An cần giữ nguyên thứ tự các chữ cái như trong xâu ban đầu. Em hãy giúp An thực hiện yêu cầu này.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 10^5\)).
• Dòng thứ hai chứa xâu \(S\) gồm đúng \(n\) chữ cái tiếng Anh in thường từ a đến z.

Output

• Gồm \(n\) dòng. Dòng thứ \(i\) ghi ký tự \(S_i\) và số lần xuất hiện của ký tự đó trong xâu \(S\).

Example

9
abacbcaba

a 4
b 3
a 4
c 2
b 3
c 2
a 4
b 3
a 4

a 4
b 3
a 4
c 2
b 3
c 2
a 4
b 3
a 4

Constraints

• \(n \le 10^5\)
• Xâu \(S\) chỉ gồm các chữ cái tiếng Anh in thường.