A coastal survey team monitors a chain of automated lighthouses, each broadcasting a distinct signal frequency that passing ships can subscribe to for weather and hazard updates. The team logged every subscription event recorded during the survey period as a (ship, lighthouse) pair, and no ship ever subscribes to the same lighthouse twice. For every lighthouse that received at least one subscription, report how many ships subscribed to it, so the harbor office can decide which lighthouses need stronger transmitters.

Input format

• Line 1: a single integer n, the number of subscription records.
• Each of the next n lines contains two integers ship_id and lighthouse_id, meaning ship ship_id is subscribed to lighthouse lighthouse_id. No (ship_id, lighthouse_id) pair repeats.

Output format

For every lighthouse_id that appears in the input, print one line "lighthouse_id count" (space-separated), where count is the number of ships subscribed to that lighthouse. Print the lines ordered by lighthouse_id in strictly increasing order. If n is 0, print nothing.

Constraints

• 0 <= n <= 10^5
• 1 <= ship_id, lighthouse_id <= 10^9

4
1 2
2 2
3 1
1 1

1 2
2 2

1
5 100

100 1