You are given a set $T$, which is a subset of $S$. The set $S$ consists of $0, 1, ... n-1$. Print all subsets of $T$. Note that we represent $0, 1, ... n-1$ as 00...0001, 00...0010, 00...0100, ..., 10...0000 in binary respectively and the integer representation of a subset is calculated by bitwise OR of existing elements.

Constraints

* $1 \leq n \leq 28$
* $0 \leq k \leq 18$
* $k \leq n$
* $0 \leq b_i < n$

Input

The input is given in the following format.


$n$
$k \; b_0 \; b_1 \; ... \; b_{k-1}$


$k$ is the number of elements in $T$, and $b_i$ represents elements in $T$.

Output

Print the subsets ordered by their decimal integers. Print a subset in the following format.


$d$: $e_0$ $e_1$ ...


Print ':' after the integer value $d$, then print elements $e_i$ in the subset in ascending order. Separate two adjacency elements by a space character.

Example

Input

4
2 0 2


Output

0:
1: 0
4: 2
5: 0 2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = int(input())
ind = '0' + str(n) + 'b'
t = list(map(int, input().split()))
k = t[0]
t.pop(0)
T = t
T.reverse()
ind = '0' + str(k) + 'b'
for i in range(2 ** k):
	compare = [int(j) for j in format(i, ind)]
	disp = [T[j] for j in range(k) if compare[j] == 1]
	disp.reverse()
	if len(disp) == 0:
		print('0:')
	else:
		calc = [2 ** j for j in disp]
		print(str(sum(calc)) + ':', end='')
		print(' ' + ' '.join(map(str, disp)))


import itertools
n = int(input())
(k, *list_b) = map(int, input().split())
list_d = []
for k in range(len(list_b) + 1):
	for tuple_e in itertools.combinations(list_b, k):
		d = 0
		for bit in tuple_e:
			d += 2 ** bit
		list_d.append((d, tuple_e))
for (d, tuple_e) in sorted(list_d):
	if tuple_e:
		print(f'{d}: ', end='')
		print(*tuple_e)
	else:
		print(f'{d}:')


from itertools import combinations
_ = input()
(k, *B) = map(int, input().split())
for (v, combi) in sorted([(sum([1 << cc for cc in c]), ' '.join(map(str, c))) for i in range(k + 1) for c in combinations(B, i)]):
	print(f'{v}: {combi}' if v else '0:')


n = int(input())
(k, *b) = map(int, input().split())
t = sum((1 << i for i in b))
for i in range(1 << k):
	tmp = 0
	rs = []
	for j in range(k):
		if i & 1 << j != 0:
			tmp |= 1 << b[j]
			rs.append(b[j])
	print(str(tmp) + ':', *rs)


from itertools import combinations
bit = int(input())
(k, *E) = map(lambda x: int(x), input().split())
for (d, ans) in sorted([(sum([1 << cc for cc in c]), ' '.join(map(str, c))) for i in range(k + 1) for c in combinations(E, i)]):
	if d:
		print(f'{d}: {ans}')
	else:
		print(f'0:')


from itertools import combinations
_ = input()
(k, *B) = map(int, input().split())
for (v, combi) in sorted([(sum([1 << cc for cc in c]), ' '.join(map(str, c))) for i in range(k + 1) for c in combinations(B, i)]):
	print(f'{v}: {combi}' if v else '0:')


from functools import lru_cache

def subset(n, mask):

	@lru_cache(maxsize=None)
	def _subset(i):
		if i < 0:
			return [(0, [])]
		m = mask[i]
		return _subset(i - 1) + [(v + (1 << m), vs + [m]) for (v, vs) in _subset(i - 1)]
	return _subset(len(mask) - 1)

def run():
	n = int(input())
	mask = tuple([int(i) for i in input().split()][1:])
	for (i, vs) in subset(n, mask):
		print('{}:{}'.format(i, ''.join([' {}'.format(v) for v in vs])))
run()


from itertools import combinations
n = int(input())
(k, *b_arr) = map(int, input().split())

def calc_int(arr):
	ret = 0
	for i in arr:
		ret += 1 << i
	return ret
subsets = []
for i in range(len(b_arr) + 1):
	i_subsets = []
	for sub in combinations(b_arr, i):
		i_subsets.append((calc_int(sub), sub))
	subsets.extend(i_subsets)
subsets.sort()
for sub in subsets:
	print('{}: {}'.format(sub[0], ' '.join(map(str, sub[1])))) if len(sub[1]) != 0 else print(f'{sub[0]}:')


import itertools
n = int(input())
tlist = list(map(int, input().split()))
k = tlist[0]
tlist.remove(tlist[0])
if k == 0:
	print('0:')
	exit()
combslist = []
for i in range(1, k + 1):
	combs = list(itertools.combinations(tlist, i))
	for comb in combs:
		combslist.append(comb)
sumlist = []
for comb in combslist:
	sum = 0
	for c in comb:
		sum += pow(2, c)
	sumlist.append(sum)
z = zip(sumlist, combslist)
z = sorted(z)
(sumlist, combslist) = zip(*z)
print('0:')
for (sum, comb) in zip(sumlist, combslist):
	c_str = ' '.join((str(c) for c in comb))
	print(str(sum) + ': ' + c_str)


n = int(input())
(k, *l) = [int(x) for x in input().split()]
mbit = []
for i in l:
	mbit.append(i)
print('0:')
for i in range(1, 1 << len(mbit)):
	num = 0
	p = []
	for j in range(len(mbit)):
		if i & 1 << j != 0:
			num |= 1 << mbit[j]
			p.append(mbit[j])
	print('{}: '.format(num), end='')
	print(*p)


from itertools import combinations
n = int(input())
b = list(map(int, input().split()))
r = b[0]
b = b[1:]
print('0:')
ans = []
for i in range(1, r + 1):
	for j in combinations(b, i):
		comb = list(j)
		comb.reverse()
		s = 0
		for h in comb:
			s += 2 ** h
		ans.append([s, list(j)])
ans.sort()
for (i, j) in ans:
	print(str(i) + ':', *j)


import sys
readline = sys.stdin.readline
write = sys.stdout.write
N = int(readline())
(k, *B) = map(int, readline().split())
M = sum((1 << b for b in B))
R = []
v = -1 & M
while v:
	R.append(v)
	v = v - 1 & M
R.sort()
write('0:\n')
for i in R:
	write('%d: %s\n' % (i, ' '.join((str(j) for j in range(N) if i & 1 << j))))