Orders per customer

Problem

Every order has the name of its customer. Count how many orders each customer placed, and print the customers in alphabetical order.

Input: The first line has n. The second line has n customer names separated by spaces.
Output: One line <name> <orders> per customer, sorted by name (capital letters sort before small letters).
Constraints: 1 ≤ n ≤ 100000
Names have 1 to 20 letters

Example

Input

6
Riya Arjun Riya Meera Arjun Riya

Output

Arjun 2
Meera 1
Riya 3

Arjun 2 orders, Meera 1, Riya 3.

Try the problem first. Open one hint at a time.

Hint 1

A TreeMap keeps its keys sorted, so you do not need a separate sort.

Hint 2

Count with merge(name, 1, (a, b) -> a + b).

Write your Java code, run it on the examples and submit it to hidden tests.