The Router's Guest Book

A home router keeps a guest book of the long network addresses that visited it, but different devices spell the same address differently. An address is eight groups, each a number from 0 to 65535 written in hexadecimal, separated by :. A spelling may:

• use upper or lower case letters and leading zeros in a group (0DB8, db8, 0db8);
• replace one stretch of one or more consecutive groups that are all zero by :: (so fe80::1 is fe80:0:0:0:0:0:0:1, and :: alone is all eight groups zero).

The tidy spelling of an address is: lower-case letters, no leading zeros (a zero group is written 0), and the longest stretch of two or more consecutive zero groups replaced by ::. If two stretches tie for longest, replace the leftmost; a lone zero group is never replaced.

Write busiest_address(log) that returns a tuple (distinct, top): the number of distinct addresses in the list log, and the tidy spelling of the address that appears most often. If several addresses tie, choose the one whose first appearance in log comes earliest.

Examples

Input:  log = ["2001:DB8::2:1", "fe80::1", "2001:0db8:0:0:0:0:2:1", "FE80:0:0:0:0:0:0:1", "::"]
Output: (3, "2001:db8::2:1")
Explanation: two visits each for 2001:db8::2:1 and fe80::1; the first one was seen first.

Input:  log = ["0:0:1:0:0:2:0:0", "0000::1:0:0:2:0:0"]
Output: (1, "::1:0:0:2:0:0")

Input:  log = ["1:2:3:4:5:6:7::", "1:0:0:0:1:0:0:0"]
Output: (2, "1:2:3:4:5:6:7:0")

Constraints

• 1 <= len(log) <= 10**5; every entry is a valid spelling as described
• groups have 1 to 4 hexadecimal digits; :: appears at most once in an entry

Goals

• Expand a shortened address into its eight groups
• Produce the one agreed short spelling of an address
• Count by canonical key and break frequency ties by first appearance