Sort the dates

Sort the dates according to the following criteria:

• in non-decreasing order of years;

• if the dates have the same year, then sort them in non-decreasing order of months;

• if the dates have the same year and month, then sort them in non-decreasing order of days.

Input

The first line contains the number of dates $n(1\le n\le 1000)$. Each of the following $n$ lines contains a date in the format day.month.year. Each date is specified with three integers — day (from $1$ to $31$), month (from $1$ to $12$) and year (from $1900$ to $2021$).

Output

Print the dates in non-decreasing order in the same format as they are given in the input.

Examples