An IPv6-address is a 128-bit number. For convenience, this number is recorded in blocks of 16 bits in hexadecimal record, the blocks are separated by colons — 8 blocks in total, each block has four hexadecimal digits. Here is an example of the correct record of a IPv6 address: "0124:5678:90ab:cdef:0124:5678:90ab:cdef". We'll call such format of recording an IPv6-address full.

Besides the full record of an IPv6 address there is a short record format. The record of an IPv6 address can be shortened by removing one or more leading zeroes at the beginning of each block. However, each block should contain at least one digit in the short format. For example, the leading zeroes can be removed like that: "a56f:00d3:0000:0124:0001:f19a:1000:0000"  →  "a56f:d3:0:0124:01:f19a:1000:00". There are more ways to shorten zeroes in this IPv6 address.

Some IPv6 addresses contain long sequences of zeroes. Continuous sequences of 16-bit zero blocks can be shortened to "::". A sequence can consist of one or several consecutive blocks, with all 16 bits equal to 0. 

You can see examples of zero block shortenings below:

  "a56f:00d3:0000:0124:0001:0000:0000:0000"  →  "a56f:00d3:0000:0124:0001::";  "a56f:0000:0000:0124:0001:0000:1234:0ff0"  →  "a56f::0124:0001:0000:1234:0ff0";  "a56f:0000:0000:0000:0001:0000:1234:0ff0"  →  "a56f:0000::0000:0001:0000:1234:0ff0";  "a56f:00d3:0000:0124:0001:0000:0000:0000"  →  "a56f:00d3:0000:0124:0001::0000";  "0000:0000:0000:0000:0000:0000:0000:0000"  →  "::". 

It is not allowed to shorten zero blocks in the address more than once. This means that the short record can't contain the sequence of characters "::" more than once. Otherwise, it will sometimes be impossible to determine the number of zero blocks, each represented by a double colon.

The format of the record of the IPv6 address after removing the leading zeroes and shortening the zero blocks is called short.

You've got several short records of IPv6 addresses. Restore their full record.


-----Input-----

The first line contains a single integer n — the number of records to restore (1 ≤ n ≤ 100).

Each of the following n lines contains a string — the short IPv6 addresses. Each string only consists of string characters "0123456789abcdef:".

It is guaranteed that each short address is obtained by the way that is described in the statement from some full IPv6 address.


-----Output-----

For each short IPv6 address from the input print its full record on a separate line. Print the full records for the short IPv6 addresses in the order, in which the short records follow in the input.


-----Examples-----
Input
6
a56f:d3:0:0124:01:f19a:1000:00
a56f:00d3:0000:0124:0001::
a56f::0124:0001:0000:1234:0ff0
a56f:0000::0000:0001:0000:1234:0ff0
::
0ea::4d:f4:6:0

Output
a56f:00d3:0000:0124:0001:f19a:1000:0000
a56f:00d3:0000:0124:0001:0000:0000:0000
a56f:0000:0000:0124:0001:0000:1234:0ff0
a56f:0000:0000:0000:0001:0000:1234:0ff0
0000:0000:0000:0000:0000:0000:0000:0000
00ea:0000:0000:0000:004d:00f4:0006:0000

Source: codeforces | Difficulty: MEDIUM
Tags: String algorithms

Implementation


Solutions:
def s():
	n = int(input())

	def st(x):
		if x[0] == ':':
			x = x[1:]
		if x[-1] == ':':
			x = x[:-1]
		return x
	for _ in range(n):
		a = st(input()).split(':')
		for i in range(len(a)):
			if len(a[i]) == 0:
				a[i] = '0000:' * (8 - len(a)) + '0000'
			elif len(a[i]) < 4:
				a[i] = '0' * (4 - len(a[i])) + a[i]
		print(*a, sep=':')
s()


t = int(input())
for h in range(t):
	s = input().split(':')
	l = len(s)
	if l == 8:
		p = ''
		for i in range(8):
			k = len(s[i])
			s[i] = '0' * (4 - k) + s[i]
			p = p + s[i]
			if i != 7:
				p = p + ':'
	elif s[0] == '':
		p = ''
		m = 10 - l
		for i in range(m):
			p += '0000:'
		for i in range(2, l):
			k = len(s[i])
			s[i] = '0' * (4 - k) + s[i]
			p = p + s[i]
			if i != l - 1:
				p = p + ':'
	elif s[-1] == '':
		m = 10 - l
		p = ''
		for i in range(l - 2):
			k = len(s[i])
			s[i] = '0' * (4 - k) + s[i] + ':'
			p = p + s[i]
		for i in range(m):
			if i != m - 1:
				p += '0000:'
			else:
				p += '0000'
	else:
		p = ''
		m = 9 - l
		for i in range(l):
			k = len(s[i])
			if k == 0:
				for i in range(m):
					p += '0000:'
			else:
				s[i] = '0' * (4 - k) + s[i]
				p = p + s[i]
				if i != l - 1:
					p = p + ':'
	print(p)


import re
n = int(input())
for i in range(n):
	s = input().strip()
	group_count = s.count(':') + 1
	s = re.sub('::', ':' + (9 - group_count) * '0000:', s)
	groups = s.split(':')
	for (i, group) in enumerate(groups):
		if len(group) < 4:
			groups[i] = (4 - len(group)) * '0' + group
	print(':'.join(groups))


import sys

def solve():
	n = int(input())
	for test in range(n):
		line = input().split(':')
		i = 0
		while i < len(line):
			if i > 0 and line[i] == '' and (line[i - 1] == ''):
				line.pop(i)
				i -= 1
			i += 1
		for (i, string) in enumerate(line):
			if string == '':
				line[i] = modify(string, want=32 - 4 * (len(line) - 1))
			else:
				line[i] = modify(string)
		tempstr = ''.join(line)
		chunked = [tempstr[i:i + 4] for i in range(0, 32, 4)]
		print(':'.join(chunked))

def modify(string, want=4):
	while len(string) < want:
		string = '0' + string
	return string
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


for i in range(int(input())):
	t = input().split(':')
	if t[-1] == '':
		t.pop()
	elif t[0] == '':
		t.pop(0)
	if '' in t:
		t[t.index('')] = ('0000:' * (9 - len(t)))[:-1]
	print(':'.join(('0' * (4 - len(i)) + i for i in t)))


count = input()
for i in range(int(count)):
	n = input()
	ip = n.split(':')
	begin = 0
	end = 0
	if ip[0] == '' and ip[1] == '' and (len(ip) > 8):
		begin = 1
	if ip[len(ip) - 2] == '' and ip[len(ip) - 1] == '' and (len(ip) > 8):
		end = 1
	while len(ip) < 8:
		index = ip.index('')
		ip = ip[:index] + [''] + ip[index:]
	for item in ip:
		i = item
		while len(i) < 4:
			i = '0' + i
		ip[ip.index(item)] = i
	if end == 1:
		ip = ip[:len(ip) - 1]
	if begin == 1:
		ip = ip[1:]
	print(':'.join(ip))


def nts(x):
	x = str(hex(x))[2:]
	return '0' * (4 - len(x)) + x

def ch(s):
	if s == '':
		return ''
	a = [e for e in s.split(':')]
	for i in range(len(a)):
		a[i] = int(a[i], 16)
	return ':'.join((nts(e) for e in a))

def cnt(s):
	if s == '':
		return 0
	return sum([int(i == ':') for i in s]) + 1

def get(n):
	return ':'.join(['0000' for i in range(n)])
T = int(input())
for cas in range(T):
	s = input()
	(p, n) = (-1, len(s))
	for i in range(n - 1):
		if s[i] == s[i + 1] == ':':
			p = i
			break
	if p == -1:
		s = ch(s)
	else:
		s1 = ch(s[:i])
		s3 = ch(s[i + 2:])
		(a, b) = (cnt(s1), cnt(s3))
		s2 = get(8 - a - b)
		s = s1 + ('' if s2 == '' or s1 == '' else ':') + s2 + ('' if s3 == '' or (s1 == '' and s2 == '') else ':') + s3
	print(s)


class CodeforcesTask250BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.shorts = []

	def read_input(self):
		self.n = int(input())
		for x in range(self.n):
			self.shorts.append(input())

	def process_task(self):
		results = []
		for short in self.shorts:
			if '::' in short:
				if short[-2:] != '::' and short[:2] != '::':
					valid_blocks = short.count(':')
				elif short[-2:] == '::' and short[:2] == '::':
					valid_blocks = 0
				else:
					valid_blocks = short.count(':') - 1
				if valid_blocks:
					full = short.replace('::', ':' + ':'.join(['0000' for x in range(8 - valid_blocks)]) + ':')
				else:
					full = '0000:' * 8
				if full[-1] == ':':
					full = full[:-1]
				if full[0] == ':':
					full = full[1:]
				parts = full.split(':')
				for x in range(len(parts)):
					parts[x] = '0' * (4 - len(parts[x])) + parts[x]
				results.append(':'.join(parts))
			else:
				parts = short.split(':')
				for x in range(len(parts)):
					parts[x] = '0' * (4 - len(parts[x])) + parts[x]
				results.append(':'.join(parts))
		self.result = '\n'.join(results)

	def get_result(self):
		return self.result
Solution = CodeforcesTask250BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


def f(s):
	res = []
	sp = s.split(':')
	if not sp[0]:
		sp[0] = '0'
	if not sp[-1]:
		sp[-1] = '0'
	for b in sp:
		if b:
			res.append('{:0>4}'.format(b))
		if not b:
			res.extend(('0000' for i in range(8 - len(sp) + 1)))
	return ':'.join(res)
t = int(input())
for i in range(t):
	ip = input()
	print(f(ip))


for kk in range(int(input())):
	str = input()
	print(':'.join((i.zfill(4) for i in str.replace('::', ':' * (9 - str.count(':'))).split(':'))))


def zr(s):
	tmp = ':0000'
	if s == '::':
		return tmp[1:] + 7 * tmp
	ind = s.find('::')
	if ind < 0:
		return s
	(h, k) = (1, 0)
	if ind == 0 or ind == len(s) - 2:
		if ind > 0:
			h = 2
		else:
			k = 1
		ddc = 9 - s.count(':')
	else:
		ddc = 8 - s.count(':')
	return (s[:ind] + ddc * tmp + s[ind + h:])[k:]

def t4(s):
	ls = len(s)
	if ls == 4:
		return s
	return (4 - ls) * '0' + s

def spu(s):
	ns = ''
	fc = 0
	sc = s.find(':')
	while sc > 0:
		ns += t4(s[fc:sc]) + ':'
		fc = sc + 1
		sc = s.find(':', fc)
	ns += t4(s[fc:])
	return ns
n = int(input())
v = []
for c in range(n):
	v.append(spu(zr(input())))
for c in v:
	print(c)


n = int(input())
for i in range(n):
	ans = ''
	k = ''
	s = input().split(':')
	c = m = 0
	for g in range(len(s)):
		if s[g] != '':
			c += 1
	if c == 8:
		for j in range(c):
			s[j] = (4 - len(s[j])) * '0' + s[j]
			ans += s[j] + ':'
	else:
		k = (8 - c) * '0000:'
		for j in range(len(s)):
			if s[j] == '':
				ans += k
				k = ''
				m = 1
			else:
				s[j] = (4 - len(s[j])) * '0' + s[j]
				ans += s[j] + ':'
	ans += k
	ans = ans[:-1]
	print(ans)


n = int(input())
for i in range(n):
	s = input().split(':')
	if s[0] == '':
		s.pop(0)
	if s[-1] == '':
		s.pop(-1)
	rq = 8 - len(s) + 1
	t = []
	for x in s:
		if x == '':
			for j in range(rq):
				t += ['0000']
		else:
			t += [x]
	u = ''
	for x in t:
		u += '0' * (4 - len(x)) + x + ':'
	print(u[:-1])


n = int(input())
for i in range(n):
	r = input().split(':')
	s = ':'.join((x.zfill(4) if x else x for x in r))
	while len(s) < 39:
		x = s.index('::')
		s = s[:x + 1] + '0000:' + s[x + 1:]
	if '::' in s:
		x = s.index('::')
		s = s[:x + 1] + s[x + 2:]
	print(s.strip(':'))


n = int(input())
short_ips = []
for i in range(n):
	short_ips.append(input())
answers = [[] for x in range(n)]
ans_id = -1
for ip in short_ips:
	ans_id += 1
	visited = False
	segments = ip.split(':')
	for segment in segments:
		if len(segment) == 0:
			if visited:
				answers[ans_id].append('0' * 4)
				continue
			visited = True
			missing = 8 - len(segments)
			for i in range(missing + 1):
				answers[ans_id].append('0' * 4)
		elif len(segment) == 4:
			answers[ans_id].append(segment)
		else:
			leading = 4 - len(segment)
			answers[ans_id].append('0' * leading + segment)
for restored in answers:
	print(':'.join(restored))


n = int(input())
dfg = []
for i in range(n):
	IP = input().split(':')
	if IP[0] == '':
		IP.pop(0)
	if IP[-1] == '':
		IP.pop(-1)
	addlen = 8 - len(IP)
	for i in range(len(IP)):
		if IP[i] == '':
			for j in range(addlen):
				IP.insert(i, '')
			break
	for i in range(8):
		IP[i] = '0' * (4 - len(IP[i])) + IP[i]
	b = []
	for i in range(8):
		b.append(IP[i] + ':' if i != 7 else IP[i])
	dfg.append(b)
for i in range(n):
	for j in range(8):
		print(dfg[i][j], end='')
	print()


n = int(input())
list = []
for i in range(n):
	str = input()
	list = str.split(':')
	if str.count('::') > 0:
		t = list.count('')
		if t == 3:
			t = '0000:' * 8
			print(t[:len(t) - 1])
		elif t == 2:
			if str[0:2] == '::':
				str = str.replace('::', '0000:' * (10 - len(list)))
				res = ''
				list2 = str.split(':')
				for i in range(len(list2)):
					res += '0' * (4 - len(list2[i])) + list2[i] + ':'
				print(res[0:len(res) - 1])
			else:
				str = str.replace('::', ':0000' * (10 - len(list)))
				res = ''
				list2 = str.split(':')
				for i in range(len(list2)):
					res += '0' * (4 - len(list2[i])) + list2[i] + ':'
				print(res[0:len(res) - 1])
		else:
			str = str.replace('::', ':0000:' * (9 - len(list)))
			str = str.replace('::', ':')
			res = ''
			list2 = str.split(':')
			for i in range(len(list2)):
				res += '0' * (4 - len(list2[i])) + list2[i] + ':'
			print(res[0:len(res) - 1])
	else:
		res = ''
		for i in range(len(list)):
			res += '0' * (4 - len(list[i])) + list[i] + ':'
		print(res[0:len(res) - 1])


def solve(ip):
	ch = ip.split(':')
	n = len(ch)
	if ch[n - 1] == '' and n - 2 >= 0 and (ch[n - 2] == ''):
		ch.pop(n - 1)
	if ch[0] == '' and n > 1 and (ch[1] == ''):
		ch.pop(0)
	extra = 8 - len(ch)
	ans = []
	for i in range(len(ch)):
		if ch[i] != '':
			while len(ch[i]) < 4:
				ch[i] = '0' + ch[i]
			ans.append(ch[i])
		else:
			ans.append('0000')
			while extra > 0:
				ans.append('0000')
				extra -= 1
	ret = ''
	for i in range(len(ans)):
		ret += ans[i]
		if i != len(ans) - 1:
			ret += ':'
	return ret
n = int(input())
for i in range(n):
	s = input()
	print(solve(s))


def index(lena):
	if lena == 8:
		return 4
	elif lena == 7:
		return 9
	elif lena == 6:
		return 14
	elif lena == 5:
		return 19
	elif lena == 4:
		return 24
	elif lena == 3:
		return 29
	elif lena == 2:
		return 34
	elif lena == 1:
		return 39
s = int(input())
ip = []
for a in range(s):
	q = input().split(':')
	q1 = []
	c = 0
	for a in q:
		if a == '' and c == 0:
			q1.append(a)
			c = 1
		elif a == '' and c == 1:
			pass
		else:
			q1.append(a)
	ip.append(q1)
for a in ip:
	s = []
	lena = len(a)
	z = '0000:0000:0000:0000:0000:0000:0000:0000'
	for i in range(lena):
		if a[i] == '':
			s.append(z[:index(lena)])
		else:
			q = '{0:0>4}'.format(a[i])
			s.append(q)
	res = ':'.join(s)
	print(res)


y = 0
n = eval(input())
while y < n:
	ans = ''
	l = list(map(str, input().split(':')))
	i = 0
	c = 0
	while i < len(l):
		if l[i] != '':
			c += 1
		i += 1
	c = 8 - c
	i = 0
	while i < len(l):
		if l[i] == '':
			ans += c * '0000:'
			c = 0
		elif len(l[i]) < 4:
			ans += str((4 - len(l[i])) * '0') + str(l[i])
			ans += ':'
		else:
			ans += l[i]
			ans += ':'
		i += 1
	print(ans[0:39])
	y += 1


zero = str('0000')
for _ in range(int(input())):
	m = 0
	k = input()
	s = list(map(str, k.split(':')))
	if k[len(k) - 1] == ':':
		s.pop(len(s) - 1)
	if k[0] == ':':
		s.pop(0)
	for i in range(len(s)):
		if len(s[i]) != 4 and s[i] != '':
			s[i] = zero[0:4 - len(s[i])] + s[i]
		elif s[i] == '':
			m += 1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '' and m == 1:
			s[i] = zero
			while len(s) < 8:
				s.insert(i, zero)
		elif s[i] == '':
			s[i] = zero
			m -= 1
	print(':'.join(s))


for i in range(int(input())):
	t = input().split(':')
	if '' in t:
		j = t.index('')
		t[j:j + 1] = [''] * (9 - len(t))
	print(':'.join((j.rjust(4, '0') for j in t)))


for _ in range(int(input())):
	s = input()
	print(':'.join((i.zfill(4) for i in s.replace('::', ':' * (9 - s.count(':'))).split(':'))))


for _ in range(int(input())):
	D = input()
	print(':'.join((d.zfill(4) for d in D.replace('::', ':' * (9 - D.count(':'))).split(':'))))


def restora(lin):
	lin = lin.split(':')
	ans = []
	falt = 8
	for w in lin:
		if w != '':
			falt -= 1
	for w in lin:
		if w == '':
			while falt > 0:
				ans.append('0000')
				falt -= 1
			continue
		while len(w) < 4:
			w = '0' + w
		ans.append(w)
	return ':'.join(ans)

def main():
	n = int(input())
	for i in range(n):
		print(restora(input()))
main()


n = int(input())
ips = [input() for j in range(n)]
for ip in ips:
	if ip.find('::') != -1:
		ip = ip.replace('::', ':' * (9 - ip.count(':')))
	comps = ip.split(':')
	for i in range(len(comps)):
		comps[i] = '0' * (4 - len(comps[i])) + comps[i]
	print(':'.join(comps))


for i in range(int(input())):
	ipv6 = input().split(':')
	ipv6 = [(4 - len(i)) * '0' + i if i != '' else '' for i in ipv6]
	if ipv6[-1] == '':
		ipv6[-1] = '0000'
	if ipv6[0] == '':
		ipv6[0] = '0000'
	if '' in ipv6:
		string = '0000:' * (8 - len(ipv6) + 1)
		ipv6[ipv6.index('')] = string[:-1]
	if '' in ipv6:
		ipv6.remove('')
	print(':'.join(ipv6))


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def do(s):
	r = []
	for i in s.split(':'):
		r.append('0' * (4 - len(i)) + i)
	return ':'.join(r)
n = mint()
for i in range(n):
	s = minp()
	m = s.find('::')
	if m != -1:
		print(do(s[:m]) + ':0000' * (8 - s.count(':')) + ':' + do(s[m + 2:]))
	else:
		print(do(s))


n = int(input())
adrs = [input().split(':') for i in range(n)]
res = []
for ad in adrs:
	new_ad = ''
	ind = 0
	for s in ad:
		if s:
			new_ad += '0' * (4 - len(s)) + s + ' '
		elif s == '::':
			res.append('0000 ' * 8)
			break
		elif not s and ind == 0:
			new_ad += '0000 ' * (8 - len(ad) + ad.count(''))
			ind = 1
	res.append(new_ad)
for x in res:
	print(x.replace(' ', ':')[:39])


t = int(input())
for _ in range(t):
	s = input()
	if '::' not in s:
		arr = s.split(':')
		temp = ''
		for x in arr:
			temp += (4 - len(x)) * '0' + x + ':'
		print(temp[:-1])
	else:
		arr = s.split(':')
		val = 0
		for x in arr:
			if x != '':
				val += 1
		idx = arr.index('')
		need = 8 - val
		temp = ''
		fl = 0
		for x in arr:
			if x != '':
				temp += (4 - len(x)) * '0' + x + ':'
			elif fl == 0:
				temp += '0000:' * need
				fl = 1
		print(temp[:-1])


for _ in range(int(input())):
	s = input().split(':')
	tmp = 8 - sum((i != '' for i in s))
	if tmp > 0:
		for i in range(len(s)):
			if s[i] == '':
				s[i] = '0000' + (tmp - 1) * ':0000'
				break
	l = []
	for i in s:
		if i != '':
			l.append('0' * (4 - len(i)) + i)
	print(':'.join(l))


for _ in range(int(input())):
	D = input().split(':')
	if not D[0]:
		D = D[1:]
	if not D[-1]:
		D.pop()
	n = len(D)
	for i in range(n):
		D[i] = D[i].zfill(4) if D[i] else '0000:' * (8 - n) + '0000'
	print(':'.join(D))