여러 단어가 주어진다.

각 단어가 몇 번 등장했는지 세고, 등장 횟수가 많은 단어부터 정렬하여 출력하라.

등장 횟수가 같다면 단어의 사전순으로 정렬한다.

입력

첫째 줄에 단어의 개수 \(n\)이 주어진다.

둘째 줄부터 \(n\)개의 줄에 단어가 하나씩 주어진다.

\((1 \le n \le 1000)\)

단어의 길이는 \(1\) 이상 \(20\) 이하이다.

출력

정렬된 순서대로 단어와 등장 횟수를 한 줄에 하나씩 출력한다.

예제 입력

8
apple
banana
apple
kiwi
banana
apple
kiwi
banana

예제 출력

apple 3
banana 3
kiwi 2