Vampire

Mr. C is a vampire. If he is exposed to the sunlight directly, he turns into ash. Nevertheless, last night, he attended to the meeting of Immortal and Corpse Programmers Circle, and he has to go home in the near dawn. Fortunately, there are many tall buildings around Mr. C's home, and while the sunlight is blocked by the buildings, he can move around safely. The top end of the sun has just reached the horizon now. In how many seconds does Mr. C have to go into his safe coffin?

To simplify the problem, we represent the eastern dawn sky as a 2-dimensional x-y plane, where the x axis is horizontal and the y axis is vertical, and approximate building silhouettes by rectangles and the sun by a circle on this plane.

The x axis represents the horizon. We denote the time by t, and the current time is t=0. The radius of the sun is r and its center is at (0, -r) when the time t=0. The sun moves on the x-y plane in a uniform linear motion at a constant velocity of (0, 1) per second.

The sunlight is blocked if and only if the entire region of the sun (including its edge) is included in the union of the silhouettes (including their edges) and the region below the horizon (y ≤ 0).

Write a program that computes the time of the last moment when the sunlight is blocked.

The following figure shows the layout of silhouettes and the position of the sun at the last moment when the sunlight is blocked, that corresponds to the first dataset of Sample Input below. As this figure indicates, there are possibilities that the last moment when the sunlight is blocked can be the time t=0.


<image>


The sunlight is blocked even when two silhouettes share parts of their edges. The following figure shows the layout of silhouettes and the position of the sun at the last moment when the sunlight is blocked, corresponding to the second dataset of Sample Input. In this dataset the radius of the sun is 2 and there are two silhouettes: the one with height 4 is in -2 ≤ x ≤ 0, and the other with height 3 is in 0 ≤ x ≤ 2.


<image>


Input

The input consists of multiple datasets. The first line of a dataset contains two integers r and n separated by a space. r is the radius of the sun and n is the number of silhouettes of the buildings. (1 ≤ r ≤ 20, 0 ≤ n ≤ 20)

Each of following n lines contains three integers xli, xri, hi (1 ≤ i ≤ n) separated by a space.

These three integers represent a silhouette rectangle of a building. The silhouette rectangle is parallel to the horizon, and its left and right edges are at x = xli and x = xri, its top edge is at y = hi, and its bottom edge is on the horizon. (-20 ≤ xli < xri ≤ 20, 0 < hi ≤ 20)

The end of the input is indicated by a line containing two zeros separated by a space.

Note that these silhouettes may overlap one another.

Output

For each dataset, output a line containing the number indicating the time t of the last moment when the sunlight is blocked. The value should not have an error greater than 0.001. No extra characters should appear in the output.

Sample Input


2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0


Output for the Sample Input


0.0000
3.0000
2.2679
2.2679






Example

Input

2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0


Output

0.0000
3.0000
2.2679
2.2679

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
while True:
	(r, n) = list(map(int, input().split()))
	if r == 0:
		break
	b = [0 for i in range(60)]
	for i in range(n):
		(ll, rr, x) = list(map(int, input().split()))
		for j in range(ll, rr):
			b[30 + j] = max(b[30 + j], x)
	(b[30 - r - 1], b[30 + r]) = (1000000000.0, 1000000000.0)
	ans = 1000000000.0
	for x in range(30 - r, 30 + r + 1):
		t = (r ** 2 - (x - 30) ** 2) ** (1 / 2)
		cur = r - t + min(b[x], b[x - 1])
		ans = min(ans, cur)
	print(ans)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def main():
	rr = []
	while True:
		(r, n) = map(int, input().split())
		if r == 0 and n == 0:
			break
		a = [list(map(int, input().split())) for _ in range(n)]
		d = defaultdict(int)
		for (xl, xr, h) in a:
			for x in range(xl, xr):
				if d[x] < h:
					d[x] = h
		tr = float('inf')
		r2 = r ** 2
		for x in range(-r, r):
			h = d[x]
			k = min(abs(x), abs(x + 1))
			t = (r2 - k ** 2) ** 0.5
			xr = r - t + h
			if tr > xr:
				tr = xr
		rr.append('{:0.9f}'.format(tr))
	return '\n'.join(map(str, rr))
print(main())


while True:
	(R, N) = map(int, input().split())
	if not R | N:
		break
	geta = 20
	buildings = [0] * (geta * 2)
	for _ in range(N):
		(xl, xr, h) = map(int, input().split())
		for i in range(xl + geta, xr + geta):
			buildings[i] = max(buildings[i], h)
	(left, right) = (0, 20)
	while right - left > 0.0001:
		mid = (left + right) / 2
		flag = True
		for i in range(-R + geta, R + geta):
			if i < geta:
				y = pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5)
				flag &= buildings[i] >= y - R + mid
			else:
				y = pow(R * R - (i - geta) * (i - geta), 0.5)
				flag &= buildings[i] >= y - R + mid
		if flag:
			left = mid
		else:
			right = mid
	print('{:.20f}'.format(left))


import math

def ri():
	return int(input())

def rli():
	return list(map(int, input().split()))
(r, n) = rli()
while r != 0:
	shade = [0 for i in range(41)]
	shade[40] = 1145148101919
	t = [1145148101919 for i in range(41)]
	for i in range(n):
		(xl, xr, h) = rli()
		for j in range(xl + 20, xr + 20):
			shade[j] = max(shade[j], h)
	shade[20 - r - 1] = 1145148101919
	shade[20 + r] = 1145148101919
	for i in range(20 - r, 20 + r + 1):
		x = 20 - i
		t[i] = min(shade[i - 1], shade[i]) - math.sqrt(r ** 2 - x ** 2) + r
	print(min(t))
	(r, n) = rli()


while 1:
	(r, n) = map(int, input().split())
	if r == n == 0:
		break
	ans = [[float('inf') for i in range(100)] for j in range(100)]
	for y in range(100):
		for j in range(2 * r):
			x = j - r
			if x < 0:
				x += 1
			ans[y][j] = r + y - (r ** 2 - x ** 2) ** 0.5
	for i in range(n):
		(a, b, h) = map(int, input().split())
		for x in range(a, b):
			j = x + r
			for y in range(h):
				ans[y][j] = float('inf')
	a = float('inf')
	for i in ans:
		a = min(min(i), a)
	print(a)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10 ** 5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right

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

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

def LI_():
	return list(map(lambda x: int(x) - 1, stdin.readline().split()))

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

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

def LS():
	return list(map(list, stdin.readline().split()))

def S():
	return list(stdin.readline().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def A():
	while True:
		n = II()
		if not n:
			break
		a = IR(n)
		a.sort()
		print(sum(a[1:-1]) // (n - 2))
	return

def B():
	move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
	while True:
		(w, h) = LI()
		if w == h == 0:
			break
		field = SR(2 * h - 1)
		check = [[True] * (2 * w - 1) for i in range(2 * h - 1)]
		next = deque()
		next.append((0, 0))
		ans = 1
		flg = True
		while next and flg:
			now = next
			next = deque()
			while now:
				(x, y) = now.pop()
				for (mx, my) in move:
					(mmx, mmy) = (x + mx, y + my)
					if 0 <= mmx < 2 * w - 1 and 0 <= mmy < 2 * h - 1:
						if field[mmy][mmx] == '0' and check[mmy + my][mmx + mx]:
							next.append((mmx + mx, mmy + my))
							check[mmy + my][mmx + mx] = False
							if mmx + mx == 2 * w - 2 and mmy + my == 2 * h - 2:
								print(ans + 1)
								flg = False
								next = deque()
								now = deque()
								break
			ans += 1
		if flg:
			print(0)
	return

def C():
	while 1:
		(r, n) = LI()
		if r == n == 0:
			break
		lis = [0 for i in range(2 * r)]
		ans = inf
		for _ in range(n):
			(xl, xr, h) = LI()
			for i in range(2 * r):
				if xl + r <= i < xr + r:
					lis[i] = max(lis[i], h)
		for i in range(2 * r):
			if i < r:
				ans = min(ans, r - math.sqrt(r ** 2 - (r - i - 1) ** 2) + lis[i])
			else:
				ans = min(ans, r - math.sqrt(r ** 2 - (r - i) ** 2) + lis[i])
		print(ans)
	return

def D():
	return

def E():
	return

def F():
	return

def G():
	return

def H():
	return
C()


while True:
	(R, N) = map(int, input().split())
	if not R | N:
		break
	geta = 20
	buildings = [0] * (geta * 2)
	for _ in range(N):
		(xl, xr, h) = map(int, input().split())
		for i in range(xl + geta, xr + geta):
			buildings[i] = max(buildings[i], h)
	(left, right) = (0, 20)
	for _ in range(100):
		mid = (left + right) / 2
		flag = True
		for i in range(-R + geta, R + geta):
			if i < geta:
				y = pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5)
				flag &= buildings[i] >= y - R + mid
			else:
				y = pow(R * R - (i - geta) * (i - geta), 0.5)
				flag &= buildings[i] >= y - R + mid
		if flag:
			left = mid
		else:
			right = mid
	print('{:.20f}'.format(left))


from math import sqrt
while True:
	(R, N) = map(int, input().split())
	if not R | N:
		break
	geta = 20
	buildings = [0] * (geta * 2)
	for _ in range(N):
		(xl, xr, h) = map(int, input().split())
		for i in range(xl + geta, xr + geta):
			buildings[i] = max(buildings[i], h)
	print(min((buildings[i] - sqrt(R * R - (i - geta + (i < geta)) * (i - geta + (i < geta))) + R for i in range(-R + geta, R + geta))))


while True:
	(R, N) = map(int, input().split())
	if not R | N:
		break
	geta = 20
	buildings = [0] * (geta * 2)
	for _ in range(N):
		(xl, xr, h) = map(int, input().split())
		for i in range(xl + geta, xr + geta):
			buildings[i] = max(buildings[i], h)
	sun = [0] * (geta * 2)
	for i in range(-R + geta, R + geta):
		if i < geta:
			buildings[i] -= pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5) - R
		else:
			buildings[i] -= pow(R * R - (i - geta) * (i - geta), 0.5) - R
	(left, right) = (0, 20)
	while right - left > 0.0001:
		mid = (left + right) / 2
		flag = True
		for i in range(-R + geta, R + geta):
			if i < geta:
				flag &= buildings[i] >= mid
			else:
				y = pow(R * R - (i - geta) * (i - geta), 0.5)
				flag &= buildings[i] >= mid
		if flag:
			left = mid
		else:
			right = mid
	print('{:.20f}'.format(left))


import sys
import math
OFFSET = 20

def main():
	while True:
		(r, n) = map(int, sys.stdin.readline().split())
		if r == 0 and n == 0:
			break
		seq = [0] * 40
		for i in range(n):
			(x1, x2, h) = map(int, sys.stdin.readline().split())
			for k in range(x1, x2):
				seq[k + OFFSET] = max(seq[k + OFFSET], h)
		ans = 9999999999
		for x in range(-r + 1, r):
			y = min(seq[x + OFFSET - 1], seq[x + OFFSET])
			t = y + r - math.sqrt(r * r - x * x)
			ans = min(ans, t)
		print('{0:.4f}'.format(ans))
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 998244353
dd = [(0, -1), (1, 0), (0, 1), (-1, 0)]
ddn = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

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

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	rr = []
	while True:
		(r, n) = LI()
		if r == 0 and n == 0:
			break
		a = [LI() for _ in range(n)]
		d = collections.defaultdict(int)
		for (xl, xr, h) in a:
			for x in range(xl, xr):
				if d[x] < h:
					d[x] = h
		tr = inf
		r2 = r ** 2
		for x in range(-r, r):
			h = d[x]
			k = min(abs(x), abs(x + 1))
			t = (r2 - k ** 2) ** 0.5
			xr = r - t + h
			if tr > xr:
				tr = xr
		rr.append('{:0.9f}'.format(tr))
	return '\n'.join(map(str, rr))
print(main())


while True:
	(R, N) = map(int, input().split())
	if not R | N:
		break
	geta = 20
	buildings = [0] * (geta * 2)
	for _ in range(N):
		(xl, xr, h) = map(int, input().split())
		for i in range(xl + geta, xr + geta):
			buildings[i] = max(buildings[i], h)
	ans = 20
	for i in range(-R + geta, R + geta):
		if i < geta:
			buildings[i] -= pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5) - R
		else:
			buildings[i] -= pow(R * R - (i - geta) * (i - geta), 0.5) - R
		ans = min(ans, buildings[i])
	print(ans)


while True:
	(R, N) = map(int, input().split())
	if not R | N:
		break
	geta = 20
	buildings = [0] * (geta * 2)
	for _ in range(N):
		(xl, xr, h) = map(int, input().split())
		for i in range(xl + geta, xr + geta):
			buildings[i] = max(buildings[i], h)
	print(min((buildings[i] - pow(R ** 2 - (i - geta + (i < geta)) ** 2, 0.5) + R for i in range(-R + geta, R + geta))))


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, datetime
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

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

def inpl_str():
	return list(input().split())

def calc(p, x):
	return p * (100 + x) // 100
while True:
	(r, n) = inpl()
	if r == 0:
		break
	else:
		heights = defaultdict(int)
		ans = INF
		for _ in range(n):
			(xl, xr, h) = inpl()
			heights[xl + 0.1] = max(heights[xl + 0.1], h)
			heights[xr - 0.1] = max(heights[xr - 0.1], h)
			for x in range(xl + 1, xr):
				heights[x - 0.1] = max(heights[x - 0.1], h)
				heights[x + 0.1] = max(heights[x + 0.1], h)
		for x in range(-23, 23):
			h = min(heights[x - 0.1], heights[x + 0.1])
			if r > abs(x):
				tmp = h - (r ** 2 - x ** 2) ** (1 / 2)
				ans = min(ans, tmp + r)
		print(ans)


from math import sqrt

def inpl():
	return list(map(int, input().split()))
(R, N) = inpl()
while R:
	H = [0] * 41
	r0 = 0
	l0 = 0
	for _ in range(N):
		(l, r, h) = inpl()
		if l < 0 and r >= 0:
			l0 = max(l0, h)
		if l <= 0 and r > 0:
			r0 = max(r0, h)
		l += l <= 0
		r -= r >= 0
		for i in range(l, r + 1):
			if i != 0:
				H[i + 20] = max(H[i + 20], h)
	H[20] = min(l0, r0)
	ans = 20
	for x in range(-R + 1, R):
		time = R - sqrt(R ** 2 - x ** 2) + H[x + 20]
		ans = min(ans, time)
	print(ans)
	(R, N) = inpl()


while 1:
	co = [0 for i in range(40)]
	(r, n) = map(int, input().split())
	if r == n == 0:
		break
	for i in range(n):
		(a, b, h) = map(int, input().split())
		a += 20
		b += 20
		for j in range(a, b):
			co[j] = max(co[j], h)
	r_list = []
	for i in range(r):
		r_list.append((r ** 2 - i ** 2) ** 0.5 + 500)
	r_list = [-9999 for j in range(20 - r)] + r_list[::-1] + r_list + [-9999 for j in range(20 - r)]
	for i in range(40):
		if co[i] < r_list[i]:
			tmp = r_list[i]
			r_list = list(map(lambda x: x - (tmp - co[i]), r_list))
	print(r_list[20])


import math
while True:
	(r, n) = map(int, input().split())
	if r == 0 and n == 0:
		break
	sun_place = [-10000000000000000000 for _ in range(r)]
	for i in range(r):
		sun_place[i] = 0 - r + math.sqrt(r * r - i * i)
	ans = 10000000000000000
	bilding1 = [0 for i in range(len(sun_place))]
	bilding2 = [0 for i in range(len(sun_place))]
	for i in range(n):
		(x1, x2, h) = map(int, input().split())
		if x1 < -r:
			x1 = -r
		if r <= x2:
			x2 = r
		for j in range(x1, x2):
			if j < 0:
				j += 1
				bilding1[abs(j)] = max(h, bilding1[abs(j)])
			else:
				bilding2[abs(j)] = max(h, bilding2[abs(j)])
	for i in range(len(sun_place)):
		ans = min(ans, bilding1[i] - sun_place[i])
		ans = min(ans, bilding2[i] - sun_place[i])
	print(ans)