Petya has n integers: 1, 2, 3, ..., n. He wants to split these integers in two non-empty groups in such a way that the absolute difference of sums of integers in each group is as small as possible. 

Help Petya to split the integers. Each of n integers should be exactly in one group.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 60 000) — the number of integers Petya has.


-----Output-----

Print the smallest possible absolute difference in the first line.

In the second line print the size of the first group, followed by the integers in that group. You can print these integers in arbitrary order. If there are multiple answers, print any of them.


-----Examples-----
Input
4

Output
0
2 1 4 

Input
2

Output
1
1 1 



-----Note-----

In the first example you have to put integers 1 and 4 in the first group, and 2 and 3 in the second. This way the sum in each group is 5, and the absolute difference is 0.

In the second example there are only two integers, and since both groups should be non-empty, you have to put one integer in the first group and one in the second. This way the absolute difference of sums of integers in each group is 1.

Difficulty: EASY
Tags: Graph algorithms

Mathematics

Constructive algorithms

Starter code:

Solutions:
n = int(input())
l = []
r = []
ls = rs = 0
for i in range(n, 0, -1):
	if ls <= rs:
		ls += i
		l.append(i)
	else:
		rs += i
		r.append(i)
print(abs(ls - rs))
print(len(l), *l)


n = int(input())
ans = []
flag = 0
if n % 2:
	n -= 1
	flag = 1
if n % 4 == 0 and (not flag) or (n % 4 and flag):
	print(0)
	for i in range(n // 2):
		if i % 2 == 0:
			ans.append(i + 1)
			ans.append(n - i)
	print(len(ans), end=' ')
	for i in ans:
		print(i, end=' ')
else:
	print(1)
	for i in range(n // 2 - 1):
		if i % 2 == 0:
			if i % 2 == 0:
				ans.append(i + 1)
				ans.append(n - i)
	ans.append(n // 2 + 1)
	print(len(ans), end=' ')
	for i in ans:
		print(i, end=' ')


n = int(input())
f = []
l = r = 0
for p in range(n, 0, -1):
	if l > r:
		r += p
	else:
		l += p
		f.append(p)
print(abs(l - r))
print(len(f), *f)


n = int(input())
res = []
if n % 4 == 0:
	print(0)
	for i in range(1, n + 1):
		if i % 4 == 0 or i % 4 == 1:
			res.append(i)
elif n % 4 == 2:
	print(1)
	for i in range(1, n + 1):
		if i % 4 == 0 or i % 4 == 1:
			res.append(i)
elif n % 4 == 3:
	print(0)
	for i in range(1, n // 4 + 1):
		res.append(i)
	for i in range(n - n // 4, n + 1):
		res.append(i)
elif n % 4 == 1:
	print(1)
	for i in range(1, n // 4 + 2):
		res.append(i)
	for i in range(n - n // 4 + 1, n + 1):
		res.append(i)
print(len(res))
print(*res)


number = int(input())
answer = list()
if number % 2 == 0 and number % 4 == 0:
	print(0)
	answer.append(number // 2)
	index = 1
	while index <= number // 4:
		answer.append(index)
		answer.append(number + 1 - index)
		index += 1
elif number % 2 == 0 and number % 4 != 0:
	print(1)
	answer.append(number // 2)
	if 0 <= number // 2 - 1:
		rep = (number // 2 - 1) // 2
		index = 1
		while rep != 0:
			answer.append(index)
			answer.append(number + 1 - index)
			index += 1
			rep -= 1
	answer.append(number // 2)
elif number % 2 != 0 and (number - 1) % 4 == 0:
	print(1)
	answer.append(number // 2 + 1)
	answer.append(1)
	answer.append(2)
	if 0 <= number // 2 - 2:
		rep = (number // 2 - 2) // 2
		index = 4
		while rep != 0:
			answer.append(index)
			answer.append(number + 4 - index)
			index += 1
			rep -= 1
	answer.append(number - (number - 3) // 2)
else:
	print(0)
	answer.append(number // 2 + 1)
	answer.append(1)
	answer.append(2)
	if 0 <= number // 2 - 1:
		rep = (number // 2 - 1) // 2
		index = 4
		while rep != 0:
			answer.append(index)
			answer.append(number + 4 - index)
			index += 1
			rep -= 1
print(*answer)


n = int(input())
a = [0 for i in range(n + 1)]
if n % 2 == 0:
	a[n] = 1
	for i in range(n - 1, 0, -1):
		if i % 2 == 0:
			a[i] = a[i + 1]
		else:
			a[i] = 1 - a[i + 1]
else:
	a[n] = 1
	for i in range(n - 1, 0, -1):
		if i % 2 == 1:
			a[i] = a[i + 1]
		else:
			a[i] = 1 - a[i + 1]
b = []
c = []
sb = 0
sc = 0
for i in range(1, n + 1):
	if a[i] == 0:
		b.append(i)
		sb += i
	else:
		c.append(i)
		sc += i
print(abs(sb - sc))
print(len(c), end=' ')
for i in c:
	print(i, end=' ')
print()


n = int(input())
a = []
(sm0, sm1) = (0, 0)
for i in range(1, n + 1):
	if sm0 <= sm1:
		sm0 += n + 1 - i
		a.append(n + 1 - i)
	else:
		sm1 += n + 1 - i
print(abs(sm1 - sm0))
print(len(a), ' '.join((str(i) for i in a)))


n = int(input())
if n % 4 == 3:
	print(0)
	print((n - 3) // 2 + 2, end=' ')
	print(1, 2, ' '.join([str(i) + ' ' + str(i + 3) for i in range(4, n - 2, 4)]))
elif n % 4 == 0:
	print(0)
	print(n // 2, end=' ')
	print(' '.join([str(i) + ' ' + str(i + 3) for i in range(1, n - 2, 4)]))
elif n % 4 == 1:
	print(1)
	print(n // 2 + 1, end=' ')
	print(1, ' '.join([str(i) + ' ' + str(i + 3) for i in range(2, n - 2, 4)]))
elif n % 4 == 2:
	print(1)
	print(n // 2, end=' ')
	print(1, ' '.join([str(i) + ' ' + str(i + 3) for i in range(3, n - 2, 4)]))


import os
import sys
from io import BytesIO, IOBase
import math

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
if n % 4 == 0:
	print(0)
	print(n // 2, end=' ')
	for i in range(0, n // 4):
		print(i + 1, n - i, end=' ')
elif n % 4 == 2:
	print(1)
	print(n // 2, end=' ')
	for i in range(0, n // 4):
		print(i + 1, n - i, end=' ')
	print(n // 2)
elif n % 4 == 3:
	print(0)
	l = n // 4
	r = l + 1
	print(l + r, end=' ')
	for i in range(0, l):
		print(i + 1, end=' ')
	for i in range(n - 1, n - r - 1, -1):
		print(i + 1, end=' ')
else:
	print(1)
	r = n // 4
	l = r + 1
	print(l + r, end=' ')
	for i in range(0, l):
		print(i + 1, end=' ')
	for i in range(n - 1, n - r - 1, -1):
		print(i + 1, end=' ')


n = int(input())
a = []
i = n
diff = n * (n + 1) // 2 // 2
sum = 0
for i in range(n, 0, -1):
	if i + sum < diff:
		a.append(i)
		sum = sum + i
	else:
		a.append(diff - sum)
		sum = sum + (diff - sum)
		break
print(abs(n * (n + 1) // 2 - 2 * sum))
print(len(a), end=' ')
for i in a:
	print(i, end=' ')


n = int(input())
A = []
a = 0
b = n * (n + 1) // 2
m = n
while a < b and m > 0:
	a += m
	A.append(m)
	b -= m
	m -= 1
diff = (a - b) // 2
i = m
j = m + 1
while j - i < diff and j < n:
	j += 1
while j - i < diff and i > 0:
	i -= 1
if diff > 0:
	A.remove(j)
	a -= j
	b += j
	A.append(i)
	a += i
	b -= i
print(abs(a - b))
print(len(A), *A)


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
arr = [i for i in range(1, n + 1)]
x = (sum(arr) + 1) // 2
ml = []
for i in arr[::-1]:
	if i <= x:
		ml.append(i)
		x -= i
print(sum(ml) - sum(arr) // 2)
print(len(ml), *ml)


n = int(input())
arr = []
if n % 4 == 0:
	ans = 0
	for x in range(1, n + 1):
		if x % 4 == 1 or x % 4 == 0:
			arr.append(x)
if n % 4 == 1:
	ans = 1
	for x in range(1, n + 1):
		if x % 4 == 2 or x % 4 == 1:
			arr.append(x)
if n % 4 == 2:
	ans = 1
	for x in range(1, n + 1):
		if x % 4 == 3 or x % 4 == 2:
			arr.append(x)
if n % 4 == 3:
	ans = 0
	for x in range(1, n + 1):
		if x % 4 == 0 or x % 4 == 3:
			arr.append(x)
print(ans)
print(len(arr), end=' ')
print(*arr)


(n, first, second, ar) = (int(input()), 0, 0, [])
for i in range(n, 0, -1):
	if first >= second:
		second += i
	else:
		first += i
		ar.append(i)
print(abs(first - second), len(ar), ' '.join(map(str, ar)), sep='\n')


n = int(input())
if n % 4 == 0:
	print('0')
	L = []
	L.append(str(int(n // 2)))
	for i in range(n // 4):
		L.append(str(i + 1))
		L.append(str(n - i))
	print(' '.join(L))
elif n % 4 == 1:
	print('1')
	L = []
	L.append(str(n // 2))
	for j in range((n - 1) // 4):
		L.append(str(j + 2))
		L.append(str(n - j))
	print(' '.join(L))
elif n % 4 == 2:
	print('1')
	L = []
	L.append(str(n // 2))
	for k in range(n // 4):
		L.append(str(k + 3))
		L.append(str(n - k))
	L.append(str(1))
	print(' '.join(L))
elif n % 4 == 3:
	print('0')
	L = []
	L.append(str(n // 2))
	for l in range(n // 4):
		L.append(str(l + 4))
		L.append(str(n - l))
	L.append(str(3))
	print(' '.join(L))


n = int(input())
lista_a = []
lista_a.append(n)
for i in range(n - 3, 0, -4):
	lista_a.append(i)
	if i != n and i > 1:
		lista_a.append(i - 1)
a = sum(lista_a)
t = int(n * (n + 1) / 2)
b = t - a
print(abs(b - a))
print(str(len(lista_a)) + ' ' + ' '.join([str(i) for i in lista_a]))


n = int(input())
s = ''
if n % 4 == 0:
	print(0)
	s += str(n // 2) + ' '
	for i in range(n // 4):
		s += str(4 * i + 1) + ' '
		s += str(4 * i + 4) + ' '
	print(s[:-1])
elif n % 4 == 3:
	print(0)
	s += str(n // 2 + 1) + ' '
	s += '1 2 '
	for i in range(n // 4):
		s += str(4 * i + 4) + ' '
		s += str(4 * i + 7) + ' '
	print(s[:-1])
elif n % 4 == 2:
	print(1)
	s += str(n // 2) + ' 1 '
	for i in range(0, n // 4):
		s += str(4 * i + 3) + ' '
		s += str(4 * i + 6) + ' '
	print(s[:-1])
else:
	print(1)
	s += str(n // 2 + 1) + ' 1 '
	for i in range(0, n // 4):
		s += str(4 * i + 2) + ' '
		s += str(4 * i + 5) + ' '
	print(s[:-1])


n = int(input())
x = n * (n + 1) // 4
i = n
while x > i:
	x -= i
	i -= 1
a = list(range(i + 1, n + 1))
if x != 0:
	print(n * (n + 1) // 2 % 2)
	print(n - i + 1, x, end=' ')
	print(*a)
else:
	print(n * (n + 1) // 2 % 2)
	print(n - i, end=' ')
	print(*a)


n = int(input())
(add, v) = (0, [])
if n % 2:
	(n, add, v) = (n - 3, add + 1, [3])
if n % 4 == 0:
	print(0, n // 2 + add, sep='\n', end=' ')
	for i in range(1, n // 4 + 1):
		print(i + add * 3, n - i + 1 + add * 3, end=' ')
	print(*v)
elif n % 2 == 0:
	print(1, n // 2 + add, sep='\n', end=' ')
	for i in range(1, n // 4 + 1):
		print(i + add * 3, n - i + 1 + add * 3, end=' ')
	print(n // 2 + add * 3, *v)


n = int(input())
(a, b) = (0, 0)
x = []
for i in range(n, 0, -1):
	if a > b:
		b += i
	else:
		x.append(i)
		a += i
print(abs(a - b))
print(len(x), *x)


import sys
n = int(sys.stdin.readline().rstrip('\n'))
if n % 4 == 0:
	res = []
	for i in range(1, n + 1):
		if i % 4 == 1 or i % 4 == 0:
			res.append(i)
	print(0)
	print(len(res), ' '.join(list(map(str, res))))
	exit(0)
elif n % 4 == 1:
	res = []
	for i in range(2, n + 1):
		if i % 4 == 1 or i % 4 == 2:
			res.append(i)
	print(1)
	print(len(res) + 1, 1, ' '.join(list(map(str, res))))
	exit(0)
elif n % 4 == 2:
	res = []
	for i in range(3, n + 1):
		if i % 4 == 3 or i % 4 == 2:
			res.append(i)
	print(1)
	print(len(res) + 1, 1, ' '.join(list(map(str, res))))
	exit(0)
elif n % 4 == 3:
	res = []
	for i in range(4, n + 1):
		if i % 4 == 0 or i % 4 == 3:
			res.append(i)
	print(0)
	print(len(res) + 2, 1, 2, ' '.join(list(map(str, res))))
	exit(0)


n = int(input())
if n < 4:
	if n == 2:
		print(1)
		print(1, 1)
	elif n == 3:
		print(0)
		print(1, 3)
elif n % 4 == 0:
	print(0)
	k = int(n / 4)
	print(2 * k, end=' ')
	for i in range(k):
		print(n - i, i + 1, end=' ')
elif n % 4 == 1:
	print(1)
	k = int(n / 4)
	print(2 * k, end=' ')
	for i in range(k):
		print(n - i, i + 2, end=' ')
elif n % 4 == 2:
	print(1)
	k = int(n / 4)
	print(2 * k + 1, 1, end=' ')
	for i in range(k):
		print(n - i, i + 3)
elif n % 4 == 3:
	print(0)
	k = int(n / 4)
	print(2 * k + 1, 3, end=' ')
	for i in range(k):
		print(n - i, i + 4, end=' ')


n = int(input())
if n == 2:
	print(1)
	print(1, 1)
	exit()
s = n * (n + 1) // 2
if s & 1:
	print(1)
	x = (s - 1) // 2
	res = set()
	for i in range(n, 0, -1):
		if i <= x:
			x -= i
			res.add(i)
			if not x:
				break
	print(len(res), *res)
else:
	print(0)
	x = s // 2
	res = set()
	for i in range(n, 0, -1):
		if i <= x:
			x -= i
			res.add(i)
			if not x:
				break
	print(len(res), *res)


n = int(input())
first = list()
second = list()
sm1 = sm2 = 0
for i in range(n, 0, -1):
	if sm1 <= sm2:
		sm1 += i
		first.append(i)
	else:
		sm2 += i
		second.append(i)
print(abs(sm1 - sm2))
print(len(first), *first)


n = int(input())
d = -1
s = n // 2
if n % 4 == 0:
	d = 0
elif n % 2 != 0:
	k1 = n - 3
	if k1 % 4 == 0:
		d = 0
	else:
		d = 1
else:
	d = 1
print(d)
if n == 1:
	print(s, 0, end=' ')
elif n == 2:
	print(s, 1, end=' ')
elif n == 3:
	print(1, 3, end=' ')
else:
	print(s, end=' ')
	if n % 2 != 0:
		print(3, end=' ')
		j = 4
		n += 3
		if k1 % 4 == 0:
			while j < n // 2:
				print(j, end=' ')
				j += 2
			j = n // 2 + 2
			while j <= n - 3:
				print(j, end=' ')
				j += 2
		else:
			while j < n // 2 - 1:
				print(j, end=' ')
				j += 2
			print(n // 2, end=' ')
			j = n // 2 + 3
			while j <= n - 3:
				print(j, end=' ')
				j += 2
	elif n % 4 == 0:
		j = 1
		while j < n // 2:
			print(j, end=' ')
			j += 2
		j = n // 2 + 2
		while j <= n:
			print(j, end=' ')
			j += 2
	else:
		j = 1
		while j < n // 2 - 1:
			print(j, end=' ')
			j += 2
		print(n // 2, end=' ')
		j = n // 2 + 3
		while j <= n:
			print(j, end=' ')
			j += 2


n = int(input())
(l, t, s1, s2) = ([n], [n - 1], n, n - 1)
for i in range(n - 2, 0, -1):
	if s1 < s2:
		l.append(i)
		s1 += i
	else:
		t.append(i)
		s2 += i
print(abs(s2 - s1))
print(len(l), *l)


n = int(input())
out = []
if n % 4 == 0:
	print(0)
	out = []
	for i in range(n // 2):
		if i & 1 == 0:
			out.append(i + 1)
			out.append(n - i)
	print(len(out), *out)
elif n % 2 == 0:
	print(1)
	mid = n // 2
	out.append(n // 2)
	for i in range(n // 2 - 1):
		if i & 1 == 0:
			out.append(i + 1)
			out.append(n - i)
	print(len(out), *out)
elif n % 2 != 0 and n % 4 == 1:
	print(1)
	out.append(1)
	l = 2
	r = n
	flag = True
	while l < r:
		if flag:
			out.append(l)
			out.append(r)
		l += 1
		r -= 1
		flag = not flag
	print(len(out), *out)
else:
	print(0)
	out.append(1)
	out.append(n // 2 + 1)
	mid = n // 2
	l = 2
	r = n
	flag = True
	while l <= mid:
		if flag:
			out.append(l)
			out.append(r)
		l += 1
		r -= 1
		flag = not flag
	print(len(out), *out)


n = int(input())
summa = (n + 1) * n // 2
L = []
if summa % 2 == 0:
	print(0)
	summa1 = 0
	k = n
	while summa1 + k <= summa // 2:
		summa1 += k
		L.append(k)
		k -= 1
	if summa // 2 != summa1 and summa // 2 - summa1 != 0:
		L.append(summa // 2 - summa1)
else:
	print(1)
	summa1 = 0
	k = n
	while summa1 + k <= summa // 2:
		summa1 += k
		L.append(k)
		k -= 1
	if summa // 2 - summa1 != 0:
		L.append(summa // 2 - summa1)
print(len(L), end=' ')
for i in L:
	print(i, end=' ')


n = int(input())
s = sum([i for i in range(n + 1)])
print(s % 2)
ans = []
q = s // 2
for i in range(n - 1, 0, -1):
	if q >= i:
		ans = [i] + ans
		q -= i
print(len(ans), *ans)


n = int(input())
ls = list(range(1, n + 1))

def ans(ls, n):
	ls2 = []
	if n == 2:
		print(1)
		print(1, 1)
		return
	if n % 2 == 0:
		if n % 4 == 0:
			print(0)
			print(n // 2, end=' ')
			for i in range(0, n // 2, 2):
				ls2.append(ls[i])
				ls2.append(ls[n - i - 1])
			for i in ls2:
				print(i, end=' ')
			print()
			return
		else:
			print(1)
			for i in range(0, n // 2 - 1, 2):
				ls2.append(ls[i])
				ls2.append(ls[n - i - 1])
			ls2.append(ls[n // 2])
			print(len(ls2), end=' ')
			for i in ls2:
				print(i, end=' ')
			print()
			return
	ls2 = ['1']
	j = 1
	k = 0
	while j < n:
		ls2.append(ls[j])
		if k % 2 == 0:
			j += 3
		else:
			j += 1
		k += 1
	if n == 3:
		print(0)
		print(2, 1, 2)
		return
	elif (n - 1) % 4 == 0:
		print(1)
	else:
		print(0)
	print(n // 2 + 1, end=' ')
	for i in ls2:
		print(i, end=' ')
	print()
	return
ans(ls, n)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = inp()
s = n * (n + 1) // 2
if s % 2 == 0:
	pr(0)
else:
	pr(1)
size = n // 2
ans = []
prl(size)
s = s // 2
for i in range(n, 0, -1):
	if i > s:
		continue
	if size * (size - 1) // 2 <= s - i:
		ans.append(i)
		s -= i
		size -= 1
print(*ans)


n = int(input())
sumV = int(n * (n + 1) / 4)
if n % 4 == 1 or n % 4 == 2:
	print('1')
else:
	print('0')
arr = list()
while sumV > 0:
	if sumV > n:
		arr.append(n)
		sumV -= n
		n -= 1
	else:
		arr.append(sumV)
		sumV = 0
print(len(arr), end=' ')
for i in range(len(arr)):
	print(arr[i], end=' ')


n = int(input())
if n % 4 == 0:
	print(0)
	print(n // 4 * 2, end=' ')
	i = 1
	while i + 3 <= n:
		print(i, end=' ')
		print(i + 3, end=' ')
		i += 4
else:
	right = 0
	left = 0
	ans = []
	i = 2
	while n > 0:
		if right > left:
			left += n
		else:
			ans.append(n)
			right += n
		n -= 1
	print(abs(right - left))
	print(len(ans), *ans)


n = int(input())
l = [n]
r = []
for i in range(n - 1, 0, -4):
	r.append(i)
	if i > 1:
		r.append(i - 1)
for i in range(n - 3, 0, -4):
	l.append(i)
	if i > 1:
		l.append(i - 1)
print(abs(sum(l) - sum(r)))
print('' + str(len(l)) + ' ' + ' '.join(map(str, l)))


def chet(path):
	n = len(path)
	if n % 2 == 0:
		if n == 2:
			print(1)
			print(1, 1)
		if n > 2 and n % 4 != 0:
			f_half = []
			i = 0
			while i + 1 < n // 2:
				f_half.append(path[i])
				f_half.append(path[-1 - i])
				i = i + 2
			f_half.append(path[n // 2 - 1])
			print(1)
			print(n // 2, *f_half)
		elif n > 2 and n % 4 == 0:
			f_half = []
			i = 0
			while i + 1 < n // 2:
				f_half.append(path[i])
				f_half.append(path[-1 - i])
				i = i + 2
			print(0)
			print(n // 2, *f_half)

def nechet(path):
	if sum(path) % 2 == 0:
		if len(path) == 3:
			print(0)
			print(1, 3)
		else:
			f_half = [1, 2]
			n = len(path[3:])
			i = 0
			while i + 1 < n // 2:
				f_half.append(path[3:][i])
				f_half.append(path[3:][-1 - i])
				i = i + 2
			print(0)
			print(len(f_half), *f_half)
	else:
		f_half = [1]
		n = len(path[1:])
		i = 0
		while i + 1 < n // 2:
			f_half.append(path[1:][i])
			f_half.append(path[1:][-1 - i])
			i = i + 2
		print(1)
		print(len(f_half), *f_half)
n = int(input())
path = range(1, n + 1)
if n % 2 == 0:
	chet(path)
else:
	nechet(path)


a = []
n = int(input().strip())
if n % 4 == 0:
	print(0)
	for i in range(1, n + 1, 4):
		a.append(i)
		a.append(i + 3)
elif n % 4 == 3:
	print(0)
	a.append(3)
	for i in range(4, n + 1, 4):
		a.append(i)
		a.append(i + 3)
elif n % 4 == 2:
	print(1)
	a.append(1)
	for i in range(3, n + 1, 4):
		a.append(i)
		a.append(i + 3)
else:
	print(1)
	for i in range(2, n + 1, 4):
		a.append(i)
		a.append(i + 3)
print(len(a), end=' ')
for i in range(len(a)):
	print(a[i], end=' ')


n = int(input())
sm = n * (n + 1) // 2
arr = []
tempsm = 0
for i in range(n, 0, -1):
	if tempsm + i <= (sm + 1) // 2:
		tempsm += i
		arr.append(i)
print(int(abs(2 * sum(arr) - sm)))
print(len(arr))
for i in arr:
	print(i, end=' ')


n = int(input())
v = int(n * (n + 1) / 2)
print(v % 2)
targ = int(v / 2)
seq = []
for i in range(n, 0, -1):
	if targ >= i:
		targ -= i
		seq.append(i)
print(len(seq), end=' ')
[print(seq[i], end=' ') for i in range(len(seq))]


n = int(input())
k = n * (n + 1) // 2
if n == 2:
	print(1)
	print(1, 1, sep=' ')
elif n & 1 == 0 and k & 1 == 0:
	s = 0
	a = []
	s1 = 1
	s2 = n
	d = 0
	while s != k // 2:
		a.append(s1)
		a.append(s2)
		s += s1 + s2
		s1 += 1
		s2 -= 1
	print(0)
	print(len(a), *a, sep=' ')
elif n & 1 == 0 and k & 1 == 1:
	s = 0
	a = []
	s1 = 1
	s2 = n
	d = k // 2
	while d - s > n:
		a.append(s1)
		a.append(s2)
		s += s1 + s2
		s1 += 1
		s2 -= 1
	a.append(d - s)
	print(1)
	print(len(a), *a, sep=' ')
elif n & 1 == 1:
	s = 0
	a = []
	s1 = 1
	s2 = n
	d = k // 2
	while d - s > n:
		a.append(s1)
		a.append(s2)
		s += s1 + s2
		s1 += 1
		s2 -= 1
	if d - s not in a:
		a.append(d - s)
	else:
		a.append(d - s + 1)
	if k & 1 == 0:
		print(0)
	else:
		print(1)
	print(len(a), *a, sep=' ')


n = int(input())
s = n * (n + 1) // 2
f = s // 2 + s % 2
l = []
while n > 0:
	if f - n >= 0:
		l += [n]
		f -= n
	n -= 1
print(s % 2)
print(len(l), ' '.join(map(str, l)))


n = int(input())
(n2, a, b) = ((n * n + n) // 2, [], 0)
print(n2 % 2)
n2 //= 2
while n2 >= n:
	(a, n2, n, b) = (a + [n], n2 - n, n - 1, b + 1)
if n2 != 0:
	(a, b) = (a + [n2], b + 1)
print(b, ' '.join(map(str, a)))


n = int(input())
if n % 4 == 0:
	a = [int(n / 2)]
	for t in range(1, int(n / 2) + 1):
		if t % 2 == 1:
			a.append(t)
			a.append(n + 1 - t)
	print(0)
	print(' '.join(map(str, a)))
if n % 4 == 1:
	a = [int(n / 2) + 1, 1]
	for t in range(2, int(n / 2) + 1):
		if t % 2 == 0:
			a.append(t)
			a.append(n + 2 - t)
	print(1)
	print(' '.join(map(str, a)))
if n % 4 == 2:
	a = [int(n / 2)]
	for t in range(1, n + 1):
		if t % 4 == 1 or t % 4 == 0:
			a.append(t)
	print(1)
	print(' '.join(map(str, a)))
if n % 4 == 3:
	a = [int(n / 2) + 1, 1, 2]
	for t in range(4, int((n - 3) / 2) + 3):
		if t % 2 == 0:
			a.append(t)
			a.append(n + 4 - t)
	print(0)
	print(' '.join(map(str, a)))


n = int(input())
length = n
group1 = []
group2 = []
if length % 4 == 0:
	for i in range(1, int(length / 2)):
		if i % 2 == 1:
			group1.append(i)
			group1.append(n - i + 1)
		else:
			group2.append(i)
			group2.append(n - i + 1)
	print(0)
	print(len(group1), *group1)
elif length % 2 == 0:
	k = 0
	for i in range(1, int(length / 2)):
		if i % 2 == 1:
			group1.append(i)
			group1.append(n - k)
		else:
			group2.append(i)
			group2.append(n - k)
		k += 1
	group1.append(int(length / 2))
	group2.append(int(length % 2 + 1))
	print(1)
	print(len(group1), *group1)
else:
	if length % 4 == 3:
		k = 0
		for i in range(4, int(length / 2 + 3)):
			if i % 2 == 1:
				group1.append(i)
				group1.append(n - k)
			else:
				group2.append(i)
				group2.append(n - k)
			k += 1
		group1.append(1)
		group1.append(2)
		group2.append(3)
		print(0)
		print(len(group1), *group1)
	if length % 4 == 1:
		k = 0
		for i in range(2, int(length / 2 + 3)):
			if i % 2 == 1:
				group1.append(i)
				group1.append(n - k)
			else:
				group2.append(i)
				group2.append(n - k)
			k += 1
		group1.append(1)
		print(1)
		print(len(group1), *group1)


n = int(input())
tot = n * (n + 1) // 2
print(tot % 2)
sol = []
goal = tot // 2
for sub in range(n, 0, -1):
	if goal >= sub:
		goal -= sub
		sol.append(sub)
if goal != 0:
	assert 1 == 2
print('{} {}'.format(len(sol), str(sol)[1:-1].replace(',', '')))


n = int(input())
a = [int(i) for i in range(1, n + 1)]
a.reverse()
left = 0
right = 0
l = []
r = []
for i in a:
	if left < right:
		left += i
		l.append(i)
	else:
		right += i
		r.append(i)
print(abs(left - right))
l.sort()
r.sort()
ans = [l, r]
ans.sort()
print(len(ans[0]), ' '.join((str(i) for i in ans[0])))


n = int(input())
total_sum = n * (n + 1) // 2
if total_sum % 2 == 0:
	ans = 0
	n1 = total_sum // 2
else:
	n1 = total_sum // 2
	ans = 1
arr = [i + 1 for i in range(n)]
ans1 = []
for i in range(n, 0, -1):
	if n1 != 0 and n1 >= i:
		n1 -= i
		ans1.append(i)
	if n1 == 0:
		break
print(ans)
print(len(ans1), *ans1)


n = int(input())
print(0 if n % 4 == 0 or n % 4 == 3 else 1)
l = []
if n % 4 == 0 or n % 4 == 2:
	if n % 4 == 2:
		l.append(n // 2)
	for i in range(1, n // 4 + 1):
		l.append(i)
		l.append(n + 1 - i)
else:
	if n % 4 == 3:
		l.append(1)
		l.append(n // 2 + 1)
	for i in range(2, n // 4 + 2):
		l.append(i)
		l.append(n + 2 - i)
print(len(l), *l)


n = int(input())
sum = (1 + n) * n // 2
print(sum % 2)
a = sum // 2
ans = []
while a:
	if a > n:
		ans += [n]
		a -= n
		n -= 1
	else:
		ans += [a]
		a = 0
print(len(ans), end=' ')
for i in ans:
	print(i, end=' ')


from math import ceil
n = int(input())
if n % 4 == 0:
	print(0)
	print(int(n / 2), end=' ')
	for i in range(1, int(n / 2), 2):
		print(i, n + 1 - i, end=' ')
elif n % 2 == 0:
	print(1)
	print(int(n / 2), end=' ')
	for i in range(3, int(n / 2) + 1, 2):
		print(i, n + 3 - i, end=' ')
	print(1)
elif (n - 1) % 4 == 0:
	print(1)
	print(ceil(n / 2), end=' ')
	for i in range(2, int(n / 2) + 2, 2):
		print(i, n + 2 - i, end=' ')
	print(1)
elif (n - 1) % 2 == 0:
	print(0)
	print(ceil(n / 2), end=' ')
	for i in range(4, int(n / 2) + 3, 2):
		print(i, n + 4 - i, end=' ')
	print(1, 2)


import sys
lines = []
for line in sys.stdin:
	lines.append(line)
n = int(lines[0].rstrip('\r\n\t '))
in_a = []
a_size = 0
a_sum = 0
b_sum = 0
for x in range(n, 0, -1):
	if a_sum <= b_sum:
		in_a.append(str(x))
		a_size += 1
		a_sum += x
	else:
		b_sum += x
print('{}\n{} {}'.format(abs(a_sum - b_sum), a_size, ' '.join(in_a)))


n = int(input())
(a, b) = (0, 0)
l = []
for i in range(n, 0, -1):
	if a <= b:
		a += i
		l.append(i)
	else:
		b += i
print(a - b)
print(len(l), end=' ')
print(*tuple(l))


n = int(input())
if n % 2 == 0:
	if n % 4 == 0:
		print(0)
		print(n // 2, end=' ')
		k = 1
		for i in range(n // 4):
			print(k, end=' ')
			print(n - k + 1, end=' ')
			k += 1
	else:
		print(1)
		print(n // 2, end=' ')
		k = 1
		for i in range(n // 4):
			print(k, end=' ')
			print(n - k + 1, end=' ')
			k += 1
		print(n // 2)
elif n % 2 == 1:
	a = n * (n + 1) // 2
	if a % 2 == 0:
		print(0)
		print((n + 1) // 2, end=' ')
		k = (n + 1) // 4
		for i in range((n + 1) // 2):
			print(k, end=' ')
			k += 1
	elif a % 2 == 1:
		print(1)
		print((n - 1) // 2, end=' ')
		k = (n + 7) // 4
		for i in range((n - 1) // 2):
			print(k, end=' ')
			k += 1


n = int(input())
tot = n * (n + 1) // 2
l = []
if n == 2:
	print(1)
	print('1 1')
	exit(0)
if n == 3:
	print(0)
	print('2 1 2')
	exit(0)
i = 1
if tot % 2 == 0:
	tot //= 2
	while 1:
		tot -= n + 1
		l.append(i)
		l.append(n + 1 - i)
		if tot == 0:
			break
		elif tot <= n and tot > i:
			l.append(tot)
			break
		i += 1
	print('0')
else:
	tot //= 2
	while 1:
		tot -= n + 1
		l.append(i)
		l.append(n + 1 - i)
		if tot <= n and tot > i:
			l.append(tot)
			break
		elif tot <= n and tot + 1 > i:
			l.append(tot + 1)
			break
		i += 1
	print('1')
print(len(l), end=' ')
for i in l:
	print(i, end=' ')


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
n = int(input())
if n == 2:
	print(1)
	print(1, 1)
elif n == 3:
	print(0)
	print(2, 1, 2)
else:
	l = []
	for i in range(n, 2, -4):
		l.append(i - 1)
		l.append(i - 2)
	if n % 4 == 0 or n % 4 == 3:
		print(0)
		print(len(l), *l)
	else:
		print(1)
		print(len(l) + 1, *l, 1)


from math import sqrt, ceil

def main():
	n = int(input())
	nn = n * (n + 1) // 2
	x = int(ceil(sqrt(nn + 0.25) - 0.5))
	(res, xx) = (list(range(n, x, -1)), x * (x + 1))
	t = (xx - nn) // 2
	if t:
		res.append(t)
		xx -= t * 2
	print(xx - nn)
	res.append(len(res))
	print(' '.join(map(str, res[::-1])))
main()


import math
import sys
from collections import defaultdict
from collections import Counter
from collections import deque
import bisect
sys.setrecursionlimit(1000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
N = int(input())
t = N * (N + 1) // 2
tt = t // 2
f = 0
A = []
for i in range(N, 0, -1):
	if f + i <= tt:
		A.append(i)
		f += i
print(abs(t - 2 * f))
print(len(A), end=' ')
print(*A)


n = int(input())
l = list(range(1, n + 1))
r = []
if n % 4 == 0:
	r = list(range(1, n // 2, 2)) + list(range(n, n // 2, -2))
	print(0)
	print(len(r), *r)
if n % 4 == 2 and n != 2:
	r = list(range(1, n // 2, 2)) + list(range(n, n // 2, -2))
	print(1)
	print(len(r), *r)
if n % 4 == 1:
	r = list(range(1, n // 2, 2)) + list(range(n, n // 2, -2))
	m = (n + 1) // 2
	if m // 2 % 2 != 0:
		m = m // 2
	else:
		m = (m + 1) // 2
	r.remove(m)
	print(1)
	print(len(r), *r)
if n % 4 == 3:
	n += 1
	r = list(range(1, n // 2, 2)) + list(range(n, n // 2, -2))
	r.remove(n)
	r.append(n // 2)
	print(0)
	print(len(r), *r)
if n == 2:
	print(1)
	print(1, 1)


import math
n = int(input())
ans = []
b = False
if n % 4 == 0:
	print(0)
	print(n // 2, end=' ')
	for i in range(n // 4):
		print(i + 1, n - i, end=' ')
if n % 4 == 1:
	print(1)
	if n // 4 % 2 == 0:
		print(n // 2 + 1, end=' ')
		for i in range(n // 4):
			print(2 * i + 1, n - 2 * i, end=' ')
		print((n // 2 + 1) // 2, end=' ')
	if n // 4 % 2 == 1:
		print(n // 2 + 1, end=' ')
		for i in range(n // 4):
			print(2 * i + 1, n - 2 * i, end=' ')
		print((n // 2 + 1) // 2 + 1, end=' ')
if n % 4 == 2:
	print(1)
	print(n // 2, end=' ')
	for i in range(n // 4):
		print(2 * i + 1, n - 2 * i, end=' ')
	print(n // 2)
if n % 4 == 3:
	if n == 3:
		print(0)
		print(1, ' ', 3)
	if n > 3:
		print(0)
		for i in range(n // 4):
			ans.append(1 + 2 * i)
			ans.append(n - 2 * i)
		for i in range(len(ans)):
			if ans[i] == int(n / 4 - 0.75):
				ans[i] = n // 2
				ans.append(n // 2 + 1)
				b = True
		if b == False:
			ans.append(n // 2 + 2)
			ans.append(int(n / 4 - 0.75))
		print(len(ans), end=' ')
		for i in range(len(ans)):
			print(ans[i], end=' ')


n = int(input())
num_list = []
part_sum = n * (n + 1) // 4
if n % 4 == 1 or n % 4 == 2:
	dif = 1
elif n % 4 == 3 or n % 4 == 0:
	dif = 0
now = 0
for i in range(n // 2):
	num_list.append(i + 1)
	now += i + 1
i += 1
while now != part_sum:
	if now < part_sum:
		i += 1
		num_list.append(i)
		now += i
	else:
		now -= num_list.pop(0)
print(dif)
print(len(num_list), end=' ')
for i in range(len(num_list)):
	print(num_list[i], end=' ')
print()


n = int(input())
tot = n * (n + 1) / 2
m = int(tot / 2)
arr = []
s = 0
for i in range(n, 0, -1):
	s += i
	if s > m:
		s -= i
	else:
		arr.append(i)
tot = int(tot - sum(arr))
print(abs(tot - sum(arr)))
print(len(arr), *arr)


n = int(input())
if n % 4 == 0:
	print(0)
	print(n // 2, end=' ')
	step = 0
	for i in range(1, n + 1, 2):
		print(i + step, end=' ')
		step = 1 - step
elif n % 4 == 3:
	print(0)
	print(n // 2, end=' ')
	step = 1
	for i in range(2, n + 1, 2):
		print(i + step, end=' ')
		step = 1 - step
else:
	print(1)
	if n % 4 == 2:
		print(n // 2, end=' ')
		step = 0
		for i in range(1, n + 1, 2):
			print(i + step, end=' ')
			step = 1 - step
	else:
		print(n // 2, end=' ')
		step = 1
		for i in range(2, n + 1, 2):
			print(i + step, end=' ')
			step = 1 - step


import bisect

def list_output(s):
	print(' '.join(map(str, s)))

def list_input(s='int'):
	if s == 'int':
		return list(map(int, input().split()))
	elif s == 'float':
		return list(map(float, input().split()))
	return list(map(str, input().split()))
n = int(input())
a = list()
for i in range(n // 4):
	a.append(i + 1 + n % 4)
	a.append(n - i)
diff = 0
if n % 4 == 1:
	diff = 1
elif n % 4 == 2:
	diff = 1
	a.append(1)
elif n % 4 == 3:
	diff = 0
	a.append(1)
	a.append(2)
print(diff)
print(len(a), ' '.join(map(str, a)))


n = int(input())
print(n * (n + 1) // 2 % 2)
ans = list()
t = True
while n > 0:
	ans.append(n)
	if t:
		n -= 3
		t = False
	else:
		n -= 1
		t = True
print(len(ans), end=' ')
for i in ans:
	print(i, end=' ')


n = int(input())
total = n * (n + 1) / 2
if total % 2 == 0:
	diff = 0
else:
	diff = 1
res = []
nums = [i for i in range(1, n + 1)][::-1]
sum_num = 0
for num in nums:
	if sum_num + num <= total / 2:
		sum_num += num
		res.append(num)
print(diff)
print(str(len(res)) + ' ' + ' '.join((str(item) for item in res)))


import sys
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
n = int(ri())
summ = n * (n + 1) // 2
if summ % 2 == 0:
	print(0)
	ans = []
	csumm = 0
	for i in range(n, 0, -1):
		csumm += i
		if csumm <= summ // 2:
			ans.append(i)
		else:
			csumm -= i
	print(len(ans), *ans)
else:
	print(1)
	ans = []
	csumm = 0
	for i in range(n, 0, -1):
		csumm += i
		if csumm <= summ // 2:
			ans.append(i)
		else:
			csumm -= i
	print(len(ans), *ans)


N = int(input())
List = list()
(K, curr) = (N * (N + 1) / 2, 0)
want = K // 2
if K % 2 == 0:
	print(0)
else:
	print(1)
while N != 0:
	if curr + N <= want:
		curr += N
		List.append(N)
	N -= 1
print(len(List), end=' ')
for num in List:
	print(num, end=' ')


n = int(input())
i = 1
l = []
if n % 2 == 1:
	l = [1]
	i = 2
	print((n // 2 + 1) % 2)
else:
	print(n // 2 % 2)
j = 0
while i <= n:
	l.append(i)
	i = i + 3 if j % 2 == 0 else i + 1
	j = (j + 1) % 2
print(len(l), *l, sep=' ')


import sys
mod = 1000000007

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline()

def print_array(a):
	print(' '.join(map(str, a)))

def main():
	n = int(input())
	l = list(range(1, n + 1))
	a = []
	target = n * (n + 1) // 4
	accum = 0
	for i in reversed(l):
		if accum + i <= target:
			a.append(i)
			accum += i
	print(abs(accum - n * (n + 1) // 2 + accum))
	print(len(a), ' '.join((str(x) for x in a)))
main()


import sys
from math import gcd, ceil, sqrt
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7
from collections import Counter, defaultdict as df
from functools import reduce

def counter(l):
	return dict(Counter(l))

def printm(l):
	for i in range(len(l[0])):
		print(*l[i])

def P(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def so(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

def rev(l):
	return list(reversed(l))

def ini():
	return int(sys.stdin.readline())

def inp():
	return map(int, sys.stdin.readline().strip().split())

def li():
	return list(map(int, sys.stdin.readline().strip().split()))

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

def inputm(n, m):
	return [li() for i in range(m)]
a = 'Ashishgup'
b = 'FastestFinger'
n = ini()
l = []
c1 = 0
c2 = 0
x = n * (n + 1) // 4
for i in range(1, n + 1):
	if c1 + i <= x:
		l += [i]
		c1 += i
	else:
		break
m = i
for i in range(i, n + 1):
	c2 += i
if abs(c1 - c2) == 0:
	print(0)
	print(len(l), *l)
else:
	x = m - (c2 - c1) // 2
	if x in l:
		c1 -= x
		c1 += m
		c2 += x
		c2 -= m
		l.remove(x)
		l += [m]
	print(abs(c1 - c2))
	print(len(l), *l)


n = int(input())
if n == 3:
	print(0)
	print(2, 1, 2)
	quit()
start = 1
if n % 2 != 0:
	start = 2
end = n // 2
if end % 2 != 0:
	end -= 1
a = [k for k in range(start, n + 1)]
b = a[::-1]
c = []
d = []
step = True
for k in range(end):
	if step:
		c.append(a[k])
		c.append(b[k])
	else:
		d.append(a[k])
		d.append(b[k])
	step = not step
if start != 1:
	c.insert(0, 1)
if end != n // 2:
	c.append(b[n // 2])
	d.append(a[n // 2])
print(abs(sum(c) - sum(d)))
print(len(c), *c)


N = int(input())
if N % 4 in [0, 3]:
	print(0)
else:
	print(1)
if N % 4 in [0, 1]:
	print(N // 4 * 2, end=' ')
else:
	print(N // 4 * 2 + 1, end=' ')
while N >= 4:
	print(N, N - 3, end=' ')
	N -= 4
if N == 3:
	print(3, end=' ')
if N == 2:
	print(2, end=' ')


n = int(input())
l = [x for x in range(1, n + 1)]
a = []
b = []
a.append(l.pop())
while l:
	b.append(l.pop())
	if l:
		b.append(l.pop())
		if l:
			a.append(l.pop())
			if l:
				a.append(l.pop())
x = n % 4
if x == 0 or x == 3:
	print(0)
else:
	print(1)
print(len(a), end=' ')
for i in a:
	print(i, end=' ')


n = int(input())
if n % 4 == 0:
	print(0)
	ans = []
	x = 1
	for i in range(n // 4):
		ans.append(x)
		ans.append(n + 1 - x)
		x += 1
	print(len(ans), *ans)
elif n % 4 == 1:
	x = 2
	ans = []
	print(1)
	for i in range(n // 4):
		ans.append(x)
		ans.append(n + 2 - x)
		x += 1
	print(len(ans), *ans)
elif n % 4 == 2:
	x = 3
	ans = [2]
	print(1)
	for i in range(n // 4):
		ans.append(x)
		ans.append(n + 3 - x)
		x += 1
	print(len(ans), *ans)
else:
	print(0)
	x = 4
	ans = [3]
	for i in range(n // 4):
		ans.append(x)
		ans.append(n + 4 - x)
		x += 1
	print(len(ans), *ans)


n = int(input())
arr = []
(left, right) = (0, 0)
for i in range(n, 0, -1):
	if left >= right:
		right += i
	else:
		left += i
		arr.append(i)
print(abs(right - left))
print(len(arr), *arr)


n = int(input())

def getg(n):
	if n % 4 == 0:
		return (0, list(range(n // 4 + 1, 3 * n // 4 + 1)))
	elif n % 4 == 1:
		return (1, [1] + [x + 1 for x in getg(n - 1)[1]])
	elif n % 4 == 2:
		return (1, getg(n - 2)[1] + [n - 1])
	elif n % 4 == 3:
		return (0, [1] + [x + 1 for x in getg(n - 1)[1]])
g = getg(n)
print(g[0])
print(str(len(g[1])) + ' ' + ' '.join((str(x) for x in g[1])))


import sys
input = sys.stdin.readline
ins = lambda : input().rstrip()
ini = lambda : int(input().rstrip())
inm = lambda : map(int, input().rstrip().split())
inl = lambda : list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))
n = ini()
count = n * (n + 1) // 2 // 2
ans = []
for i in range(n, 0, -1):
	if count >= i:
		count -= i
		ans.append(i)
	if count == 0:
		break
ans = [len(ans)] + ans
if n * (n + 1) // 2 % 2 == 0:
	print(0)
	print(*ans)
else:
	print(1)
	print(*ans)


t = int(input())
if t % 4 == 0:
	print(0)
	print(t // 2, end=' ')
	for i in range(1, t, 4):
		print(i, i + 3, end=' ')
elif t % 4 == 3:
	print(0)
	print(2 + (t - 3) // 2, 1, 2, end=' ')
	for i in range(4, t, 4):
		print(i, i + 3, end=' ')
elif t % 4 == 1:
	print(1)
	print(1 + (t - 1) // 2, 1, end=' ')
	for i in range(2, t, 4):
		print(i, i + 3, end=' ')
else:
	print(1)
	print(1 + (t - 2) // 2, 1, end=' ')
	for i in range(3, t, 4):
		print(i, i + 3, end=' ')


import sys
n = int(input())
vseh = n * (n + 1) // 2
hit = vseh // 2

def posible(hit, n):
	nums = set()
	maks = n
	while hit > 0:
		if maks > hit:
			maks = hit
		hit -= maks
		nums.add(maks)
		maks -= 1
		if maks <= 0:
			break
	return nums
for k in range(5):
	A = posible(hit - k, n)
	x = vseh - sum(A)
	print(abs(x - sum(A)))
	print(str(len(A)) + ' ' + ' '.join(map(str, A)))
	sys.exit(0)


n = int(input())
m = n % 4
rec = []
if m == 0:
	for i in range(1, n + 1, 4):
		rec.append(i)
	for i in range(4, n + 1, 4):
		rec.append(i)
	rec = sorted(rec)
	print(0)
	print('{} '.format(len(rec)) + ' '.join(map(str, rec)))
elif m == 3:
	for i in range(4, n + 1, 4):
		rec.append(i)
	for i in range(7, n + 1, 4):
		rec.append(i)
	rec = sorted(rec)
	print(0)
	print('{} {} '.format(len(rec) + 1, 3) + ' '.join(map(str, rec)))
elif m == 2:
	for i in range(3, n + 1, 4):
		rec.append(i)
	for i in range(6, n + 1, 4):
		rec.append(i)
	rec = sorted(rec)
	print(1)
	print('{} {} '.format(len(rec) + 1, 2) + ' '.join(map(str, rec)))
else:
	for i in range(2, n + 1, 4):
		rec.append(i)
	for i in range(5, n + 1, 4):
		rec.append(i)
	rec = sorted(rec)
	print(1)
	print('{} {} '.format(len(rec) + 1, 1) + ' '.join(map(str, rec)))


from fractions import gcd
from datetime import date, timedelta
from heapq import *
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def main():
	n = int(input())
	a = n * (n + 1) // 2
	print(a % 2)
	a //= 2
	ansl = []
	for i in range(n, 0, -1):
		if a > i:
			ansl.append(i)
			a -= i
		else:
			break
	if a > 0:
		ansl.append(a)
	ansl.sort()
	print(len(ansl), *ansl)
main()


n = int(input())
if n % 4 == 0:
	print(0)
	data = []
	for i in range(1, n + 1, 4):
		data.append(str(i) + ' ' + str(i + 3))
elif n % 4 == 3:
	print(0)
	data = []
	for i in range(4, n + 1, 4):
		data.append(str(i) + ' ' + str(i + 3))
	data.append('1 2')
elif n % 4 == 1:
	print(1)
	data = []
	for i in range(2, n + 1, 4):
		data.append(str(i) + ' ' + str(i + 3))
	data.append('1')
else:
	print(1)
	data = []
	for i in range(3, n + 1, 4):
		data.append(str(i) + ' ' + str(i + 3))
	data.append('1')
data = ' '.join(data).split()
print(len(data), ' '.join(data))


import sys
n = int(input())
a = []
s1 = 0
s2 = 0
for i in range(n, 0, -1):
	if s1 <= s2:
		s1 += i
		a.append(str(i))
	else:
		s2 += i
print(abs(s1 - s2))
print(len(a), str.join(' ', a))


n = int(input(''))
sol = []
ans = 0
for i in range(n, 0, -1):
	if ans <= 0:
		ans += i
		sol.append(i)
	else:
		ans -= i
print(ans)
print(len(sol), *sol)


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	n = int(input())
	s = n * (n + 1) // 2
	a = s - s // 2
	b = s - a
	if b - a == 0:
		print(0)
	else:
		print(1)
	ans = []
	while b > n:
		ans.append(n)
		b = b - n
		n = n - 1
	ans.append(b)
	print(str(len(ans)) + ' ' + ' '.join([str(x) for x in ans]))
main()


n = int(input())
a = []
b = []
if n > 4:
	for i in range(n, n % 4, -4):
		a.append(i)
		a.append(i - 3)
		b.append(i - 1)
		b.append(i - 2)
	a.sort()
	if a[0] == 3 or a[0] == 2:
		print(1)
		print(len(a) + 1, 1, *a)
	elif a[0] == 1:
		print(0)
		print(len(a), *a)
	else:
		print(0)
		print(len(a) + 2, 1, 2, *a)
elif n == 1 or n == 2:
	print(1)
	print(1, 1)
elif n == 3:
	print(0)
	print(2, 1, 2)
else:
	print(0)
	print(2, 1, 4)


def main():
	n = int(input())
	a_s = 0
	b_s = 0
	ass = []
	bss = []
	for i in range(n, 0, -1):
		if a_s > b_s:
			b_s += i
			bss.append(i)
		else:
			a_s += i
			ass.append(i)
	print(abs(a_s - b_s))
	print(len(ass), end=' ')
	for a in ass:
		print(a, end=' ')
	print()
main()


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
(sa, sb, l) = (0, 0, [])
for i in range(n, 0, -1):
	if sa > sb:
		sb += i
	else:
		sa += i
		l.append(i)
print(abs(sb - sa))
print(len(l), *l)


n = int(input())
x = []
for i in range(1, n + 1):
	x.append(i)
if n % 4 == 0:
	s = n * (n + 1) // 4
	val = 0
	i = len(x) - 1
	ans = []
	while val < s:
		val += x[i]
		ans.append(x[i])
		i -= 1
	ans.pop()
	val -= x[i + 1]
	if s - val > 0:
		ans.append(s - val)
	print(0)
	print(len(ans), end=' ')
	print(*ans)
elif n % 2 == 0:
	s1 = n * (n + 1) // 2
	s = (s1 - 1) // 2
	val = 0
	i = len(x) - 1
	ans = []
	while val < s:
		val += x[i]
		ans.append(x[i])
		i -= 1
	ans.pop()
	val -= x[i + 1]
	if s - val > 0:
		ans.append(s - val)
	print(1)
	print(len(ans), end=' ')
	print(*ans)
else:
	n += 1
	if n % 4 == 0:
		s = n * (n - 1) // 4
		val = 0
		i = len(x) - 1
		ans = []
		while val < s:
			val += x[i]
			ans.append(x[i])
			i -= 1
		ans.pop()
		val -= x[i + 1]
		if s - val > 0:
			ans.append(s - val)
		print(0)
		print(len(ans), end=' ')
		print(*ans)
	elif n % 2 == 0:
		s1 = n * (n - 1) // 2
		s = (s1 - 1) // 2
		val = 0
		i = len(x) - 1
		ans = []
		while val < s:
			val += x[i]
			ans.append(x[i])
			i -= 1
		ans.pop()
		val -= x[i + 1]
		if s - val > 0:
			ans.append(s - val)
		print(1)
		print(len(ans), end=' ')
		print(*ans)


n = int(input())
f = []
f1 = s1 = 0
for i in range(n, 0, -1):
	if f1 <= s1:
		f1 += i
		f.append(i)
	else:
		s1 += i
print(abs(f1 - s1))
print(str(len(f)), *f)


n = int(input())
(s1, s2) = (0, 0)
ans = []
for i in range(n, 0, -1):
	if s1 >= s2:
		s2 += i
		ans.append(i)
	else:
		s1 += i
print(abs(s1 - s2))
print(len(ans), end=' ')
for i in ans:
	print(i, end=' ')


n = int(input())
a = []
b = []
ans1 = ans2 = 0
for i in range(n, 0, -1):
	if ans1 > ans2:
		ans2 += i
		b.append(i)
	else:
		ans1 += i
		a.append(i)
print(abs(ans1 - ans2))
a.sort()
print(len(a), *a)


n = int(input())
if n % 2 == 0:
	if n % 4 == 0:
		print(0)
		print(int(n // 4 * 2), end=' ')
		i = 1
		while i <= n // 4:
			print(str(i) + ' ' + str(n - i + 1), end=' ')
			i += 1
		print()
	else:
		print(1)
		print(int(n // 4 * 2 + 1), end=' ')
		i = 1
		while i <= n / 4:
			print(str(i) + ' ' + str(n - i + 1), end=' ')
			i += 1
		print(int(n // 2))
elif (n + 1) % 4 == 0:
	print(0)
	print(int((n + 1) // 4 * 2), end=' ')
	i = 1
	while i <= (n + 1) // 4:
		if (n + 1) / 4 == i:
			print(str(i) + ' ' + str(int((n + 1) // 2)), end=' ')
		else:
			print(str(i) + ' ' + str(n - i + 1), end=' ')
		i += 1
	print()
else:
	print(1)
	print(str(int((n + 1) // 4 * 2)), end=' ')
	i = 1
	while i <= (n + 1) // 4:
		if (n + 1) // 4 == i:
			print(str(int((n + 1) // 2)) + ' ' + str(n - i + 1), end=' ')
		else:
			print(str(i) + ' ' + str(n - i + 1), end=' ')
		i += 1
	print()


n = int(input())
numbers = [i for i in range(1, n + 1)]
first = 0
second = 0
result = []
for i in range(len(numbers), 0, -1):
	if first > second:
		second += i
	else:
		first += i
		result.append(i)
print(abs(first - second))
result.insert(0, len(result))
print(*result)


import sys

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

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

def iinp():
	return int(input())

def nninp():
	return map(int, sys.stdin.readline().strip().split())

def llinp():
	return list(map(int, sys.stdin.readline().strip().split()))

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
n = iinp()
s = n * (n + 1) // 2
if s % 2 == 0:
	print(0)
	ans = []
	s1 = 0
	for i in range(n, 0, -1):
		if s1 + i <= s // 2:
			ans.append(i)
			s1 = s1 + i
			if s1 == s // 2:
				break
	print(len(ans), *ans)
else:
	print(1)
	ans = []
	s1 = 0
	for i in range(n, 0, -1):
		if s1 + i <= s // 2 + 1:
			ans.append(i)
			s1 += i
			if s1 == s // 2 + 1:
				break
	print(len(ans), *ans)


def main():
	n = int(input())
	all_sum = n * (n + 1) / 2
	mid = int(all_sum / 2)
	out = 0
	if mid * 2 == all_sum:
		out = 0
	else:
		out = 1
	s = 0
	st = ''
	group = []
	for i in reversed(range(1, n + 1)):
		s += i
		if s >= mid:
			s -= i
			group.append(mid - s)
			st += ' ' + str(mid - s)
			break
		group.append(i)
		st += ' ' + str(i)
	print(out)
	print(len(group), st[1:])
main()


n = int(input())
S = n * (n + 1) // 2
a = []
s = S // 2
for i in range(n, 0, -1):
	if s >= i:
		s -= i
		a.append(i)
print(S - sum(a) - sum(a))
print(len(a), ''.join((str(x) + ' ' for x in a)))


n = int(input())
l = list(range(1, n + 1))
a = []
target = n * (n + 1) // 4
accum = 0
for i in reversed(l):
	if accum + i <= target:
		a.append(i)
		accum += i
print(abs(accum - n * (n + 1) // 2 + accum))
print(len(a), ' '.join((str(x) for x in a)))


n = int(input())
x = n * (n + 1) // 2
a = x // 2
b = x - a
c = []
print(abs(b - a))
for i in range(n, 0, -1):
	if i <= a:
		a -= i
		c.append(i)
print(len(c), end=' ')
for i in c:
	print(i, end=' ')


n = int(input())
Sum = n * (n + 1)
Sum = int(Sum / 2)
l = []
if Sum % 2 == 0:
	print(0)
else:
	print(1)
Sum = int(Sum / 2)
sz = 0
while 1:
	if Sum <= n:
		l.append(Sum)
		print(sz + 1, end=' ')
		break
	else:
		l.append(n)
		Sum -= n
		n -= 1
		sz += 1
for i in l:
	print(i, end=' ')


n = int(input())
out = []
while n >= 4:
	out += [n, n - 3]
	n -= 4
diff = 0
if n == 3:
	out += [3]
elif n == 2:
	out += [1]
	diff = 1
elif n == 1:
	diff = 1
print(diff)
print(' '.join(map(str, [len(out)] + out)))


n = int(input())
d = n
for i in range(n):
	d += i
h = d >> 1
a = []
t = n
s = 0
while h:
	if t <= h:
		h -= t
		s += t
		a.append(t)
	t = min(t - 1, h)
print(abs(d - s * 2))
print(len(a), end=' ')
print(*a)


a = []
for i in range(5, 60001, 4):
	a.append(i)
for i in range(2, 60001, 4):
	a.append(i)
x = int(input())
jumlah = x * (x + 1) // 2
h = 0
hsl = []
if x not in a:
	print(0)
	jml = jumlah // 2
	for i in range(x, 0, -1):
		if jml >= i:
			hsl.append(i)
			h += 1
			jml -= i
		if jml <= 0:
			break
	print(h, end=' ')
	for i in hsl:
		print(i, end=' ')
else:
	print(1)
	jml = jumlah // 2 + 1
	for i in range(x, 0, -1):
		if jml >= i:
			hsl.append(i)
			h += 1
			jml -= i
		if jml <= 0:
			break
	print(h, end=' ')
	for i in hsl:
		print(i, end=' ')
print()


n = int(input())
f = 0
l = 0
arr = []
for i in range(n, 0, -1):
	if f <= l:
		f += i
		arr.append(i)
	else:
		l += i
print(abs(f - l))
print(len(arr), *arr)


n = int(input())
s = n * (n + 1) // 2
if s % 2 == 0:
	print(0)
else:
	print(1)
s //= 2
ans = []
while s >= 0:
	if s - n >= 0:
		ans.append(n)
		s -= n
	else:
		if s != 0:
			ans.append(s)
		print(len(ans), *ans)
		exit()
	n -= 1


n = int(input().strip())
(l1, l2) = ([], [])
(s1, s2) = (0, 0)
for i in range(n, 0, -1):
	if s1 < s2:
		s1 += i
		l1.append(i)
	else:
		s2 += i
		l2.append(i)
print(abs(s1 - s2))
print(len(l1), end=' ')
for i in l1:
	print(i, end=' ')


n = int(input())
s = (n + 1) * n // 4
a = []
for i in range(n, 0, -1):
	if s >= i:
		a.append(i)
		s -= i
print(abs((n + 1) * n // 2 - sum(a) - sum(a)))
print(len(a), end=' ')
for x in a:
	print(x, end=' ')


n = int(input())
t = n * (n + 1) // 2
if t % 2 == 0:
	print(0)
	t = t // 2
else:
	print(1)
	t = t // 2
i = n
ans = []
while t - i > 0:
	t -= i
	ans.append(i)
	i -= 1
print(len(ans) + 1, end=' ')
ans.append(t)
for i in ans:
	print(i, end=' ')


n = int(input())
goal = n * (n + 1) >> 1
ans = 1 if goal & 1 == 1 else 0
lis = ''
cnt = 0
goal >>= 1
while goal > 0:
	if goal > n:
		goal -= n
		lis += ' ' + str(n)
		n -= 1
	else:
		lis += ' ' + str(goal)
		goal = 0
	cnt += 1
print(ans)
print(str(cnt) + lis)


def flip(n):
	if n:
		return 0
	else:
		return 1
n = int(input(''))
ans = [0, 1, 1]
for i in range(3, 60002):
	if ans[i - 1] == ans[i - 2]:
		ans.append(flip(ans[i - 1]))
	else:
		ans.append(ans[i - 1])
sol = []
a = 0
for i in range(n, 0, -1):
	if a <= 0:
		a += i
		sol.append(i)
	else:
		a -= i
print(ans[n])
print(len(sol), *sol)


n = int(input())
s = sum(range(1, n + 1))
s2 = 0
result = []
for i in range(n, 0, -1):
	if s - i >= s2 + i:
		s -= i
		s2 += i
		result.append(i)
print(s - s2)
st = str(len(result)) + ' '
for i in result:
	st += str(i) + ' '
print(st)


n = int(input())
g1 = []
g2 = []
s1 = s2 = n1 = 0
for i in range(n, 0, -1):
	if s1 <= s2:
		g1.append(i)
		s1 += i
		n1 += 1
	else:
		g2.append(i)
		s2 += i
print(abs(s1 - s2))
print(n1, end=' ')
print(' '.join((f'{a}' for a in g1)))


n = int(input())
a = [x for x in range(1, n + 1)]
suma = sum(a)
ans = []
if suma % 2 != 0 or n == 2:
	print(1)
else:
	print(0)
req = suma // 2
for i in range(n, 0, -1):
	if i > req:
		if req == 0:
			break
		ans.append(req)
		break
	ans.append(i)
	req -= i
print(len(ans), *ans)


n = int(input())
all = (n + 1) * n // 2
x = n
ans = 0
while ans + x < all / 2:
	ans += x
	x -= 1
m = [i for i in range(x + 1, n)]
if all % 2 == 1:
	print(1)
else:
	print(0)
s = ''
for i in range(x + 1, n + 1):
	s += str(i) + ' '
if all // 2 != ans:
	print(n - x + 1, s + str(all // 2 - ans))
else:
	print(n - x, s[:-1])


n = int(input())
sum = n * (1 + n) / 4
v = []
p = []
sum_v = 0
sum_p = 0
for i in range(n, 0, -1):
	if sum_v + i <= sum:
		sum_v += i
		v.append(i)
	else:
		sum_p += i
if sum_v >= sum_p:
	print(sum_v - sum_p)
else:
	print(sum_p - sum_v)
print(len(v), end=' ')
for x in v:
	print(x, end=' ')
print()


n = int(input())
(res, sum, total) = ([], 0, n * (n + 1) // 2)
for i in range(n, 0, -1):
	if sum + i <= total // 2:
		sum += i
		res += [i]
print(total - 2 * sum)
print(len(res), end=' ')
for i in res:
	print(i, end=' ')


def case_not_4(n):
	res = n * (n + 1) // 4
	a = []
	s = res
	i = n
	while s != 0:
		if s >= i:
			s -= i
			a.append(i)
		i -= 1
	if res * 4 == n * (n + 1):
		print(0)
	else:
		print(1)
	print(len(a), end=' ')
	for i in a:
		print(i, end=' ')
n = int(input())
case_not_4(n)


n = int(input())
a = list(range(1, n + 1))
Sum = sum(a)
k = Sum // 2
nums = []
for i in range(n, 0, -1):
	if k >= i:
		k -= i
		nums.append(i)
print(Sum % 2)
print(len(nums), ''.join((str(x) + ' ' for x in nums)))


n = int(input())
s = int(n * (n + 1) / 2)
med = int(s / 2)
i = n
group = []
while med != 0:
	if med >= i:
		med -= i
		group.append(str(i))
	i -= 1
print(s % 2)
l = len(group)
print(l, ' '.join(group))


n = int(input())
summa = (n + n * n) // 2 // 2
i = 0
s = 0
a = ''
while True:
	if s + n - i > summa:
		break
	s += n - i
	a = a + str(n - i) + ' '
	i += 1
if summa - s == 0:
	i -= 1
if (n + n * n) // 2 % 2 == 0:
	print(0)
else:
	print(1)
if len(a) == 0:
	print(i + 1, summa - s)
elif summa - s == 0:
	print(i + 1, a[0:-1])
else:
	print(i + 1, a[0:-1], summa - s)


from sys import stdin, stdout
from collections import Counter

def ai():
	return list(map(int, input().split()))

def ei():
	return map(int, input().split())

def ip():
	return int(stdin.readline())

def op(ans):
	return stdout.write(str(ans) + '\n')
n = ip()
r = l = 0
li = []
for i in range(n, 0, -1):
	if r < l:
		r += i
	else:
		l += i
		li.append(i)
print(abs(r - l))
print(len(li), *li)


n = int(input())
if n % 2 == 0:
	x = n // 2
	if x % 2 == 0:
		print(0)
	else:
		print(1)
	arr1 = []
	arr2 = []
	cnt = 0
	for i in range(1, n + 1, 2):
		if cnt == 0:
			arr1.append(i)
			arr2.append(i + 1)
			cnt = cnt ^ 1
		else:
			arr1.append(i + 1)
			arr2.append(i)
			cnt = cnt ^ 1
	print(len(arr1), *arr1)
else:
	x = n - 1
	x = x // 2
	if x % 2 == 0:
		print(1)
	else:
		print(0)
	arr1 = []
	arr2 = []
	cnt = 0
	for i in range(2, n + 1, 2):
		if cnt == 0:
			arr1.append(i)
			arr2.append(i + 1)
			cnt = cnt ^ 1
		else:
			arr1.append(i + 1)
			arr2.append(i)
			cnt = cnt ^ 1
	if sum(arr1) <= sum(arr2):
		arr1.append(1)
		print(len(arr1), *arr1)
	else:
		arr2.append(1)
		print(len(arr2), *arr2)


n = int(input())
l = [x for x in range(1, n + 1)]
g1 = []
g2 = []
if n % 2 == 1:
	l = l[1:]
	a = l[:len(l) // 2]
	b = l[len(l) // 2:]
	b.reverse()
	if len(a) % 2 == 1:
		for x in range(len(a) - 1):
			if x % 2 == 0:
				g1.append(a[x])
				g1.append(b[x])
			else:
				g2.append(a[x])
				g2.append(b[x])
		g1.append(a[len(a) - 1])
		g2.append(b[len(a) - 1])
	else:
		for x in range(len(a)):
			if x % 2 == 0:
				g1.append(a[x])
				g1.append(b[x])
			else:
				g2.append(a[x])
				g2.append(b[x])
	sumg1 = sum(g1)
	sumg2 = sum(g2)
	if sumg1 < sumg2:
		g1.append(1)
		sumg1 += 1
	else:
		g2.append(1)
		sumg2 += 1
	print(abs(sumg1 - sumg2))
	print(len(g1), end=' ')
	for z in g1:
		print(z, end=' ')
else:
	a = l[:len(l) // 2]
	b = l[len(l) // 2:]
	b.reverse()
	if len(a) % 2 == 1:
		for x in range(len(a) - 1):
			if x % 2 == 0:
				g1.append(a[x])
				g1.append(b[x])
			else:
				g2.append(a[x])
				g2.append(b[x])
		g1.append(a[len(a) - 1])
		g2.append(b[len(a) - 1])
	else:
		for x in range(len(a)):
			if x % 2 == 0:
				g1.append(a[x])
				g1.append(b[x])
			else:
				g2.append(a[x])
				g2.append(b[x])
	sumg1 = sum(g1)
	sumg2 = sum(g2)
	print(abs(sumg1 - sumg2))
	print(len(g1), end=' ')
	for z in g1:
		print(z, end=' ')


x = int(input())
s = [*range(1, x + 1)]
s = s[::-1]
k = x * (x + 1) // 2
if k % 2 == 0:
	print(0)
else:
	print(1)
p = k // 2
c = 0
i = 0
lol = []
while c < p:
	if c + s[i] <= p:
		c += s[i]
		lol.append(s[i])
	i += 1
print(len(lol), *lol)


n = int(input())
sum_of_n = n * (n + 1) / 2
modulo = int(sum_of_n % 2)
sum_of_n = int(sum_of_n / 2) if modulo == 0 else int(sum_of_n // 2)
print(str(modulo))
digits = []
while sum_of_n != 0:
	if sum_of_n >= n:
		digits.append(str(n))
		sum_of_n -= n
		n -= 1
	else:
		digits.append(str(sum_of_n))
		sum_of_n -= sum_of_n
print(str(len(digits)), ' '.join(digits))


n = int(input())
elementos = 0
sum = n * (n + 1) // 2
if sum % 2 == 0:
	print(0)
else:
	print(1)
num = n
halfsum = sum // 2
while halfsum - num >= 0:
	elementos += 1
	halfsum -= num
	num -= 1
if halfsum > 0:
	print(elementos + 1, halfsum, end=' ')
else:
	print(elementos, end=' ')
for i in range(n - (elementos - 1), n + 1):
	print(i, end=' ')
print()


N = int(input())
arr1 = []
sum1 = 0
sum2 = 0
for val in range(1, N + 1)[::-1]:
	if sum1 > sum2:
		sum2 += val
	else:
		sum1 += val
		arr1.append(val)
print(abs(sum1 - sum2))
print(len(arr1), end=' ')
print(*arr1)


n = int(input())
s = n
i = n - 1
g = [n]
while i > 0:
	if s > 0:
		s -= i
	else:
		s += i
		g.append(i)
	i -= 1
print(s)
print(len(g), end=' ')
print(*g)


from sys import stdin as cin
from sys import stdout as cout

def main():
	n = int(cin.readline())
	if n % 4 == 0:
		print(0)
		print(n // 2, end='')
		for i in range(n // 4):
			print('', i * 4 + 1, i * 4 + 4, end='')
	elif n % 2 == 0:
		print(1)
		print(n // 2, end='')
		for i in range((n - 2) // 4):
			print('', i * 4 + 1, i * 4 + 4, end='')
		print('', n - 1)
	elif n % 4 == 1:
		print(1)
		print(n // 2, end='')
		for i in range((n - 1) // 4):
			print('', i * 4 + 2, i * 4 + 5, end='')
	else:
		print(0)
		print(n // 2, 3, end='')
		for i in range((n - 3) // 4):
			print('', i * 4 + 4, i * 4 + 7, end='')
main()


from sys import stdin, setrecursionlimit, stdout
setrecursionlimit(100)
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
from heapq import heapify, heappop, heappush, heapreplace, heappushpop
from bisect import bisect_right, bisect_left

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline().rstrip()

def lsi():
	return list(si())
mod = 1000000007
res = ['NO', 'YES']
test = test_case = 1
while test <= test_case:
	test += 1
	n = ii()
	x = n * (n + 1) // 4
	print(n * (n + 1) // 2 - x - x)
	a = []
	for i in range(n, 0, -1):
		if i <= x:
			a.append(i)
			x -= i
			if not x:
				break
	print(len(a), *a)


n = int(input())
(a, b, r) = (0, 0, [])
for i in range(n, 0, -1):
	if a > b:
		b += i
	else:
		a += i
		r += [i]
print(abs(a - b))
print(len(r), *r)


n = int(input().strip())
if n % 2 == 1:
	print((n + 1) // 2 % 2)
	print((n + 1) // 2, end=' ')
	i = 1
	while i <= n:
		if i < n:
			print(i, i + 1, end=' ')
		else:
			print(i, end=' ')
		i += 4
	print()
else:
	print(n // 2 % 2)
	print(n // 2, 1, end=' ')
	i = 4
	while i <= n:
		if i < n:
			print(i, i + 1, end=' ')
		else:
			print(i, end=' ')
		i += 4
	print()


import sys
n = int(sys.stdin.readline().split(' ')[0])
small_cases = {}
small_cases[1] = [[1], 1]
small_cases[2] = [[1], 1]
small_cases[3] = [[1, 2], 0]
small_cases[4] = [[1, 4], 0]

def mod_4(m):
	set1 = []
	for j in range(1, m + 1):
		if j <= int(m / 4) or j > int(3 * m / 4):
			set1.append(j)
	return set1
result = []
if n % 4 == 0:
	result = [0, mod_4(n)]
else:
	k = n % 4
	set1 = mod_4(n - k)
	set2 = small_cases[k]
	result.append(set2[1])
	result_set = [set1[j] + k for j in range(len(set1))]
	for j in range(len(set2[0])):
		result_set.append(set2[0][j])
	result.append(result_set)
output = str(len(result[1])) + ' '
for j in range(len(result[1])):
	output += str(result[1][j])
	if j < len(result[1]) - 1:
		output += ' '
print(result[0])
print(output)


n = int(input())
sum = n * (n + 1) // 2
req = sum // 2
l = [n]
s = n
curr = n - 1
while s + curr < req:
	s += curr
	l.append(curr)
	curr -= 1
if s < req:
	l.append(req - s)
if sum % 2 == 0:
	print(0)
else:
	print(1)
print(len(l), end=' ')
print(*l)


for t in range(1):
	n = int(input())
	sum1 = 0
	sum2 = 0
	arr1 = []
	arr2 = []
	for i in range(n, 0, -1):
		if sum1 >= sum2:
			sum2 += i
			arr2.append(i)
		else:
			sum1 += i
			arr1.append(i)
	print(abs(sum1 - sum2))
	print(len(arr1), *arr1)


class CodeforcesTask899CSolution:

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

	def read_input(self):
		self.n = int(input())

	def process_task(self):
		if not self.n % 4:
			sol = []
			for x in range(self.n // 4):
				sol.append(x + 1)
				sol.append(self.n - x)
			self.result = '0\n{0} {1}'.format(len(sol), ' '.join([str(x) for x in sol]))
		elif not self.n % 2:
			sol = []
			for x in range(self.n // 4):
				sol.append(x + 1)
				sol.append(self.n - x)
			sol.append(self.n // 2)
			self.result = '1\n{0} {1}'.format(len(sol), ' '.join([str(x) for x in sol]))
		elif self.n % 4 == 3:
			sol = []
			for x in range(self.n // 4):
				sol.append(x + 1)
				sol.append(self.n - x)
			sol.append(self.n - self.n // 4)
			self.result = '{2}\n{0} {1}'.format(len(sol), ' '.join([str(x) for x in sol]), 0)
		else:
			sol = []
			for x in range(self.n // 4):
				sol.append(x + 1)
				sol.append(self.n - x)
			sol.append(self.n // 4 + 1)
			self.result = '{2}\n{0} {1}'.format(len(sol), ' '.join([str(x) for x in sol]), 1)

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


n = int(input())
if (n + 1) * n // 2 % 2 == 0:
	print(0)
else:
	print(1)
left = 0
right = 0
ans = []
for i in range(n, 0, -1):
	if left < right:
		left += i
		ans.append(i)
	else:
		right += i
print(len(ans), *ans)


def findTwoGroup(n):
	s = n * (n + 1) / 2
	group1Sum = s / 2
	group1 = []
	group2 = []
	for i in range(n, 0, -1):
		if group1Sum - i >= 0:
			group1.append(i)
			group1Sum -= i
		else:
			group2.append(i)
	print(abs(sum(group1) - sum(group2)))
	group1.sort()
	print(len(group1), *group1)
n = int(input())
findTwoGroup(n)


n = int(input())
(s1, s2) = (n * (n + 1) // 2, 0)
res = []
for i in range(n, 0, -1):
	if s2 + i <= s1 - i:
		s1 -= i
		s2 += i
		res.append(i)
print(s1 - s2)
print(len(res), *res)


import math
n = int(input())
sum = n * (n + 1) / 2
sum1 = math.ceil(sum / 2)
sum2 = math.floor(sum / 2)
diff = abs(sum1 - sum2)
group1 = []
for i in range(n, 0, -1):
	if sum1 - i == 0:
		group1.append(i)
		break
	elif sum1 - i > 0:
		sum1 -= i
		group1.append(i)
print(diff)
print(len(group1), end=' ')
for num in group1:
	print(num, end=' ')
print('')


n = int(input())
whSumv = n * (n + 1) // 2
sumv = 0
ans = []
for i in reversed(range(1, n + 1)):
	if sumv + i <= whSumv // 2:
		sumv += i
		ans += [i]
print(abs(whSumv - sumv - sumv))
print(len(ans), ' '.join(map(str, ans)))


n = int(input())
if n % 4 == 0:
	print('0')
	print(n // 2)
	for i in range(1, n + 1):
		if i % 4 == 1 or i % 4 == 0:
			print(i)
elif n % 4 == 1:
	print('1')
	print(n // 2 + 1)
	for i in range(1, n + 1):
		if i % 4 == 1 or i % 4 == 2:
			print(i)
elif n % 4 == 2:
	print('1')
	print(n // 2)
	for i in range(1, n + 1):
		if i % 4 == 1 or i % 4 == 0:
			print(i)
else:
	print('0')
	print(n // 2 + 1)
	for i in range(1, n + 1):
		if i % 4 == 1 or i % 4 == 2:
			print(i)


n = int(input())
s = n * (n + 1) // 2
print(s & 1)
s //= 2
ans = []
for i in range(n, 0, -1):
	if s - i >= 0:
		ans.append(i)
		s -= i
print(len(ans), *ans)


n = int(input())
a = [i for i in range(1, n + 1)]
b = n // 4
c = n % 4
B = [i for i in range(c + 1, 4 * b + c + 1)]
kk = []
for i in range(1, b + 1):
	hhh = 4 * i - 1
	hhhh = 4 * i - 4
	kk.append(B[hhh])
	kk.append(B[hhhh])
if c == 0:
	d = 0
elif c == 1:
	kk.append(1)
	d = 1
elif c == 2:
	d = 1
	kk.append(1)
elif c == 3:
	kk.append(3)
	d = 0
kk.sort()
k = len(kk)
print(d)
print(k, end=' ')
for i in range(0, k):
	print(kk[i], end=' ')


def read_int():
	return int(input())

def read_str():
	return input()

def read_list(type):
	return list(map(type, input().split()))

def print_list(x):
	print(len(x), ' '.join(map(str, x)))

def f(arr):
	r = []
	for (x, y) in zip(arr, arr[::-1]):
		r.extend([x, y])
	return r[:len(arr) // 2]
n = read_int()
mod = n % 4
print((mod + 1) % 4 // 2)
arr = list(range(1, n + 1))
res = f(arr[mod:])
if mod:
	res += arr[:mod - 1]
print_list(res)


def main():
	N = int(input())
	sum_ = N * (N + 1) // 2
	if sum_ & 1:
		diff = 1
	else:
		diff = 0
	if N & 1:
		start = 2
		group = [1]
	else:
		start = 1
		group = []
	mid = (start + N + 1) // 2
	group.extend([i for i in range(start, mid, 2)])
	group.extend([i for i in range(N, mid, -2)])
	print(diff)
	print(len(group), end=' ')
	print(*group, sep=' ')
main()


n = int(input())
s = n * (n + 1) // 2
A = []
x = 0
for a in reversed(range(1, n + 1)):
	if x + a <= s // 2:
		A.append(a)
		x += a
print(s % 2)
print(len(A), *A)


n = int(input())
res = []
app = res.append
if n % 2 == 1:
	for i in range(2, n // 2 + 1, 2):
		app(i)
		app(n - i + 2)
	if n // 2 % 2 == 1:
		app(n // 2 + 2)
else:
	for i in range(1, n // 2, 2):
		app(i)
		app(n - i + 1)
	if n // 2 % 2 == 1:
		app(n // 2)
res.sort()
print(n * (n + 1) // 2 % 2)
print(len(res), *res)


n = int(input())
res = n % 4
if res == 0:
	d = 0
	nl = list(range(1, n + 1, 4)) + list(range(4, n + 1, 4))
elif res == 3:
	d = 0
	nl = [1, 2] + list(range(4, n + 1, 4)) + list(range(7, n + 1, 4))
elif res == 1:
	d = 1
	nl = list(range(2, n + 1, 4)) + list(range(5, n + 1, 4))
else:
	d = 1
	nl = [1] + list(range(3, n + 1, 4)) + list(range(6, n + 1, 4))
print(d)
print(len(nl), end=' ')
print(' '.join(map(str, nl)))


n = int(input())
ans = []
if n * (n + 1) % 4 == 0:
	a = [i + 1 for i in range(n)]
	if n % 2 == 0:
		a = [i + 1 for i in range(n)]
		for i in range(0, n // 2, 2):
			ans.append(a[i])
			ans.append(a[n - i - 1])
		print(0)
		print(len(ans), end=' ')
		for i in ans:
			print(i, end=' ')
	else:
		a = [i + 1 for i in range(n - 1)]
		for i in range(0, (n - 1) // 2, 2):
			ans.append(a[i])
			ans.append(a[n - i - 2])
		print(0)
		print(len(ans), end=' ')
		for i in ans:
			print(i, end=' ')
else:
	a = [i + 1 for i in range(n)]
	if n % 2 == 0:
		for i in range(0, n // 2 - 1, 2):
			ans.append(a[i])
			ans.append(a[n - i - 1])
		print(1)
		ans.append(a[n // 2])
		print(len(ans), end=' ')
		for i in ans:
			print(i, end=' ')
	else:
		a = [i + 1 for i in range(1, n)]
		for i in range(0, (n - 1) // 2, 2):
			ans.append(a[i])
			ans.append(a[n - i - 1 - 1])
		print(1)
		ans.append(1)
		print(len(ans), end=' ')
		for i in ans:
			print(i, end=' ')


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())

def solve(s, l):
	a = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
	for i in range(len(l)):
		if l[i] != a[s]:
			return 0
		s += 1
		s %= 12
	return 1
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = 0
b = 0
l = []
for i in range(n, 0, -1):
	if a > b:
		b += i
	else:
		a += i
		l.append(i)
print(abs(a - b))
print(len(l), *l)


n = int(input())
remainder_n = n % 4
answer = []
if remainder_n == 0:
	print(0)
	for i in range(1, n + 1):
		if i % 4 == 0 or i % 4 == 1:
			answer.append(i)
elif remainder_n == 1:
	print(1)
	for i in range(1, int(n / 4) + 2):
		answer.append(i)
	for i in range(n - int(n / 4) + 1, n + 1):
		answer.append(i)
elif remainder_n == 2:
	print(1)
	for i in range(1, n + 1):
		if i % 4 == 0 or i % 4 == 1:
			answer.append(i)
else:
	print(0)
	for i in range(1, int(n / 4) + 1):
		answer.append(i)
	for i in range(n - int(n / 4), n + 1):
		answer.append(i)
answer = str(len(answer)) + ' ' + str(answer).replace('[', '').replace(']', '').replace(',', '')
print(answer)


n = int(input())
a = list(reversed([1 if i % 2 != 0 else 0 for i in range(int((n + 1) / 2)) for j in range(2)]))[1:] + [1]
b = [1 if i % 2 == 0 else 0 for i in range(int((n + 1) / 2)) for j in range(2)]
if n % 2 != 0:
	a = a[1:]
	b = b[:-1]
dif = b[n - 1]
list_ = []
for (index, i) in enumerate(a):
	if (index + 1) * i != 0:
		list_.append((index + 1) * i)
digits = '{} '.format(len(list_))
for d in list_:
	digits = digits + '{} '.format(d)
print(dif)
print(digits[:-1])


n = int(input())
numbers = []
for i in range(0, n):
	numbers.append(i + 1)
group1 = []
group2 = []
while numbers:
	if numbers:
		group1.append(numbers[len(numbers) - 1])
		numbers.pop()
	if numbers:
		group2.append(numbers[len(numbers) - 1])
		numbers.pop()
	if numbers:
		group2.append(numbers[len(numbers) - 1])
		numbers.pop()
	if numbers:
		group1.append(numbers[len(numbers) - 1])
		numbers.pop()
sum1 = sum(group1)
sum2 = sum(group2)
print(abs(sum1 - sum2))
print(len(group1), *group1)


n = int(input())
a = []
b = []
a.append(n)
b.append(n - 1)
c1 = n
c2 = n - 1
k = n - 2
while k > 0:
	if abs(k + c1 - c2) < abs(k + c2 - c1):
		a.append(k)
		c1 += k
	else:
		b.append(k)
		c2 += k
	k -= 1
s = ''
for i in a:
	s += str(i) + ' '
print(abs(c1 - c2))
print(str(len(a)) + ' ' + s)


n = int(input())
h = n * (n + 1) // 4
used = []
high = n
while h > 0 and high <= h:
	h -= high
	used.append(high)
	high -= 1
if h:
	used.append(h)
print(n * (n + 1) // 2 % 2)
print(len(used), *used)


import math
n = int(input())
k = n * (n + 1) // 2
if k % 2 == 0:
	print('0')
else:
	print('1')
m = k // 2
c = math.ceil((4 * m + 1) ** (1 / 2) - 1)
a = list(range(1, c + 1))
z = c * (c + 1) // 2
x = 0
while True:
	if z - m > c - x:
		z -= a[-1]
		del a[-1]
		x += 1
	else:
		del a[z - m - 1]
		x += 1
		break
print(c - x, end=' ')
print(*a)


n = int(input())
sum = n * (n + 1) // 2
print(sum & 1)
sum = sum // 2
ans = []
len = 0
while n > 0:
	if sum >= n:
		sum -= n
		ans.append(n)
		len += 1
	n -= 1
print(len, end=' ')
for i in range(len):
	print(ans[i], end=' ')


n = int(input())
if n == 2:
	print(1)
	print('1 1')
	exit()
dif = from_pos = to_pos = 0
mod = n % 4
if mod == 0 or mod == 3:
	from_pos = n // 4 + 1
	if mod == 0:
		to_pos = from_pos + n // 2
	else:
		to_pos = from_pos + n // 2 + 1
else:
	dif = 1
	if mod == 1:
		from_pos = n // 4 + 2
		to_pos = from_pos + n // 2
	else:
		from_pos = n // 4
		to_pos = from_pos + n // 2 + 1
print(dif)
print(to_pos - from_pos, ' '.join(map(str, range(from_pos, to_pos))))


from collections import Counter
n = int(input())
z = 0
for i in range(n + 1):
	z = z + i
print(z % 2)
z = 3
s = 1
a = {1}
for i in range(3, n + 1):
	d = (z + i) // 2 - s
	if d in a:
		a.remove(d)
		a.add(i)
	else:
		a.add(d)
a = list(a)
a.sort()
print(len(a), *a)


n = int(input())
AnsList = []
X = int(n * (n + 1) / 2)
if X % 2 == 0:
	print(0)
else:
	print(1)
Sum = 0
Till = int(X // 2)
for i in range(n, 0, -1):
	Sum += i
	if Sum < Till:
		AnsList.append(i)
	else:
		Sum -= i
		break
AnsList.append(Till - Sum)
AnsList.insert(0, len(AnsList))
print(*AnsList)


n = int(input())
a = n * (n + 1) // 2
if a % 2 == 0:
	print(0)
else:
	print(1)
l1 = set()
l2 = set()
sum1 = 0
sum2 = 0
for i in range(n, 0, -1):
	if sum1 >= sum2:
		sum2 += i
	else:
		sum1 += i
		l1.add(i)
print(len(l1), *l1)


n = int(input())
(x, y) = (0, 0)
l = []
for i in range(n, 0, -1):
	if x > y:
		y += i
	else:
		x += i
		l.append(i)
print(abs(x - y))
print(len(l), *l)


n = int(input())
if n == 2:
	print(1)
	print(1, 1)
else:
	sum = n * (n + 1) / 2 / 2
	one = 0
	k = 0
	ans = []
	while one + n - k <= sum:
		one += n - k
		ans.append(n - k)
		k += 2
	l = n - k
	for i in range(l, 0, -1):
		if one + i <= sum:
			one += i
			ans.append(i)
	if 4 * one == n * (n + 1):
		print(0)
	else:
		print(1)
	print(len(ans), end=' ')
	for i in ans:
		print(i, end=' ')


n = int(input())
fib_sum = 0
for value in range(1, n + 1):
	fib_sum += value
is_diff = False
if fib_sum % 2 == 1:
	fib_sum -= 1
	is_diff = True
fib_sum //= 2
group1 = []
while fib_sum != 0:
	if fib_sum - n < 0:
		n -= 1
		continue
	fib_sum -= n
	group1.append(n)
	n -= 1
if is_diff:
	print(1)
else:
	print(0)
group1 = [str(x) for x in group1]
print(len(group1), ' '.join(group1))


n = int(input())

def flatten(l):
	return [item for sublist in l for item in sublist]

def join(l):
	return ' '.join(map(str, l))
if n % 4 == 0:
	print(0)
	print(join([n // 2] + flatten([[i + 1, n - i] for i in range(n // 4)])))
elif n % 4 == 1:
	print(1)
	print(join([n // 2] + flatten([[i + 2, n - i] for i in range(n // 4)])))
elif n % 4 == 2:
	print(1)
	print(join([n // 2, 1] + flatten([[i + 3, n - i] for i in range(n // 4)])))
elif n % 4 == 3:
	print(0)
	print(join([n // 2 + 1, 1, 2] + flatten([[i + 4, n - i] for i in range(n // 4)])))


n = int(input())
r = n % 4
if r == 0 or r == 3:
	print(0)
else:
	print(1)
a = range(1, n + 1)[r:]
d = {0: 0, 1: 0, 2: 1, 3: 1}
ans = [len(a) // 2 + d[r]]
for i in range(len(a) // 4):
	ans.append(a[i * 4])
	ans.append(a[i * 4 + 3])
d = {0: [], 1: [], 2: [1], 3: [3]}
ans += d[r]
print(' '.join([str(i) for i in ans]))


n = int(input())
group1 = []
g1Sum = 0
group2 = []
g2Sum = 0
turn = 1
j = n
while j >= 1:
	if turn == 1:
		group1.append(j)
		g1Sum += j
	elif turn == 2:
		group2.append(j)
		g2Sum += j
	if g1Sum <= g2Sum:
		turn = 1
	else:
		turn = 2
	j -= 1
string = ''
for i in group1:
	string += str(i) + ' '
dif = g1Sum - g2Sum
if dif < 0:
	dif = dif * -1
print(dif)
print(len(group1), string)


n = int(input())
decide = list(range(1, n % 4 + 1))
n_sum = 0
first_group = []
if n % 4 == 1:
	n_sum = 1
if n % 4 == 2:
	n_sum = 1
	first_group.append(2)
if n % 4 == 3:
	n_sum = 0
	first_group.append(3)
k = n
while k > 3:
	first_group.append(k)
	first_group.append(k - 3)
	k -= 4
print(n_sum)
print(len(first_group), *first_group)


n = int(input())
print((n + 1) * n // 2 % 2)
k = 0
L = []
for i in range(n, 0, -2):
	k += 1
	if k % 2:
		ans = i
	else:
		ans = i - 1
	if ans:
		L.append(ans)
print(len(L), end=' ')
for i in range(len(L)):
	print(L[i], end=' ')


n = int(input())
group_1 = []
sum_group_1 = 0
sum_group_2 = 0
for number in range(n, 0, -1):
	if sum_group_1 <= sum_group_2:
		group_1.append(str(number))
		sum_group_1 += number
	else:
		sum_group_2 += number
print(abs(sum_group_1 - sum_group_2))
print(len(group_1), end=' ')
print(' '.join(group_1))


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def solve():
	n = ii()
	arr = []
	if n % 4 == 0:
		ans = 0
		for x in range(1, n + 1):
			if x % 4 == 1 or x % 4 == 0:
				arr.append(x)
	if n % 4 == 1:
		ans = 1
		for x in range(1, n + 1):
			if x % 4 == 2 or x % 4 == 1:
				arr.append(x)
	if n % 4 == 2:
		ans = 1
		for x in range(1, n + 1):
			if x % 4 == 3 or x % 4 == 2:
				arr.append(x)
	if n % 4 == 3:
		ans = 0
		for x in range(1, n + 1):
			if x % 4 == 0 or x % 4 == 3:
				arr.append(x)
	print(ans)
	print(len(arr), end=' ')
	print(*arr)
for _ in range(1):
	solve()


n = int(input())
sum = n * (n + 1) / 2
if sum % 2 == 0:
	print(0)
else:
	print(1)
s = ''
count = 0
arr = []
for i in range(1, n + 1):
	arr.append(n - i + 1)
x = []
m = int(sum / 2)
while m > 0:
	count += 1
	if m > arr[0]:
		m -= arr[0]
		x.append(arr[0])
		arr.pop(0)
	else:
		x.append(m)
		break
for i in range(len(x)):
	s = str(x[i]) + ' ' + s
s = ' ' + s
s = str(count) + s
print(s)


n = int(input())
l = range(1, n + 1)
s = (n + 1) * n // 2
print(s % 2)
t = 0
tp = []
pt = -1
while not (s // 2 - t in l and s // 2 - t not in tp):
	t += l[pt]
	tp.append(l[pt])
	pt -= 1
tp.append(s // 2 - t)
print(len(tp), ' '.join((str(i) for i in tp)))


n = int(input())
res_list = []
desired_sum = n * (n + 1) // 2
s = 0
for j in range(n, 0, -1):
	if 2 * (s + j) <= desired_sum:
		s += j
		res_list += [j]
print(desired_sum - 2 * s)
print(str(len(res_list)), ' '.join(map(str, res_list)))


n = int(input())
f = lambda k: ' '.join((f'{i - 3} {i}' for i in range(k, n + 1, 4)))
if n % 4 == 0:
	d = 0
	s = f(4)
elif n % 4 == 1:
	d = 1
	s = '3 5 ' + f(9)
elif n % 4 == 2:
	d = 1
	s = '1 ' + f(6)
else:
	d = 0
	s = '3 ' + f(7)
print(f'{d}\n{n // 2} {s}')


n = int(input())
total = int(n * (n + 1) / 2)
l = []
cur = 0
if total % 2 == 0:
	print(0)
	target = total // 2
	while cur != target:
		if target - cur <= n:
			l.append(target - cur)
			break
		else:
			l.append(n)
			cur += n
			n -= 1
else:
	print(1)
	target = total // 2
	while cur != target:
		if target - cur <= n:
			l.append(target - cur)
			break
		else:
			l.append(n)
			cur += n
			n -= 1
print(len(l), end=' ')
print(*l)


import sys
input = sys.stdin.buffer.readline
import os
from math import *
n = int(input())
s = n * (n + 1) // 2
if s % 2 == 0:
	print('0')
else:
	print('1')
ans = []
s = s // 2
while s >= 1:
	if s <= n:
		ans.append(s)
		break
	else:
		s -= n
		ans.append(n)
		n -= 1
print(len(ans), end=' ')
for x in ans:
	print(x, end=' ')


n = int(input())
group1 = []
sum1 = 0
sum2 = 0
for no in range(n, 0, -1):
	if sum1 <= sum2:
		group1.append(no)
		sum1 += no
	else:
		sum2 += no
print(abs(sum1 - sum2))
print(len(group1), end=' ')
for no in group1:
	print(no, end=' ')


n = int(input())
k = n % 4
grp1 = []
if k == 0:
	for i in range(1, n + 1):
		if i % 4 == 0 or i % 4 == 1:
			grp1.append(i)
	print(0)
	grp1.insert(0, len(grp1))
	print(*grp1)
if k == 1:
	for i in range(1, n + 1):
		if i <= n // 4 + 1 or i >= n - n // 4 + 1:
			grp1.append(i)
	print(1)
	grp1.insert(0, len(grp1))
	print(*grp1)
if k == 2:
	for i in range(1, n + 1):
		if i % 4 == 0 or i % 4 == 1:
			grp1.append(i)
	print(1)
	grp1.insert(0, len(grp1))
	print(*grp1)
if k == 3:
	for i in range(1, n + 1):
		if i <= n // 4 or i >= n - n // 4:
			grp1.append(i)
	print(0)
	grp1.insert(0, len(grp1))
	print(*grp1)