A community mentorship program keeps a running log of every mentoring session it holds. Each log entry records the mentor who ran the session, the skill that was taught, and the cohort the session belonged to. The same mentor may end up teaching the same skill again in a different cohort, and that should not be counted twice. For every mentor who appears anywhere in the log, the program wants to know how many distinct skills that mentor has taught in total, across every cohort combined.

Input format

Line 1: an integer n -- the number of log entries. Next n lines: each contains three integers mentor_id, skill_id, cohort_id -- one mentoring session.

Output format

Print one line for every distinct mentor_id that appears in the log, sorted by mentor_id ascending. Each line contains mentor_id followed by a single space and the number of distinct skill_id values that mentor taught (counted once no matter how many cohorts or log entries repeat it).

Constraints

• 1 <= n <= 1000
• 1 <= mentor_id, skill_id, cohort_id <= 100000
• The same (mentor_id, skill_id, cohort_id) triple, or the same (mentor_id, skill_id) pair with a different cohort_id, may repeat in the log.

3
1 2 3
1 2 4
1 3 3

1 2

4
1 2 1
2 3 1
2 3 2
2 4 1

1 1
2 2