Route Aggregator

The story

A branch office announces its networks to head office one /24 at a time. After a few years of growth the routing table has hundreds of entries, many of them redundant: some networks are swallowed by bigger ones, some are listed twice, and many sit right next to each other and could be announced as one bigger block. Smaller tables mean faster lookups and less memory, so routers summarise (aggregate) routes whenever the addresses allow it.

The task

Given a list of IPv4 networks in CIDR notation, print the smallest possible list of CIDR blocks that covers exactly the same set of addresses: no address may be added, none may be lost.

Input:

• the first line is n (1 to 2000), the number of networks;
• then n lines a.b.c.d/p. Every line is a proper network: its host bits are zero (10.1.2.0/24, never 10.1.2.77/24). Duplicates, overlaps, and any order are possible.

Output: the blocks, one per line as a.b.c.d/p, sorted by network address (lowest first).

Merging only works when the blocks are adjacent and aligned: two /24 networks join into a /23 only if the first one starts on an even third octet. For example 172.16.1.0/24 + 172.16.2.0/24 cannot become one block, because 172.16.1.0/23 would also contain 172.16.0.0/24, which was not in the list.

Examples

4
192.168.0.0/24
192.168.1.0/24
192.168.2.0/24
192.168.3.0/24

Output:

192.168.0.0/22

The four networks are consecutive and the first is aligned on a multiple of four, so one /22 covers them exactly.

3
172.16.1.0/24
172.16.2.0/24
172.16.0.0/24

Output:

172.16.0.0/23
172.16.2.0/24

Together the three networks span 172.16.0.0 to 172.16.2.255. The best you can do is a /23 (0 and 1) and a /24 (2).

4
192.168.0.0/24
192.168.1.0/24
192.168.2.0/24
192.168.3.0/24