Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:

  * for all x <image> the following inequality holds l ≤ x ≤ r; 
  * 1 ≤ |S| ≤ k; 
  * lets denote the i-th element of the set S as si; value <image> must be as small as possible. 



Help Victor find the described set.

Input

The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).

Output

Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.

If there are multiple optimal sets, you can print any of them.

Examples

Input

8 15 3


Output

1
2
10 11


Input

8 30 7


Output

0
5
14 9 28 11 16

Note

Operation <image> represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

Source: codeforces | Difficulty: HARD
Tags: Complete search

Mathematics

Constructive algorithms


Solutions:
import random
(l, r, k) = map(int, input().split(' '))
if k == 1:
	print(l)
	print(1)
	print(l)
	quit()
if k == 2:
	if r == l + 1:
		a = l
		b = l ^ r
		if a <= b:
			print(a)
			print(1)
			print(l)
			quit()
		else:
			print(b)
			print(2)
			print(l, l + 1)
			quit()
	for i in range(l, r + 1):
		if i % 2 == 0:
			print(1)
			print(2)
			print(i, i + 1)
			quit()
if k == 3:
	if abs(l - r) <= 10000:
		for i in range(l, r + 1):
			for j in range(i + 1, r + 1):
				if l <= i ^ j <= r:
					print(0)
					print(3)
					print(i, j, i ^ j)
					quit()
		print(1)
		print(2)
		if l % 2 == 0:
			print(l, l + 1)
			quit()
		else:
			print(l + 1, l + 2)
			quit()
	if abs(l - r) <= 1000000:
		for x in range(l, r + 1):
			if l <= x ^ x + 1 <= r:
				print(0)
				print(3)
				print(x, x + 1, x ^ x + 1)
				quit()
	for i in range(5):
		if i == 1:
			x = l
			y = l + 1
		elif i == 2:
			x = r
			y = r - 1
		else:
			x = random.randint(l, r)
			y = random.randint(l, r)
		if x == y:
			continue
		if l <= x ^ y <= r:
			print(0)
			print(3)
			print(x, y, x ^ y)
			quit()
	print(1)
	print(2)
	if l % 2 == 0:
		print(l, l + 1)
		quit()
	else:
		print(l + 1, l + 2)
		quit()
if k == 4:
	if r == l + 3:
		if l % 2 == 0:
			print(0)
			print(4)
			print(l, l + 1, l + 2, l + 3)
			quit()
		a = l
		b = l + 1
		c = l + 2
		d = l + 3
		if a ^ b ^ c == 0:
			print(0)
			print(3)
			print(a, b, c)
			quit()
		if a ^ b ^ d == 0:
			print(0)
			print(3)
			print(a, b, d)
			quit()
		if a ^ c ^ d == 0:
			print(0)
			print(3)
			print(a, c, d)
			quit()
		if b ^ c ^ d == 0:
			print(0)
			print(3)
			print(b, c, d)
			quit()
		if a ^ b == 1:
			print(1)
			print(2)
			print(a, b)
			quit()
		print(1)
		print(2)
		print(b, c)
		quit()
	for i in range(l, r + 1):
		if i % 2 == 0:
			print(0)
			print(4)
			print(i, i + 1, i + 2, i + 3)
			quit()
if k >= 5:
	for i in range(l, r + 1):
		if i % 2 == 0:
			print(0)
			print(4)
			print(i, i + 1, i + 2, i + 3)
			quit()


def main():
	from itertools import combinations
	from functools import reduce
	from random import randrange
	(l, r, k) = [int(i) for i in input().split()]
	if r - l < 4:
		f = float('inf')
		result = None
		numbers = list(range(l, r + 1))
		for mask in range(1, 1 << r - l + 1):
			tmp = [numbers[i] for i in range(r - l + 1) if mask & 1 << i]
			if len(tmp) <= k and reduce(lambda x, y: x ^ y, tmp) < f:
				f = reduce(lambda x, y: x ^ y, tmp)
				result = tmp
	elif k >= 4:
		a = l + l % 2
		f = 0
		result = [a, a + 1, a + 2, a + 3]
	elif k == 1:
		f = l
		result = [l]
	elif k == 2:
		a = l + l % 2
		f = 1
		result = [a, a + 1]
	elif k == 3:
		a = l + l % 2
		f = 1
		result = [a, a + 1]
		for a in range(l, min(r + 1, l + 400)):
			for b in range(max(l, r - 400), r + 1):
				if l <= a ^ b <= r:
					f = 0
					result = [a, b, a ^ b]
					break
		for i in range(100000):
			a = randrange(l, r + 1)
			b = randrange(l, r + 1)
			if l <= a ^ b <= r:
				f = 0
				result = [a, b, a ^ b]
				break
	print(f)
	print(len(result))
	print(' '.join((str(i) for i in sorted(result))))
main()


from itertools import combinations
from functools import reduce
from operator import xor
(l, r, k) = map(int, input().split())

def bruteforce(l, r, k):
	rc = []
	rv = float('inf')
	for i in range(1, min(k, r - l + 1) + 1):
		for c in combinations(range(l, r + 1), i):
			v = reduce(xor, c)
			if v < rv:
				rc = c[:]
				rv = v
	return (rv, rc)

def large(l, r, k):
	if l % 2 != 0:
		l += 1
	return (0, list(range(l, l + 4)))

def one(l, r, k):
	return (l, [l])

def two(l, r, k):
	if l % 2 != 0:
		l += 1
	return (1, list(range(l, l + 2)))

def three(l, r, k):
	lgr = 0
	while 1 << lgr <= r:
		lgr += 1
	lgr -= 1
	if lgr < 0:
		return two(l, r, k)
	t = r ^ 1 << lgr
	lgr -= 1
	while lgr >= 0 and (not t & 1 << lgr):
		lgr -= 1
	if lgr < 0:
		return two(l, r, k)
	lgr += 1
	if (1 << lgr) - 1 >= l:
		x1 = r
		x2 = (1 << lgr) - 1
		x3 = x1 ^ x2
		return (0, [x1, x2, x3])
	else:
		return two(l, r, k)
if r - l + 1 <= 4:
	(rv, rc) = bruteforce(l, r, k)
elif k >= 4:
	(rv, rc) = large(l, r, k)
elif k == 1:
	(rv, rc) = one(l, r, k)
elif k == 2:
	(rv, rc) = two(l, r, k)
elif k == 3:
	(rv, rc) = three(l, r, k)
else:
	assert False
print(rv)
print(len(rc))
print(*rc)


import sys
import itertools
import functools

def brute_force(l, r, k):
	best_set = None
	best = None
	for i in range(1, k + 1):
		for s in itertools.combinations(range(l, r + 1), i):
			p = functools.reduce(lambda x, y: x ^ y, s)
			if best is None or p < best:
				best = p
				best_set = s
	print(best)
	print(len(best_set))
	print(' '.join((str(x) for x in best_set)))
(l, r, k) = map(int, sys.stdin.readline().split())
n = r - l + 1
if k > 4:
	k = 4
if n < 7:
	brute_force(l, r, k)
	sys.exit(0)
if k == 1:
	print(l)
	print(1)
	print(l)
	sys.exit(0)
if k == 3:
	w = len(bin(r)) - 2
	for i in range(0, w - 2 + 1):
		a = int('1' + '0' * i + '1' + '0' * (w - 2 - i), 2)
		b = int('1' + '0' * i + '0' + '1' * (w - 2 - i), 2)
		c = int('0' + '0' * i + '1' + '1' * (w - 2 - i), 2)
		if l <= c and a <= r:
			print(0)
			print(3)
			print(c, b, a)
			sys.exit(0)
if 2 <= k <= 3:
	while l % 4 != 0:
		l += 1
	print(1)
	print(2)
	print(l, l + 1)
	sys.exit(0)
while l % 4 != 0:
	l += 1
print(0)
print(4)
print(l, l + 1, l + 2, l + 3)


from itertools import combinations
from functools import reduce

def get_res(l, r, k):
	if k == 1:
		return [l]
	if r == l:
		return [l]
	if r - l == 1:
		if r ^ l < l:
			return [r, l]
		else:
			return [l]
	if k == 2:
		return [l + l % 2, l + 1 + l % 2]
	moi = 2 ** (len(bin(l)) - 2)
	if moi + moi // 2 <= r:
		return [l, moi + moi // 2, l ^ moi + moi // 2]
	if k == 3:
		return [l + l % 2, l + 1 + l % 2]
	next4 = l + (4 - l % 4) % 4
	if next4 + 3 <= r:
		return [next4, next4 + 1, next4 + 2, next4 + 3]
	tempres = l
	tempans = [l]
	for ll in range(2, k + 1):
		for s in combinations(range(l, r + 1), ll):
			rs = reduce(lambda x, y: x ^ y, s, 0)
			if rs < tempres:
				tempans = s
				tempres = rs
	return tempans
(l, r, k) = map(int, input().split())
res = get_res(l, r, k)
s = 0
for i in res:
	s ^= i
print(s)
print(len(res))
print(*res)


def f(arr):
	val = 0
	for x in arr:
		val ^= x
	return val

def solve(l, r, k):
	ret = [l]
	if k >= 2:
		cand = [l, l + 1]
		if f(cand) < f(ret):
			ret = cand
		if l + 2 <= r:
			cand = [l + 1, l + 2]
			if f(cand) < f(ret):
				ret = cand
	if k >= 3:
		x = 1
		while x <= l:
			x *= 2
		if x + x // 2 <= r:
			ret = [x - 1, x + x // 2, x + x // 2 - 1]
	if k >= 4:
		cand = [l, l + 1, l + 2, l + 3]
		if f(cand) < f(ret):
			ret = cand
		if l + 4 <= r:
			cand = [l + 1, l + 2, l + 3, l + 4]
			if f(cand) < f(ret):
				ret = cand
	return ret
(l, r, k) = map(int, input().split())
ans = solve(l, r, k)
print(f(ans))
print(len(ans))
print(' '.join(map(str, ans)))


import functools, itertools

def main():
	(l, r, k) = read()
	tl = l + l % 2
	if tl + 3 <= r and k >= 4:
		print(0)
		print(4)
		print(tl, tl + 1, tl + 2, tl + 3)
		return
	if k >= 3:
		for i in range(0, 50):
			if l <= 2 ** i * 2 - 1 and 2 ** i * 3 <= r:
				print(0)
				print(3)
				print(2 ** i * 2 - 1, 2 ** i * 3 - 1, 2 ** i * 3)
				return
	if tl + 1 <= r and k >= 2:
		print(1)
		print(2)
		print(tl, tl + 1)
		return
	if k == 1 or l == r:
		print(l)
		print(1)
		print(l)
		return
	if l ^ r < l:
		print(l ^ r)
		print(2)
		print(l, r)
	else:
		print(l)
		print(1)
		print(l)

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return list(map(int, inputs.split()))

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')
write(main())


def solve(L, R, k):
	if k < 5:
		if k == 1:
			return [L]
		elif k == 2:
			if R - L + 1 == 2:
				if L < L ^ R:
					return [L]
				else:
					return [L, R]
			elif L & 1:
				return [L + 1, L + 2]
			else:
				return [L, L + 1]
		else:
			b = 60
			while L & 1 << b == 0 and R & 1 << b == 0:
				b -= 1
			if L == 1:
				return [1, 2, 3]
			elif k == 3:
				if L & 1 << b == R & 1 << b:
					return solve(L, R, 2)
				else:
					r = b
					while L & 1 << r == 0:
						r -= 1
					if (1 << b) + (1 << r) <= R:
						return [L, (1 << b) + (1 << r), (1 << b) + (1 << r ^ L)]
					else:
						return solve(L, R, 2)
			elif (L ^ 1) & 1:
				return [L, L + 1, L + 2, L + 3]
			elif L + 4 <= R:
				return [L + 1, L + 2, L + 3, L + 4]
			else:
				return solve(L, R, 3)
	elif L & 1:
		return [L + 1, L + 2, L + 3, L + 4]
	else:
		return [L, L + 1, L + 2, L + 3]
ans = solve(*map(int, input().split()))
xor = 0
for x in ans:
	xor ^= x
print(xor)
print(len(ans))
print(*ans)


from functools import reduce
xor = lambda x, y: x ^ y
(l, r, k) = map(int, input().split())
result = []
if r - l < 5:
	result = [l]
	l1 = [([], list(range(l, r + 1)))]
	l2 = []
	for i in range(1, k + 1):
		for (test, trash) in l1:
			for (j, el) in enumerate(trash):
				l2.append((test + [el], trash[:j] + trash[j + 1:]))
		for (test, trash) in l2:
			if reduce(xor, test) < reduce(xor, result):
				result = test
		l1 = l2
		l2 = []
elif k == 1:
	result = [l]
elif k == 2:
	x = l + l % 2
	result = [x, x + 1]
elif k == 3:
	i = 1
	while 3 * 2 ** (i - 1) <= r:
		if 2 ** i - 1 >= l:
			result = [2 ** i - 1, 3 * 2 ** (i - 1) - 1, 3 * 2 ** (i - 1)]
			break
		i += 1
	if not result:
		x = l + l % 2
		result = [x, x + 1]
else:
	x = l + l % 2
	result = [x, x + 1, x + 2, x + 3]
print(reduce(xor, result))
print(len(result))
print(' '.join(map(str, result)))