Background

(Friendly note: IPv6 basics have appeared many times in the NOIP preliminary contest.) Internet Protocol, the protocol of the Internet, is what we usually call IP. What we most often refer to is its fourth version, IPv4, which was released by IETF in 1981. Its address length is $32$ binary bits, so there are $2^{32}$ IP addresses available, about $4.3$ billion. At that time, no one expected that even such a large IPv4 address space would one day run out.

In the 21st century, the rapid development of the Internet has brought us a convenient life. Today, the world’s population has exceeded $7$ billion. Computers and various networked devices have entered thousands of households, no longer just the tools of scientists in the 1980s. This has created a conflict between the growing number of networked devices and the limited IPv4 address space. Although Network Address Translation (NAT) can be used to share IP addresses and temporarily alleviate the exhaustion problem, it is obviously not a long-term solution.

IETF was forward-looking and released the IPv6 protocol as early as 1998. Starting with Microsoft’s Windows Vista in 2006, it became a default-installed network protocol. As the successor to IPv4, its address length is $128$ binary bits, that is, $2^{128}$ IP addresses are available. However, faced with such lengthy addresses, a network engineer named Xiaoming, who has a poor memory, encountered many difficulties when configuring routing tables. He has come to you, hoping you can write a program to compress IPv6 addresses according to the standard IPv6 formatting rules.

Problem Description

[IPv6 Format]

In binary, an IPv6 address is $128$ bits long. It is divided into groups of $16$ bits, separated by colons “:”, making $8$ groups in total. Each group is written as a 4-digit hexadecimal number.

For example, 2001:0db8:0000:0000:0123:4567:89ab:cdef is a valid IPv6 address.

IPv6 addresses can be compressed under certain conditions:

1. Leading zeros in each group can be omitted.

For example, the address above can be compressed to 2001:db8:0:0:123:4567:89ab:cdef.

2. A double colon :: can represent one or more consecutive groups of 0, but it can only appear once.

For example, the address above can be compressed to 2001:db8::123:4567:89ab:cdef.

Please help the forgetful network engineer Xiaoming solve his problem.

[Supplementary Rules]

1. The input is a fully expanded IPv6 address. It is guaranteed that the input IPv6 address contains no double colon, and that any omitted zeros in each group have been filled.

2. Since :: can be used only once, compress the longest run of all-zero groups.

For example, 2001:0db8:0000:0000:1:0000:0000:0000 is compressed to 2001:db8:0:0:1::, not 2001:db8::1:0:0:0.

3. Since :: can be used only once, if there are multiple runs of all-zero groups with the same maximum length, compress the earliest one.

For example, 2001:0db8:0000:0000:ffff:0000:0000:1 is compressed to 2001:db8::ffff:0:0:1, not 2001:db8:0:0:ffff::1.

4. The input IPv6 address may not be compressible. In that case, output it as-is.

Tip: The compression rules shown in this problem match the default IPv6 display style on macOS (Darwin), whereas Windows and Linux do not use :: when there is only a single all-zero group. However, IPv6 addresses compressed in this way can still be correctly recognized by Windows and Linux.

For example, 2001:0db8:ffff:0000:0123:4567:89ab:cdef is compressed by Darwin as 2001:db8:ffff::123:4567:89ab:cdef, while Linux and Windows compress it as 2001:db8:ffff:0:123:4567:89ab:cdef.

Input Format

A string of $39$ characters representing a fully expanded IPv6 address.

Output Format

A string representing the compressed IPv6 address.

2406:0840:f990:0000:0000:0000:0000:0001

2406:840:f990::1

2a13:1801:018a:00cf:0100:0000:0000:0000

2a13:1801:18a:cf:100::

2001:4860:4860:0000:0000:0000:0000:8888

2001:4860:4860::8888

2001:0db8:0000:0000:0000:0000:0000:0001

2001:db8::1

0000:0000:0000:0000:0000:0000:0000:0000

::

0000:0000:0000:0000:0000:0000:0000:0001

::1

2001:0db8:ffff:0000:0123:4567:89ab:cdef

2001:db8:ffff::123:4567:89ab:cdef

1234:5678:9abc:def0:1234:5678:9abc:def0

1234:5678:9abc:def0:1234:5678:9abc:def0

0001:0000:0000:0000:0000:0000:0000:0001

1::1

0000:0000:0000:0000:0000:0000:0001:0002

::1:2

Hint

Translated by ChatGPT 5