Birthday Statistics

Interview

Time limit1sMemory limit128 MB

Summary

Count how many of the n employees were born in each month and print the twelve monthly totals.

Level: Easy1 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

A company collected the birth dates of all of its employees. Write a program that counts how many employees were born in each month.

Input

The first line contains the number of employees $n$ ( $1 \le n \le 5000$ ).

Each of the next $n$ lines contains one employee's ID and that employee's birth date, separated by a space. The ID is a four-digit number, and the birth date is written as day/month/year.

Every date in the input is a real date.

Output

Print 12 lines, one for each month from 1 to 12 in that order. Each line contains the month number and the number of employees born in that month, separated by a space. A month with nobody born in it still gets a line, with the count 0.

Examples1

Example 1

Input

10
1000 1/2/1967
1012 13/10/1940
1103 5/1/1965
2012 16/7/1980
1125 18/9/1979
1235 10/10/1976
1400 16/11/1973
1013 5/1/1965
2109 28/7/1958
2155 10/12/1970

Expected output