Print all subsets of a set $S$, which contains $0, 1, ... n-1$ as elements. 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 18$

Input

The input is given in the following format.


$n$


Output

Print subsets ordered by their decimal integers. Print a subset in a line 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. Seprate two adjacency elements by a space character.

Example

Input

4


Output

0:
1: 0
2: 1
3: 0 1
4: 2
5: 0 2
6: 1 2
7: 0 1 2
8: 3
9: 0 3
10: 1 3
11: 0 1 3
12: 2 3
13: 0 2 3
14: 1 2 3
15: 0 1 2 3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = int(input())
print('0:')
for b in range(1, 2 ** n):
	a = bin(b)[2:]
	a = a[::-1]
	ans = []
	for i in range(len(a)):
		if a[i] == '1':
			ans.append(i)
	ans.sort()
	print(str(b) + ':', *ans)


n = int(input())
for i in range(1 << n):
	ans = []
	_i = i
	cnt = 0
	while i:
		if i & 1:
			ans.append(cnt)
		cnt += 1
		i = i >> 1
	print(f'{_i}:', end='')
	if _i == 0:
		print()
	else:
		print('', *ans)


n = int(input())
m = 2 ** n
for i in range(m):
	temp = [0 for i in range(n)]
	j = i
	count = 0
	while j > 0:
		if j % 2 == 1:
			temp[count] = 1
		j //= 2
		count += 1
	temp2 = []
	for k in range(n):
		if temp[k] == 1:
			temp2.append(k)
	print(i, end='')
	if i != 0:
		print(':', end=' ')
		print(*temp2)
	else:
		print(':')


n = int(input())
for d in range(2 ** n):
	d_bin = '{:b}'.format(d)
	list_e = []
	for (cnt, bit) in enumerate(reversed(d_bin)):
		if bit == '1':
			list_e.append(cnt)
	if list_e:
		print(f'{d}: ', end='')
		print(*list_e)
	else:
		print(f'{d}:')


n = int(input())
nn = pow(2, n)
for i in range(nn):
	if i == 0:
		print('0:')
	else:
		bin_str = '0' + str(n) + 'b'
		bin_i = format(i, bin_str)
		ilist = list(bin_i)
		tmplist = []
		for (j, bini) in enumerate(ilist):
			if bini == '1':
				tmplist.append(n - j - 1)
		tmplist.sort()
		tmp_str = ' '.join((str(tmp) for tmp in tmplist))
		print(str(i) + ': ' + tmp_str)


n = int(input())
ans = []
for i in range(1 << n):
	ret = []
	ret.append('%d:' % i)
	for j in range(n):
		if i >> j & 1:
			ret.append(j)
	ans.append(' '.join(map(str, ret)))
print('\n'.join(ans))


bit = int(input())
print(f'0:')
for d in range(1, 2 ** bit):
	print(f'{d}: ', end='')
	print(' '.join([str(elem) for elem in range(bit) if d & 1 << elem]))


n = int(input())
for i in range(2 ** n):
	if i == 0:
		print('0:')
		continue
	else:
		print('{}: '.format(i), end='')
	l = []
	for j in range(n):
		if i & 1 << j != 0:
			l.append(j)
	print(*l)


def subset(n):
	for i in range(2 ** n):
		yield [v for v in range(n) if i & 1 << v > 0]

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


n = int(input())
print('0:')
for x in range(1, 2 ** n):
	bits = [i for (i, b) in enumerate(f'{x:b}'[::-1]) if b == '1']
	print(f"{x}: {' '.join(map(str, bits))}")


n = int(input())
U = [n - 1 - i for i in range(n)]
ind = '0' + str(n) + 'b'
for i in range(2 ** n):
	compare = [int(j) for j in format(i, ind)]
	disp = [U[j] for j in range(n) if compare[j] == 1]
	disp.reverse()
	print(i, end=':')
	if len(disp) != 0:
		print(' ' + ' '.join(map(str, disp)), end='')
	print()


n = int(input())
for i in range(1 << n):
	rs = [str(i) + ':']
	for j in range(n):
		if i & 1 << j != 0:
			rs.append(j)
	print(*rs)


n = int(input())
print('0:')
for x in range(1, 2 ** n):
	bits = [i for (i, b) in enumerate(f'{x:b}'[::-1]) if b == '1']
	print(f"{x}: {' '.join(map(str, bits))}")


n = int(input())
masks = [1 << x for x in range(n)]
for i in range(1 << n):
	sub = [idx for (idx, mask) in enumerate(masks) if i & mask != 0]
	print('{}: {}'.format(i, ' '.join(map(str, sub)))) if len(sub) != 0 else print(f'{i}:')


import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 1e-09
SIZE = 19
POW = [1] * SIZE
for i in range(1, SIZE):
	POW[i] = POW[i - 1] * 2
N = int(input())
print('0:')
index = 1
for state in range(1, POW[N]):
	print('%d:' % index, end='')
	for loop in range(N):
		if state & POW[loop] != 0:
			print(' %d' % loop, end='')
	print()
	index += 1


n = int(input())
for i in range(2 ** n):
	if i == 0:
		print('{}:'.format(i))
		continue
	else:
		print('{}: '.format(i), end='')
	l = []
	for j in range(n):
		if i & 1 << j != 0:
			l.append(j)
	print(*l)


import sys
readline = sys.stdin.readline
write = sys.stdout.write
N = int(readline())
write('0:\n')
for i in range(1, 1 << N):
	write('%d: %s\n' % (i, ' '.join((str(j) for j in range(N) if i & 1 << j))))


n = int(input())
s = []
for i in range(1 << n):
	s.append(f'{i}:')
	for j in range(n):
		if i & 1 << j:
			s.append(f' {j}')
	s.append('\n')
print(''.join(s), end='')