Addresses in order

sorting networks bit tricks array

A server log has recorded n requests, one IPv4 address per line. The administrator needs a summary: each address once, in increasing order, and how many times it occurred in the log. Increasing means as numbers: the address a.b.c.d is the 32-bit number a·2²⁴ + b·2¹⁶ + c·2⁸ + d, so 10.0.0.9 comes before 10.0.0.10, and 20.1.1.1 before 100.1.1.1.

The addresses in the tests are made up: a few busy networks that requests come from again and again, and a long tail of random one-time visitors.

Input

The first line holds n (1 ≤ n ≤ 100,000). Then n lines, each an IPv4 address: four numbers from 0 to 255 separated by dots, without leading zeros.

Output

The first line is how many distinct addresses the log has. Then a line per address, in increasing order: the address and, after a space, how many times it occurred.

Examples

Example 1

Input

9
10.0.0.9
10.0.0.10
192.168.1.1
10.0.0.9
9.255.255.255
100.1.1.1
20.1.1.1
10.0.0.10
10.0.0.9

Output

6
9.255.255.255 1
10.0.0.9 3
10.0.0.10 2
20.1.1.1 1
100.1.1.1 1
192.168.1.1 1

Example 2

Input

7
8.8.8.8
8.8.4.4
1.1.1.1
1.0.0.1
8.8.8.8
77.88.8.8
77.88.8.1

Output

6
1.0.0.1 1
1.1.1.1 1
8.8.4.4 1
8.8.8.8 2
77.88.8.1 1
77.88.8.8 1

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Look at the first sample: if the strings are sorted as text, 10.0.0.10 comes before 10.0.0.9, since the character “1” is smaller than the character “9”. An address must be turned into a number.

2Hint 2

An address is the four bytes of a 32-bit number. Such numbers can be sorted with four passes of radix sort, a byte per pass, from the least significant to the most. And after sorting, equal addresses stand together.

3The idea

Turn each address into the number a·2²⁴ + b·2¹⁶ + c·2⁸ + d: the order of the numbers matches the required order of addresses. Sort the numbers; equal ones go together, and the summary is collected in one pass: count the length of each run of equal numbers and print the address back as a.b.c.d.

4Walkthrough

The reference solutions sort by radix: four stable passes, each laying the numbers out into 256 buckets by the next byte, starting with the least significant. Why from the least significant is in the article: the last pass, by the most significant byte, keeps the order set up by the previous passes among numbers with the same most significant byte. A built-in sort with a tuple key (a, b, c, d) or a number will also do: tuples are compared component by component, like the numbers, and that is the same order.

You can also avoid sorting all n addresses: first count repeats with a dictionary, and sort only the distinct addresses. When the log consists of a few busy networks, it has far fewer distinct addresses than lines.

4+Solution

5Complexity

Radix sort is four passes over n numbers and four times 256 buckets: O(n). With a built-in sort, O(n log n); at n = 100,000 the difference is not visible to the eye, but on billions of lines of network logs radix sort by bytes is a common technique.

6Common mistakes

Sorting the strings. Text order compares characters, not numbers: 100.1.1.1 comes before 20.1.1.1. The first sample is built on exactly this.
Gluing the digits. A key “all digits in a row” (10.0.0.9 → 10009) mixes addresses up: 1.0.0.10 and 10.0.0.1 give the same number 10010.
Starting radix sort from the most significant byte with full passes: after the last pass the addresses are ordered only by the least significant byte.

Algorithms behind it

SRT Algorithm Counting sort and radix sort Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n. O(n + k) and O(d·(n + b)) 2 problems