Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef likes problems on geometry a lot. Please help him to solve one such problem.

Find all possible triangles with integer sides which has the radius of inscribed circle (also known as incircle) equal to R.

Two triangles are said to be different if they have at least one different side lengths. Formally, let there be two triangles T_{1}, T_{2}. Let a, b, c denote the sides of triangle T_{1}, such that a ≤ b ≤ c. Similarly, Let d, e, f denote the sides of triangle T_{2}, such that d ≤ e ≤ f. Then T_{1} will said to be different from T_{2} if either a ≠ d, or b ≠ e or c ≠ f.

------ Input ------ 

There is a single test case per test file.
The only line of input contains an integer R.

------ Output ------ 

Output in first line single number - number of triangles satisfying statement.
Order the sides of triangles in non-decreasing order. Output all triangles in non-decreasing order, i.e. order first by smallest sides, otherwise by second smallest sides, if first and second sides equal, then by third.

------ Constraints ------ 

$1 ≤ R ≤ 100 $

------ Subtasks ------ 

$Subtask #1: (20 points)  1 ≤ R ≤ 3$
$Subtask #2: (30 points)  1 ≤ R ≤ 20$
$Subtask #3: (50 points)  Original constraints$

------ Example ------ 

Input:
2

Output:
5
5 12 13
6 8 10
6 25 29
7 15 20
9 10 17

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Constructive algorithms

Mathematics

Ad-hoc


Solutions:
def solve(R):
	t = 4 * R * R
	ans = []
	z = 1
	while z * z <= 3 * t:
		y = z
		while True:
			nom = (y + z) * t
			denom = y * z - t
			if nom < y * denom:
				break
			if denom > 0 and nom % denom == 0:
				x = nom / denom
				if x % 2 == y % 2 and x % 2 == z % 2:
					a = int((y + z) // 2)
					b = int((x + z) // 2)
					c = int((x + y) // 2)
					ans = ans + [[a, b, c]]
					pass
			y += 1
		z += 1
	ans.sort()
	print(len(ans))
	for i in ans:
		print(*i)
R = int(input())
solve(R)


def solve(R):
	(t, ans, z) = (4 * R * R, [], 1)
	while z * z <= 3 * t:
		y = z
		while True:
			(nom, denom) = ((y + z) * t, y * z - t)
			if nom < y * denom:
				break
			if denom > 0 and nom % denom == 0:
				x = nom / denom
				if x % 2 == y % 2 and x % 2 == z % 2:
					ans += [[(y + z) // 2, (x + z) // 2, (x + y) // 2]]
					pass
			y += 1
		z += 1
	ans.sort()
	print(len(ans))
	for q in ans:
		print('%d %d %d' % (q[0], q[1], q[2]))
solve(int(input()))


from math import floor, ceil, sqrt

def isclose(a, b, rel_tol=1e-09, abs_tol=0.0):
	return abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)

def isint(a):
	return isclose(float(int(a)), a)

def genTriangles(r):
	r2 = r * r
	for x in range(1, ceil(sqrt(3 * r2)) + 1):
		y = max(x, floor(r2 / x))
		while True:
			xy_r2 = x * y - r2
			if xy_r2 <= 0:
				y += 1
				continue
			z = r2 * (x + y) / xy_r2
			if z < y:
				break
			if isint(z):
				z = int(z)
				yield (x + y, x + z, y + z)
			y += 1
triangles = sorted(genTriangles(int(input())))
print(len(triangles))
for triangle in triangles:
	print(' '.join(map(str, triangle)))