You are given an integer $n$. A set, $\mbox{S}$, of triples $(x_i,y_i,z_i)$ is beautiful if and only if:

$0\leq x_i,y_i,z_i$
$x_i+y_i+z_i=n,\forall i:1\leq i\leq|S|$
Let $\mbox{X}$ be the set of different $x_i$'s in $\mbox{S}$, $\mathbf{Y}$ be the set of different $y_i$'s in $\mbox{S}$, and $\mbox{Z}$ be the set of different $z_i$ in $\mbox{S}$. Then $|X|=|Y|=|Z|=|S|$.

The third condition means that all $x_i$'s are pairwise distinct. The same goes for $y_i$ and $z_i$.

Given $n$, find any beautiful set having a maximum number of elements. Then print the cardinality of $\mbox{S}$ (i.e., $\left|S\right|$) on a new line, followed by $\left|S\right|$ lines where each line contains $3$ space-separated integers describing the respective values of $x_i$, $y_i$, and $z_i$.

Input Format

A single integer, $n$.

Constraints

$1\leq n\leq300$  

Output Format

On the first line, print the cardinality of $\mbox{S}$ (i.e., $\left|S\right|$). 

For each of the $\left|S\right|$ subsequent lines, print three space-separated numbers per line describing the respective values of $x_i$, $y_i$, and $z_i$ for triple $\boldsymbol{i}$ in $\mbox{S}$.

Sample Input
3

Sample Output
3
0 1 2
2 0 1
1 2 0

Explanation

In this case, $n=3$. We need to construct a set, $\mbox{S}$, of non-negative integer triples ($x_{i},y_{i},z_{i}$) where $x_{i}+y_{i}+z_{i}=n$. $\mbox{S}$ has the following triples:

$(x_1,y_1,z_1)=(0,1,2)$
$(x_2,y_2,z_2)=(2,0,1)$
$(z_3,y_3,z_3)=(1,2,0)$

We then print the cardinality of this set, $|S|=3$, on a new line, followed by $3$ lines where each line contains three space-separated values describing a triple in $\mbox{S}$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms


Solutions:
n = int(input().strip())
low = n // 3
high = 2 * n // 3
print(high + 1)
for i in range(low + 1):
	print(i, 2 * (low - i), n + i - 2 * low)
for j in range(low + 1, high + 1):
	print(j, 2 * (high - j) + 1, n + j - 1 - 2 * high)


n = int(input())
a = []
add = 1
for i in range(n * 2 // 3 + 1):
	a.append(i)
if n % 3 != 2:
	b = a[len(a) // 2:] + a[:len(a) // 2]
else:
	b = a[len(a) // 2 + 1:] + a[:len(a) // 2 + 1]
	b.insert(len(a) // 2 - 1, b[len(a) // 2 - 2] + 1)
	b.pop()
c = []
for i in range(len(a)):
	val = n - a[i] - b[i]
	c.append(val)
if len(c) > 2:
	print(len(c))
	for i in range(len(c)):
		print(a[i], b[i], c[i])
elif n == 1:
	print(1)
	print(0, 0, 1)
elif n == 2:
	print(2)
	print(0, 0, 2)
	print(1, 1, 0)


from itertools import product, chain

def brute(n):
	nums = []
	for i in reversed(range(n + 1)):
		nums.append([None] + list(range(i + 1)))
	xs = list(range(n + 1))
	max_set = []
	for possible_ys in product(*nums):
		ys = [y for y in possible_ys if y is not None]
		if len(ys) != len(set(ys)):
			continue
		zs = [n - x - y for (x, y) in zip(xs, possible_ys) if y is not None and n - x - y >= 0]
		if len(zs) == len(set(zs)) and len(zs) > len(max_set):
			max_set = [(x, y, n - x - y) for (x, y) in zip(xs, possible_ys) if y is not None and n - x - y >= 0]
	return max_set

def solve(n):
	if n % 3 == 0:
		k = n // 3
		seq = chain(((i, k + i) for i in range(k + 1)), ((k + 1 + i, i) for i in range(k)))
		return [(x, y, n - x - y) for (x, y) in seq]
	if n % 3 == 1:
		return [(x + 1, y, z) for (x, y, z) in solve(n - 1)]
	return [(0, 0, n)] + [(x, y + 1, z) for (x, y, z) in solve(n - 1)]

def main():
	n = int(input())
	solution = solve(n)
	print(len(solution))
	for (x, y, z) in solution:
		print(x, y, z)
main()


def work(n):
	pts = []
	s = (n + 1) // 3
	(x, y) = (0, s)
	while x + y <= n:
		pts.append((x, y, n - x - y))
		x += 1
		y += 1
	(x, y) = (s + 1, 0)
	while x + y <= n and y < s:
		pts.append((x, y, n - x - y))
		x += 1
		y += 1
	m = len(pts)
	assert m == 1 + 2 * (n // 3) + (n % 3 == 2)
	for i in range(3):
		assert len(set((pt[i] for pt in pts))) == m
	print(m)
	for pt in pts:
		print(' '.join(map(str, pt)))
work(int(input()))


n = int(input())
k = (n + 1) // 3
print(2 * k + (n % 3 != 2))
for i in range(k):
	print('%d %d %d' % (i, k + 1 + i, n - 1 - k - 2 * i))
for i in range(k):
	print('%d %d %d' % (k + i, i, n - k - 2 * i))
if n % 3 != 2:
	print('%d %d %d' % (2 * k, n - 2 * k - n % 3, n % 3))


def beautiful(n):
	if n == 0:
		return [(0, 0, 0)]
	elif n == 1:
		return [(1, 0, 0)]
	initial_y = list(range(n - n % 2, n // 2 - 1, -1))
	initial_x = [n - y for y in initial_y]
	cardinality = []
	for i in range(0, len(initial_x)):
		(x, y) = (initial_x[i], initial_y[i])
		diff = y - x
		if diff <= (n - x - 2) // 2:
			cardinality += [x + 1 + diff]
		else:
			cardinality += [x + 1 + (n - x) // 2]
	max_cardinality = max(cardinality)
	max_index = cardinality.index(max_cardinality)
	x = initial_x[max_index]
	y = initial_y[max_index]
	z = 0
	diff = y - x
	beauties = []
	for yy in range(max(diff, (n - x - 2) // 2), y + 1):
		beauties += [(yy - diff, yy, n - 2 * yy + diff)]
	for yy in range(0, (n - x) // 2):
		x += 1
		beauties += [(x, yy, n - x - yy)]
	return beauties
n = int(input())
m = beautiful(n)
print(str(len(m)))
for r in m:
	print(' '.join((str(x) for x in r)))


n = int(input().strip())
maxset = set()
for y in range(0, n + 1):
	ts = set()
	p1 = (0, y, n - y)
	ts.add(p1)
	while True:
		p1 = (p1[0] + 1, p1[1] + 1, n - p1[0] - 1 - p1[1] - 1)
		if p1[2] < 0:
			break
		if p1[0] not in [x for (x, y, z) in ts] and p1[1] not in [y for (x, y, z) in ts] and (p1[2] not in [z for (x, y, z) in ts]):
			ts.add(p1)
	p1 = (p1[0], 0, n - p1[0])
	if p1[0] not in [x for (x, y, z) in ts] and p1[1] not in [y for (x, y, z) in ts] and (p1[2] not in [z for (x, y, z) in ts]):
		ts.add(p1)
	while True:
		p1 = (p1[0] + 1, p1[1] + 1, n - p1[0] - 1 - p1[1] - 1)
		if p1[2] < 0:
			break
		if p1[0] not in [x for (x, y, z) in ts] and p1[1] not in [y for (x, y, z) in ts] and (p1[2] not in [z for (x, y, z) in ts]):
			ts.add(p1)
	if len(ts) > len(maxset):
		maxset = set(ts)
print(len(maxset))
for t in sorted(maxset):
	print(' '.join(['%d' % x for x in t]))


n = int(input())
k = 2 * n // 3 + 1
print(k)
b_s = k // 2 if k % 2 else k // 2 + 1
mod = k if k % 2 else k + 1
for i in range(k):
	b = (b_s + i) % mod
	c = n - i - b
	print('{} {} {}'.format(i, b, c))


import math
n = int(input().strip())
rot = (n - 4) // 3 + (n - 4) % 3
N = math.floor(2 * n / 3) + 1
shift = (3 - n % 3) % 3
print(N)
for i in range(min(shift, N)):
	print('{0} {0} {1}'.format(i, n - 2 * i))
for x in range(shift, N):
	y = (x - shift + rot) % (N - shift) + shift
	z = n - x - y
	print('{0} {1} {2}'.format(x, y, z))


n = int(input())
k = 2 * n // 3 + 1
print(k)
b_s = k // 2 if k % 2 else k // 2 + 1
mod = k if k % 2 else k + 1
for i in range(k):
	b = (b_s + i) % mod
	c = n - i - b
	print('{} {} {}'.format(i, b, c))


n = int(input().strip())
maxset = set()
for y in range(0, n + 1):
	ts = set()
	p1 = (0, y, n - y)
	ts.add(p1)
	while True:
		p1 = (p1[0] + 1, p1[1] + 1, n - p1[0] - 1 - p1[1] - 1)
		if p1[2] < 0:
			break
		if p1[0] not in [x for (x, y, z) in ts] and p1[1] not in [y for (x, y, z) in ts] and (p1[2] not in [z for (x, y, z) in ts]):
			ts.add(p1)
	p1 = (p1[0], 0, n - p1[0])
	if p1[0] not in [x for (x, y, z) in ts] and p1[1] not in [y for (x, y, z) in ts] and (p1[2] not in [z for (x, y, z) in ts]):
		ts.add(p1)
	while True:
		p1 = (p1[0] + 1, p1[1] + 1, n - p1[0] - 1 - p1[1] - 1)
		if p1[2] < 0:
			break
		if p1[0] not in [x for (x, y, z) in ts] and p1[1] not in [y for (x, y, z) in ts] and (p1[2] not in [z for (x, y, z) in ts]):
			ts.add(p1)
	if len(ts) > len(maxset):
		maxset = set(ts)
print(len(maxset))
for t in sorted(maxset):
	print(' '.join(['%d' % x for x in t]))


n = input().strip()
n = int(n)
flag = 0
num = n
while flag != 1:
	t = n - num
	add = num - t - 1
	if add + num < n:
		flag = 1
		break
	num = num - 1
x = []
y = []
z = []
for i in range(num + 1):
	x.append(i)
	y.append(0)
	z.append(0)
y[t] = num
i = t + 1
j = 0
while i < len(y):
	y[i] = j
	j = j + 1
	i = i + 1
i = t - 1
j = 1
while i >= 0:
	y[i] = num - j
	j = j + 1
	i = i - 1
i = 0
while i < len(z):
	z[i] = n - (x[i] + y[i])
	i = i + 1
z_d = list(set(z))
if len(z_d) != len(z):
	i = 0
	temp = y[0]
	while i < len(y):
		if i + 1 < len(y) and y[i + 1] == 0:
			while i < len(y):
				if i == len(y) - 1:
					y[i] = temp
					i = i + 1
					break
				y[i] = y[i + 1]
				i = i + 1
		else:
			y[i] = y[i] + 2
			i = i + 1
	i = 0
	while i < len(z):
		z[i] = n - (x[i] + y[i])
		i = i + 1
print(num + 1)
i = 0
while i < len(x):
	print(x[i], y[i], z[i])
	i = i + 1


n = int(input())
C = int(2 * n / 3) + 1
k = n - C + 1
print(C)
X = range(n + 1)
table = []
for x in range(n + 1):
	candidates = []
	for y in range(n - x + 1):
		candidates.append((x, y, n - x - y))
	table.append(candidates)
for i in range(C):
	print('%d %d %d' % table[n - k - i][k - i if k - i >= 0 else len(table[n - 2 * k]) + k - i])


from math import floor, ceil
N = int(input())
if N == 0:
	print(1)
	print('0 0 0')
elif N == 1:
	print(1)
	print('1 0 0')
elif N == 2:
	print(2)
	print('1 1 0')
	print('0 0 2')
elif N == 3:
	print(3)
	print('0 1 2')
	print('2 0 1')
	print('1 2 0')
elif N == 4:
	print(3)
	print('0 1 3')
	print('3 0 1')
	print('1 3 0')
else:
	n23 = floor(N * 2 / 3) + 1
	print(n23)
	mid = [-1, -1, -1]
	mid[0] = ceil(n23 / 2)
	mid[1] = 0
	mid[2] = N - mid[0] - mid[1]
	print(' '.join(map(str, mid)))
	top = [-1, -1, -1]
	top[0] = mid[0] - 1
	top[2] = int(mid[2] % 2 == 0)
	top[1] = N - top[0] - top[2]
	print(' '.join(map(str, top)))
	while top[0] > 0:
		top[0] -= 1
		top[1] -= 1
		top[2] += 2
		print(' '.join(map(str, top)))
	bot = [-1, -1, -1]
	bot[0] = mid[0] + 1
	bot[1] = 1
	bot[2] = N - bot[0] - bot[1]
	print(' '.join(map(str, bot)))
	while bot[0] < n23 - 1:
		bot[0] += 1
		bot[1] += 1
		bot[2] -= 2
		print(' '.join(map(str, bot)))


n = int(input())
if n % 3 == 0:
	z = 2 * n // 3
	print(z + 1)
	for i in range(z + 1):
		j = (i + n // 3) % (z + 1)
		print(i, j, n - i - j)
if (n + 1) % 3 == 0:
	z = 2 * n // 3
	print(z + 1)
	for i in range(z + 1):
		j = (i + n // 3 + 2) % (z + 2)
		print(i, j, n - i - j)
if (n + 2) % 3 == 0:
	z = 2 * n // 3
	print(z + 1)
	for i in range(z + 1):
		j = (i + n // 3) % (z + 1)
		print(i, j, n - i - j)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
cards = 2 * n // 3
print(cards + 1)
y = 2 * cards - n
x = n - 2 * y
ans = []
for i in range(2 * cards - n + 1):
	ans.append((i, x + i, n - x - 2 * i))
for j in range(cards - y):
	ans.append((y + j + 1, j, n - y - 2 * j - 1))
for lis in ans:
	print(*lis)


import sys
n = int(input().strip())
S = []
X = set()
Y = set()
Z = set()
c = 0
m = 0
res = []
for d in range(1, n + 1):
	y = d
	S = []
	X = set()
	Y = set()
	Z = set()
	for x in range(n + 1):
		if x + y > n:
			y = 0
		z = n - (x + y)
		if x not in X and y not in Y and (z not in Z):
			S.append((x, y, z))
			X.add(x)
			Y.add(y)
			Z.add(z)
		y += 1
	c = len(S)
	if c > m:
		m = c
		res = S
print(len(res))
for x in res:
	print(*x)


n = int(input())
q = []
i = 0
t = -1
maxm = 0
while True:
	if maxm < len(q):
		maxm = len(q)
		r = q[:]
		q = []
	else:
		q = []
	if t == n:
		break
	l = []
	m = []
	u = []
	i = 0
	t = t + 1
	j = t
	while True:
		k = n - j - i
		l.append(i)
		m.append(j)
		u.append(k)
		if i < 0 or j < 0 or k < 0:
			break
		q.append([str(i), str(j), str(k)])
		j = j + 1
		if k == 0:
			j = 0
		i = i + 1
		if i in l or j in m or n - i - j in u:
			break
print(maxm)
for i in range(len(r)):
	print(' '.join(r[i]))


n = int(input())
q = []
i = 0
t = -1
maxm = 0
while True:
	if maxm < len(q):
		maxm = len(q)
		r = q[:]
		q = []
	else:
		q = []
	if t == n:
		break
	l = []
	m = []
	u = []
	i = 0
	t = t + 1
	j = t
	while True:
		k = n - j - i
		l.append(i)
		m.append(j)
		u.append(k)
		if i < 0 or j < 0 or k < 0:
			break
		q.append([str(i), str(j), str(k)])
		j = j + 1
		if k == 0:
			j = 0
		i = i + 1
		if i in l or j in m or n - i - j in u:
			break
print(maxm)
for i in range(len(r)):
	print(' '.join(r[i]))


n = int(input().strip())
k = int(2 * n / 3)
y = 2 * k - n
x = n - 2 * y
result = []
for i in range(y + 1):
	result.append((i, x + i, n - x - 2 * i))
for i in range(k - y):
	result.append((y + i + 1, i, n - y - 1 - 2 * i))
print(len(result))
for tu in result:
	print(' '.join([str(x) for x in tu]))


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input().strip())
k = int(n / 3)
xs = []
a = 1 if n % 3 >= 1 else 0
b = 1 if n % 3 >= 2 else 0
for i in range(2 * k + 1):
	xs.append([2 * k - i, i % 2 * k + int((i + 1) / 2) + a, (i + 1) % 2 * k + int(i / 2) + b])
if n % 3 == 2:
	xs.append([n, 0, 0])
print(len(xs))
for x in xs:
	print(' '.join(list(map(str, x))))


n = int(input())
k = int(2 * n / 3)
y = 2 * k - n
x = n - 2 * y
print(k + 1)
for i in range(int(y + 1)):
	print(i, x + i, n - x - 2 * i)
for i in range(int(k - y)):
	print(y + i + 1, i, n - y - 1 - 2 * i)


import sys
inputNumber = int(sys.stdin.read())
limit = inputNumber * 2 // 3 + 1
print(limit)
arrayOne = [x for x in range(0, limit)]
arrayTwo = []
arrayThree = []
rem = inputNumber % 3
noOfShifts = inputNumber // 3
if rem == 0:
	arrayTwo = arrayOne[noOfShifts:] + arrayOne[0:noOfShifts + 1]
if rem == 1:
	arrayTwo = arrayOne[noOfShifts:] + arrayOne[0:noOfShifts]
if rem == 2:
	arrayTwo = arrayOne[noOfShifts + 2:]
	arrayTwo.append(arrayOne[len(arrayOne) - 1] + 1)
	arrayTwo = arrayTwo + arrayOne[0:noOfShifts + 1]
for i in range(0, limit):
	diff = inputNumber - (arrayOne[i] + arrayTwo[i])
	arrayThree.append(diff)
for i in range(limit):
	print(arrayOne[i], arrayTwo[i], arrayThree[i])


N = int(input())
K = 2 * N // 3
print(K + 1)
nf = N % 3 == 2
for i in range(K + 1):
	a = (N - K + i) % (K + 1)
	b = i + (nf and i >= (K + 1) // 2)
	c = N - a - b
	print(a, b, c)


def f(N):
	k = 2 * N // 3
	a = 2 * k - N
	b = N - 2 * a
	res = []
	for i in range(a + 1):
		res.append([i, b + i, 2 * (a - i)])
	for i in range(k - a):
		res.append([a + i + 1, i, N - a - 2 * i - 1])
	return res
N = int(input())
ans = f(N)
print(len(ans))
for z in ans:
	print(' '.join(list(map(str, z))))


import sys

def print_max_cardinality(n):
	cardinality = 2 * n // 3 + 1
	print(cardinality)
	if cardinality % 2 == 0:
		y_start = cardinality // 2 + 1
		modulo = cardinality + 1
	else:
		y_start = cardinality // 2
		modulo = cardinality
	for i in range(cardinality):
		x = i
		y = (y_start + i) % modulo
		z = n - (x + y)
		print('{0} {1} {2}'.format(x, y, z))
n = int(input().strip())
print_max_cardinality(n)


n = int(input().strip())
i = n * 2 // 3
print(i + 1)
x = (i + 1) // 2
for j in range(x + 1):
	print(j, x + j, n - x - 2 * j)
for j in range(x + 1, i + 1):
	print(j, j - x - 1, n - 2 * j + x + 1)


n = int(input().strip())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input().strip())
X = list(range(n))
true_count = 0
S = []
while true_count < len(X) or len(S) - len(set(list(map(lambda x: n - sum(x), S)))):
	middle = int(len(X) / 2)
	zip_X_Y = list(zip(X, X[middle:] + X[:middle]))
	S = list(filter(lambda x: x[0] + x[1] <= n, zip_X_Y))
	true_count = len(S)
	if true_count < len(X) or len(S) - len(set(list(map(lambda x: n - sum(x), S)))):
		X.pop()
if n == 2:
	print('2')
	print('0 0 2')
	print('1 1 0')
else:
	print(len(S))
	for one in S:
		print('%s %s' % (' '.join(map(str, one)), str(n - sum(one))))


from itertools import *
myinput = int(input())
k = int(2 * myinput / 3)
print(k + 1)
y = int(2 * k - myinput)
n = islice(count(), myinput)
prods = product(n, repeat=3)
prodyinit = False
(a, b, c) = (y, myinput, 0)
for prod in prods:
	if sum(prod) == myinput:
		if prod[0] == y + 1 and prod[1] == 0 and (prodyinit == False):
			(i, j, l) = prod
			prodyinit = True
			break
		if prod[0] == y and prod[2] == 0 and (prodyinit == False):
			(a, b, c) = prod
print(i, j, l)
yloop = i + 1
while yloop < k + 1:
	(i, j, l) = (i + 1, j + 1, l - 2)
	print(i, j, l)
	yloop += 1
print(a, b, c)
while a > 0:
	(a, b, c) = (a - 1, b - 1, c + 2)
	print(a, b, c)


n = int(input().strip())
x = []
s_x = 0
s_z = -4 * (2 * n // 3) + 3 * n
s_y = n - s_z
c_x = s_x
c_y = s_y
c_z = s_z
while c_y >= 0:
	x.append((c_x, c_y, c_z))
	c_x += 1
	c_y -= 2
	c_z += 1
c_z = 0
c_y = n - c_x
while c_y >= 0 and c_z < s_z:
	x.append((c_x, c_y, c_z))
	c_x += 1
	c_y -= 2
	c_z += 1
print(len(x))
for t in x:
	print(str(t[0]) + ' ' + str(t[1]) + ' ' + str(t[2]))


n = int(input())
val = (n - 1) // 2 + 1
m = 0
z = 0
for x in range(n):
	if n - x // 2 & 1 == 0:
		temp = x // 2 + 1 + min((n - (x // 2 + 1)) // 2 + 1, n - x)
		if temp > m:
			m = temp
			z = x
x = 0
y = n - z
result = []
while z >= 0:
	result.append([x, y, z])
	x += 1
	y += 1
	z -= 2
y = 0
z = n - x
while z > 0:
	result.append([x, y, z])
	x += 1
	y += 1
	z -= 2
print(len(result))
for x in result:
	print(*x)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


res = []
i = 0
n = int(input())
a = 0
b = n // 2
c = n - b
while c >= 0:
	res.append((a, b, c))
	a += 1
	b += 1
	c -= 2
a = res[-1][0] + 1
b = 0
c = n - a
while c >= 0:
	res.append((a, b, c))
	a += 1
	b += 1
	c -= 2
res2 = []
k = 2 * n // 3
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	res2.append((i, x + i, 2 * (y - i)))
for i in range(k - y):
	res2.append((y + i + 1, i, n - y - 1 - 2 * i))
print('')
print(len(res2))
for v in res2:
	print(v[0], v[1], v[2], '')


n = int(input().strip())

def get_beauts(n):
	output = []
	n_tups = 2 * n // 3
	y = 2 * n_tups - n
	x = n - 2 * y
	for i in range(y + 1):
		output.append((str(i), str(x + i), str(n - x - 2 * i)))
	for i in range(n_tups - y):
		output.append((str(y + i + 1), str(i), str(n - y - 1 - 2 * i)))
	return output
x = get_beauts(n)
print(len(x))
for tuple in x:
	print(' '.join(tuple))


import sys
from functools import wraps

def cache(f):
	csh = {}

	@wraps(f)
	def wrapper(*args, **kwargs):
		k = (str(args), str(kwargs))
		if k in csh:
			return csh[k]
		else:
			r = csh[k] = f(*args, **kwargs)
			return r
	return wrapper

@cache
def s_size(n):
	if n == 1:
		return 1
	elif n == 2:
		return 2
	elif n == 3:
		return 3
	(k, r) = divmod(n, 3)
	if not r:
		return 2 * k + 1
	elif r == 2:
		return 2 * (k + 1)
	elif r == 1:
		return 2 * k + 1

@cache
def s0(n):
	if n == 1:
		return (0, 0, 1)
	elif n == 2:
		return (0, 2, 0)
	elif n == 3:
		return (0, 1, 2)
	else:
		return (s0(n - 3)[0], s0(n - 3)[1] + 1, s0(n - 3)[2] + 2)

@cache
def beautiful_set(n):
	if n == 1:
		return [(0, 0, 1)]
	elif n == 2:
		return [(0, 2, 0), (1, 0, 1)]
	elif n == 3:
		return [(0, 1, 2), (1, 2, 0), (2, 0, 1)]
	(k, r) = divmod(n, 3)
	l2 = beautiful_set(n - 1)
	rez = []
	if r == 1:
		rez.extend([(x[0], x[1], x[2] + 1) for x in l2])
	elif r == 2:
		rez.append(s0(n))
		ln = len(l2)
		second_half = (ln - 1) // 2 + 1
		rez.extend([(x[0], x[1] + 2, x[2] - 1) for x in l2[1:second_half]])
		rez.extend([(x[0], x[1], x[2] + 1) for x in l2[second_half:second_half + (ln - 1) // 2]])
		lst = l2[-1]
		rez.append((lst[0] + 1, lst[1] + 1, lst[2] - 1))
	elif r == 0:
		rez.append(s0(n))
		rez.extend([(x[0] + 1, x[1], x[2]) for x in l2])
	else:
		assert 'should never get to this point in  the program'
	return rez

def enter_data():
	n = int(sys.stdin.readline().strip(), 10)
	str_set = [str(s_size(n))]
	str_set.extend([' '.join(map(str, x)) for x in beautiful_set(n)])
	return str_set
for r in enter_data():
	print(r)


n = int(input().strip())
if n == 2:
	print(2)
	print(0, 0, 2)
	print(1, 1, 0)
elif n == 1:
	print(1)
	print(0, 0, 1)
elif n % 3 == 0:
	k = 2 * (n // 3) + 1
	print(k)
	for kk in range(k - n // 3 - 1):
		print(kk, n // 3 + kk + 1, n - kk - n // 3 - kk - 1)
	for kk in range(k - n // 3 - 1, k):
		print(kk, kk - k + n // 3 + 1, n - kk - (kk - k + n // 3 + 1))
elif n % 3 == 1:
	k = 2 * ((n - 1) // 3) + 1
	print(k)
	for kk in range(k - (n - 1) // 3 - 1):
		print(kk, (n - 1) // 3 + kk + 1, n - kk - (n - 1) // 3 - kk - 1)
	for kk in range(k - (n - 1) // 3 - 1, k):
		print(kk, kk - k + (n - 1) // 3 + 1, n - kk - (kk - k + (n - 1) // 3 + 1))
else:
	k = 2 * ((n + 1) // 3)
	print(k)
	print(0, 0, n)
	for kk in range(1, k - (n + 1) // 3):
		print(kk, (n + 1) // 3 + kk, n - kk - (n + 1) // 3 - kk)
	for kk in range(k - (n + 1) // 3, k):
		print(kk, kk - k + (n + 1) // 3 + 1, n - kk - (kk - k + (n + 1) // 3 + 1))


n = int(input().strip())
k = 2 * n // 3
y = 2 * k - n
x = n - 2 * y
print(k + 1)
for i in range(y + 1):
	print(*[i, x + i, n - x - 2 * i], sep=' ')
for i in range(k - y):
	print(*[y + i + 1, i, n - y - 1 - 2 * i], sep=' ')


n = int(input().strip())
k = int(2 * n / 3)
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(str(i) + ' ' + str(x + i) + ' ' + str(n - x - 2 * i))
for i in range(k - y):
	print(str(y + i + 1) + ' ' + str(i) + ' ' + str(n - y - 1 - 2 * i))


n = 0
while not (n < 300 and n > 1 or n == 300 or n == 1):
	n = int(input())
x = int(2 * n / 3)
print(x + 1)
y = int(2 * x - n)
z = int(n - 2 * y)
for i in range(0, y + 1):
	print(i, z + i, n - z - 2 * i)
for j in range(0, x - y):
	print(y + j + 1, j, n - y - 1 - 2 * j)


n = int(input())
k = 2 * n // 3
print(str(k + 1))
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(str(i) + ' ' + str(x + i) + ' ' + str(n - x - 2 * i))
for i in range(k - y):
	print(str(y + i + 1) + ' ' + str(i) + ' ' + str(n - y - 1 - 2 * i))


n = int(input())
k = 2 * n // 3
print(k + 1)

def add_all(a, b, c):
	while c >= 0:
		print(a, b, c)
		a += 1
		b += 1
		c -= 2
	return abs(a)
carry = add_all(0, n - k + 1, k - 1)
add_all(carry, n - k - carry, k)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, end=' ')
	print(x + i, end=' ')
	print(n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, end=' ')
	print(i, end=' ')
	print(n - y - 1 - 2 * i)


n = int(input())
a = 2 * n // 3 + 1
b = (n + 2) // 3 - 1
c = (2 * n + 2) // 3
print(a)
for i in range(0, a, 2):
	print(i, c - i // 2, n - c - i // 2)
for i in range(1, a, 2):
	print(i, b - i // 2, n - 1 - b - i // 2)


n = int(input())
a = 2 * n // 3 + 1
b = (n + 2) // 3 - 1
c = (2 * n + 2) // 3
print(a)
for i in range(0, a, 2):
	print(i, c - i // 2, n - c - i // 2)
for i in range(1, a, 2):
	print(i, b - i // 2, n - 1 - b - i // 2)


n = int(input())
k = 2 * n // 3 + 1
print(k)
if n % 3 <= 1:
	z = list(range(k))
else:
	z = list(range(k // 2)) + list(range(k // 2 + 1, k + 1))
zz = list(range(k - 1, -1, -2)) + list(range(k - 2, -1, -2))
zzz = [n - z[i] - zz[i] for i in range(k)]
for i in range(k):
	print(z[i], zz[i], zzz[i], sep=' ')


n = int(input().strip())
low = n // 3
high = 2 * n // 3
print(high + 1)
for i in range(low + 1):
	print(i, 2 * (low - i), n + i - 2 * low)
for j in range(low + 1, high + 1):
	print(j, 2 * (high - j) + 1, n + j - 1 - 2 * high)


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - x - 2 * i)
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - y - 1 - 2 * i)
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


def plop(n):
	Cmax = []
	for j0 in range(n + 1):
		C = []
		(i, j) = (0, j0)
		while i <= n - j:
			C.append((i, j))
			i += 1
			j += 1
		j = 0
		while i <= n - j and j < j0:
			C.append((i, j))
			i += 1
			j += 1
		if len(set((i + j for (i, j) in C))) == len(set((i for (i, j) in C))) == len(set((j for (i, j) in C))) == len(C):
			if len(C) > len(Cmax):
				Cmax = C
	return Cmax
n = int(input())
C = plop(n)
print(len(C))
for (a, b) in C:
	print(a, b, n - a - b)


import sys
n = int(input())
s = list()
x = list()
y = list()
z = list()
count = 0
if n == 1:
	print(1, '\n', 0, ' ', 1, ' ', 0)
	sys.exit()
if n % 3 == 2:
	count = (n // 3 + 1) * 2
else:
	count = (n // 3 + 1) * 2 - 1
if count % 2 == 0:
	c = count // 2
	y1 = c + 1
else:
	c = count // 2 + 1
	y1 = count // 2
for i in range(c):
	x.append(i)
	y.append(y1)
	z.append(n - (i + y1))
	y1 += 1
y1 = 0
for i in range(c, count):
	x.append(i)
	y.append(y1)
	z.append(n - (i + y1))
	y1 += 1
print(count)
for i in range(count):
	print(x[i], '', y[i], '', z[i])


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


import math
n = int(input().strip())
s = math.floor(2 * n / 3 + 1)
print(s)
x = list(range(s))
y = [i * 2 for i in range(n - s + 2)]
y = y + [i * 2 + 1 for i in range(len(x) - len(y))]
y = y[::-1]
for (xi, yi) in zip(x, y):
	print(str(xi) + ' ' + str(yi) + ' ' + str(n - xi - yi))


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(0, k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(0, k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(0, k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(0, k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input().strip())
low = n // 3
high = 2 * n // 3
print(high + 1)
for i in range(low + 1):
	print(i, 2 * (low - i), n + i - 2 * low)
for j in range(low + 1, high + 1):
	print(j, 2 * (high - j) + 1, n + j - 1 - 2 * high)


import sys

def be_3(n):
	longest = 0
	for j in range(1, n + 1):
		a = 0
		b = j
		used_2 = []
		used_3 = []
		for i in range(n):
			if a + b > n:
				b = 0
			num = n - a - b
			if b not in used_2:
				if num >= 0:
					used_3.append(num)
					used_2.append(b)
			a += 1
			b += 1
		list_set = set(used_3)
		a = len(list_set)
		if longest < a:
			longest = a
			saved = j
	answear = []
	used = []
	used_help = []
	a = 0
	b = saved
	print(longest)
	for i in range(n):
		diff = n - a - b
		if diff >= 0:
			if diff not in used:
				if b not in used_help:
					used_help.append(b)
					used.append(diff)
					print(a, b, diff)
		a += 1
		b += 1
		if a + b > n:
			b = 0
for line in sys.stdin:
	be_3(int(line))


n = int(input())
m = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * m - n
	x = (n - 2) * y
	print(m + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(m - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
elif n == 4:
	print(m + 1)
	y = 2 * (m + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(m - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(m + 1)
	y = 2 * (m + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(m - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
print()


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = input().strip()
n = int(n)
flag = 0
num = n
while flag != 1:
	t = n - num
	add = num - t - 1
	if add + num < n:
		flag = 1
		break
	num = num - 1
x = []
y = []
z = []
for i in range(num + 1):
	x.append(i)
	y.append(0)
	z.append(0)
y[t] = num
i = t + 1
j = 0
while i < len(y):
	y[i] = j
	j = j + 1
	i = i + 1
i = t - 1
j = 1
while i >= 0:
	y[i] = num - j
	j = j + 1
	i = i - 1
i = 0
while i < len(z):
	z[i] = n - (x[i] + y[i])
	i = i + 1
z_d = list(set(z))
if len(z_d) != len(z):
	i = 0
	temp = y[0]
	while i < len(y):
		if i + 1 < len(y) and y[i + 1] == 0:
			while i < len(y):
				if i == len(y) - 1:
					y[i] = temp
					i = i + 1
					break
				y[i] = y[i + 1]
				i = i + 1
		else:
			y[i] = y[i] + 2
			i = i + 1
	i = 0
	while i < len(z):
		z[i] = n - (x[i] + y[i])
		i = i + 1
print(num + 1)
i = 0
while i < len(x):
	print(x[i], y[i], z[i])
	i = i + 1


from math import ceil
n = int(input())
max_count = 0
max_ret = []
for m in range(0, n):
	try:
		j = m
		xs = list(range(n + 1))
		ys = list(range(n + 1))
		zs = list(range(n + 1))
		count = 0
		ret = []
		for i in range(0, n):
			k = n - i - j
			count += 1
			ret.append((i, j, k))
			xs.remove(i)
			ys.remove(j)
			zs.remove(k)
			j += 1
			if i + j >= n:
				j = 0
			if j not in ys:
				break
		if count > max_count:
			max_count = count
			max_ret = ret[:]
	except:
		pass
print(max_count)
for s in max_ret:
	print(*s)


n = int(input())
max_count = 0
max_ret = []
for m in range(0, n):
	try:
		j = m
		xs = list(range(n + 1))
		ys = list(range(n + 1))
		zs = list(range(n + 1))
		count = 0
		ret = []
		for i in range(0, n):
			k = n - i - j
			count += 1
			ret.append((i, j, k))
			xs.remove(i)
			ys.remove(j)
			zs.remove(k)
			j += 1
			if i + j >= n:
				j = 0
			if j not in ys:
				break
		if count > max_count:
			max_count = count
			max_ret = ret[:]
	except:
		pass
print(max_count)
for s in max_ret:
	print(*s)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + 1 + i, i, n - y - 1 - 2 * i)


n = int(input())
l = int(n * 2 / 3)
y = int(l * 2 - n)
x = int(n - 2 * y)
print(l + 1)
for i in range(0, y + 1):
	print(i, ' ', x + i, ' ', n - x - 2 * i)
for i in range(0, l - y):
	print(y + i + 1, ' ', i, ' ', n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


import itertools
n = int(input())
k = int(2 * n / 3)
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, end=' ')
	print(x + i, end=' ')
	print(n - x - 2 * i)
for i in range(0, k - y):
	print(y + i + 1, end=' ')
	print(i, end=' ')
	print(n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


def triple(n):
	k = int(2 * n / 3)
	print(k + 1)
	y = 2 * k - n
	x = n - 2 * y
	for i in range(y + 1):
		print(i, x + i, n - x - 2 * i)
	for i in range(k - y):
		print(y + i + 1, i, n - y - 1 - 2 * i)
n = int(input())
triple(n)


import fileinput

def b3set(n):
	result = list()
	k = 2 * n // 3
	print(k + 1)
	y = 2 * k - n
	x = n - 2 * y
	for i in range(0, y + 1):
		result.append((i, x + i, n - x - 2 * i))
	for i in range(0, k - y):
		result.append((i + y + 1, i, n - y - 1 - 2 * i))
	for i in range(len(result)):
		print('{0} {1} {2}'.format(result[i][0], result[i][1], result[i][2]))
	return result
for line in fileinput.input():
	b3set(int(line.rstrip()))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


import os

def getMaximumInd(vertices, adjList):
	maxInd = set()
	V = set(range(len(vertices)))
	while len(V) > 0:
		(W, indSet) = (V.copy(), set())
		while len(W) > 0:
			node = W.pop()
			indSet.add(node)
			W -= set(adjList[node])
		if len(indSet) > len(maxInd):
			maxInd = indSet
		V -= indSet
	return [vertices[i] for i in maxInd]

def getKSets(n, k):
	if k == 1:
		return [[n]]
	results = []
	for i in range(n + 1):
		R = getKSets(n - i, k - 1)
		results += [r + [i] for r in R]
	return results

def getAdjList(n, k, vertices):
	pre_adjList = [{i: set() for i in range(n + 1)} for l in range(k)]
	for (v_idx, v) in enumerate(vertices):
		for (l, i) in enumerate(v):
			pre_adjList[l][i].add(v_idx)
	adjList = {}
	for (v_idx, v) in enumerate(vertices):
		al = set()
		for (l, i) in enumerate(v):
			al.update(pre_adjList[l][i])
		adjList[v_idx] = al
	return adjList

def beautiful3Sets(n):
	if n == 1:
		return ([[0, 0, 1]], 1)
	if (n + 2) % 3 == 0:
		k1 = (n + 2) // 3 - 1
	else:
		k1 = (n + 2) // 3
	if (n - k1 - 1) % 2 == 0:
		k1 -= 1
	M1 = (n + k1) // 2
	if (n - 1) % 3 == 0:
		k2 = (n - 1) // 3 - 1
	else:
		k2 = (n - 1) // 3
	if (n - k2) % 2 == 0:
		k2 -= 1
	M2 = (n + k2 + 1) // 2
	if M1 > M2:
		A = [[i, 2 * (k1 - i), n - 2 * k1 + i] for i in range(k1 + 1)]
		B = [[k1 + 1 + i, n - k1 - 1 - 2 * i, i] for i in range((n - k1) // 2)]
		return A + B
	else:
		A = [[i, 2 * (k2 - i) + 1, n - 1 - 2 * k2 + i] for i in range(k2 + 1)]
		B = [[k2 + 1 + i, n - k2 - 1 - 2 * i, i] for i in range((n - k2 + 1) // 2)]
		return A + B
n = int(input())
result = beautiful3Sets(n)
print(len(result))
for r in result:
	print(' '.join(map(str, r)))


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(0, y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 2 * i - 1)


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(f'{i} {x + i} {n - x - 2 * i}')
for i in range(k - y):
	print(f'{y + i + 1} {i} {n - y - 1 - 2 * i}')


n = int(input())
k = 2 * n // 3
y = 2 * k - n
x = n - 2 * y
print(k + 1)
for i in range(y + 1):
	print(i, x + i, n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, i, n - y - 1 - 2 * i)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(i, ' ', x + i, ' ', n - x - 2 * i)
for i in range(k - y):
	print(y + i + 1, ' ', i, ' ', n - y - 1 - 2 * i)


def triplets(n):
	k = 2 * n // 3
	if n != 2 and n != 4:
		y = 2 * k - n
		x = (n - 2) * y
		print(k + 1)
		for i in range(y + 1):
			print(i, '', x + i, '', n - (x + i + i))
		for i in range(k - y):
			print(y + i + 1, '', i, '', n - (y + i + 1 + i))
		print('\x0b')
	elif n == 4:
		print(k + 1)
		y = 2 * (k + 1) - n
		x = n - 3
		for i in range(y):
			print(i, '', x + i, '', n - (x + i + i))
		for i in range(k - y + 1):
			print(y - i, '', i, '', n - (y - i + i))
	elif n == 2:
		print(k + 1)
		y = 2 * (k + 1) - n
		x = n - 2
		for i in range(y):
			print(i, '', x + i, '', n - (x + i + i))
		for i in range(k - y + 1):
			print(y - i, '', i, '', n - (y - i + i))
n = int(input())
triplets(n)


n = int(input())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
i = 0
j = 0
for i in range(i, y + 1):
	print(str(i) + ' ' + str(x + i) + ' ' + str(n - x - 2 * i))
for j in range(j, k - y):
	print(str(y + j + 1) + ' ' + str(j) + ' ' + str(n - y - 1 - 2 * j))


n = int(input().strip())
low = n // 3
high = 2 * n // 3
print(high + 1)
for i in range(low + 1):
	print(i, 2 * (low - i), n + i - 2 * low)
for j in range(low + 1, high + 1):
	print(j, 2 * (high - j) + 1, n + j - 1 - 2 * high)


n = int(input().strip())
k = 2 * n // 3
print(k + 1)
y = 2 * k - n
x = n - 2 * y
for i in range(y + 1):
	print(f'{i} {x + i} {n - x - 2 * i}')
for i in range(k - y):
	print(f'{y + i + 1} {i} {n - y - 1 - 2 * i}')


n = int(input().strip())
low = n // 3
high = 2 * n // 3
print(high + 1)
for i in range(low + 1):
	print(i, 2 * (low - i), n + i - 2 * low)
for j in range(low + 1, high + 1):
	print(j, 2 * (high - j) + 1, n + j - 1 - 2 * high)


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))


n = int(input())
k = 2 * n // 3
if n != 2 and n != 4:
	y = 2 * k - n
	x = (n - 2) * y
	print(k + 1)
	for i in range(y + 1):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y):
		print(y + i + 1, '', i, '', n - (y + i + 1 + i))
	print('\x0b')
elif n == 4:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 3
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))
elif n == 2:
	print(k + 1)
	y = 2 * (k + 1) - n
	x = n - 2
	for i in range(y):
		print(i, '', x + i, '', n - (x + i + i))
	for i in range(k - y + 1):
		print(y - i, '', i, '', n - (y - i + i))